[Haskell-cafe] why does a foldr not have a space leak effect?

[Mathieu Boespflug]

"Albert Y. C. Lai" <trebla at vex.net> writes:

> On 12-07-23 10:52 PM, Qi Qi wrote:
>> Foldl has the space leak effect, and that's why foldl' has been
>> recommended.
>
> foldr (+) and foldl (+) for Int have the same asymptotic costs, both
> time and space. See my http://www.vex.net/~trebla/haskell/lazy.xhtml
>
> Therefore, I do not understand why they are labeled opposite space-leakness.

That may be true, but if the function argument supplied to foldr is lazy
in its second argument, then the story can be quite different. Remember
that foldr on a list [x1..xn] produces a chain of the following form:

f x1 (f x2 ... (f xn z))

If f is lazy in its second argument, then evaluating the head of this
chain does not force evaluation of the rest of the chain. Therefore, if
you evaluate this chain from left to right and immediately discard each
element in the chain as you go along, then this can be done in constant
space.

One example of this is when you evaluating the result of a right fold on
an infinite list in ghci:

ghci> foldr (\x y -> x + 10 : y) [] [1..]
<copious output ...>

To display the resulting list, ghci evaluates the head of the list,
displays it to the screen, then evaluates the head of the tail, the head
of the tail of the tail... and so on. After displaying an element of the
list, it can be reclaimed by the garbage collector.

Hope this helps,

-- Mathieu