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.si...@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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
