[Haskell-beginners] lazyness and tail recursion

[Will Ness]

Ovidiu Deac <ovidiudeac <at> gmail.com> writes:

> 
> I've read the paragraph below from Real World Haskell
>
(http://book.realworldhaskell.org/read/efficient-file-processing-regular-expressions-and-file-name-matching.html
> section "An important aside: writing lazy functions")
> 
> I can get a feeling why lazyness compensates for the lack of tail
> recursion but I don't really understand why it would work in general.
> 
> My understanding is that that a function which returns a list with
> non-tail recursion would only work this way with certain usage
> patterns. In this case the caller of the funtion will have to use the
> string in a stream-like fashion.

The concept of tail recursion modulo cons is similar. Wikipedia has an article.
Basically it's about keeping one execution frame above the tail-recursive one.
Lazily accessing a list from the top is a lot like adding elements to it one by
one at the bottom. Prefixing a recursive call with an operation of fixed number
of operations is OK, because they will get consumed and the recursive case
called, in a fixed number of steps - the instance between current point and next
recursive invocation point won't grow, only get increased at times by a set
amount and then get consumed. 

The problem with non-tail recursion in lazy setting is that the distance grows
between the current point and the next invocation, and so the amount of "what to
do next?" information grows all the time. In imperative setting it gets flipped
into "what to do after the invocation" but it still grows. In tail-recursion
(even modulo cons, or (++) with fixed prefix) it's bounded, finite, constant.
Looking at Scheme example code in WP "continuation-passing style" article might
help. There we see as in translations of tail-recursive functions the
constructed continuation does not grow in unlimited fashion, instead only maybe
getting prefixed by a fixed amount of operations at times.

Does it make any sense? :)