[Haskell-cafe] Break Function Using Lazy Pairs

[Leon Smith]

That example doesn't particularly "tie the knot",  unless you count
the fact that "break" is itself a recursive function.  Usually "tie
the knot" refers to some kind of circular programming,  i.e. a
self-referential data structure,  or explicit use of Data.Function.fix
to produce a recursive function  (as is useful in e.g. dynamic
programming)

Also,  you aren't understanding the laziness of the return product;
instead you are still thinking of this example in terms of eager
evaluation as almost every other programming language uses.   A better
approximation of what is going on could be represented textually as:

-- break "hi\nbye"
-- ( 'h' : ys, zs )   where (  ys, zs  ) = break "i\nbye"
-- ( 'h' : 'i' : ys, zs )   where (  ys, zs  ) = break "\nbye"
-- ( 'h' : 'i' : [] , "bye")

Of course,  if you want to get more pendantic,  I've glossed over
steps involving the conditional and something resembling
beta-reduction.   Incidentally,  it's the latter part I omitted which,
 naively implemented,  creates the space leak referred to in the
original post.

Best,
Leon

On Mon, Apr 5, 2010 at 5:19 PM, aditya siram <aditya.siram at gmail.com> wrote:
> Hi all,
> For the past couple of weeks I've been trying to understand
> tying-the-knot style programming in Haskell.
>
> A couple of days ago, Heinrich Apfelmus posted the following 'break'
> function as part of an unrelated thread:
> break []     = ([],[])
> break (x:xs) = if x == '\n' then ([],xs) else (x:ys,zs)
>               where (ys,zs) = Main.break xs
>
> I've stepped through the code manually to see if I understand and I'm
> hoping someone will tell me if I'm on the right track:
> -- break "hi\nbye" =
> --    let f1 = (break "i\nbye")
> --           = let f2 = (break "\nbye")
> --                    = ([],"bye")
> --             ('i' : fst f2, snd f2) => ('i' : [], "bye")
> --    ('h' : fst f1, snd f1) => ('h' : 'i' : [], "bye")
> --                           => ("hi","bye")
>
> -deech
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>