[Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
bf3 at telenet.be
Sat Aug 18 14:35:18 EDT 2007
When reading an article about tail recursion
html) I came across the follow statements:
"If you can write a non-recursive function that uses the colon syntax it is
probably better than a tail recursive one that doesn't. This is because
Haskell's lazy evaluation enabled you to use the non-tail recursive version
on an infinite stream without getting a stack overflow. "
""Unfortunately", laziness "gets in the way". While transforming
non-tail-recursive code to a tail-recursive form is important and useful for
functional programming in general, dealing with laziness requires a little
more care, and often "non-tail-recursive" versions are preferrable. flatten
is an example of this, the first version is better in many ways. While I
don't believe it happens in this case, oftentimes naively writing code
"tail-recursively" in Haskell will actually -make- it overflow the stack.
Another (actual) benefit of the first version of flatten is that it will
work on infinite lists. http://www.haskell.org/hawiki/StackOverflow gives a
simple example and some explanation."
Unfortunately I can't find the StackOverflow page anymore.
Now if I understand this correctly, this just means that when writing
foo n = if n<0 then  else n : foo (n-1)
bar n = aux 0  where
aux i xs = if i>n then xs else aux (i+1) (i:xs)
that foo is more efficient than bar because lazy evaluation of foo just puts
the delayed computation in the "cdr" of the list, while lazy evaluation of
bar has to keep track of all aux calls (the "closures") which gives much
more overhead, maybe even stack overflow? Something like that?
More information about the Haskell-Cafe