[Haskell-cafe] Re: Laziness leaks

[Loup Vaillant]

2008/6/4 apfelmus <apfelmus at quantentunnel.de>:
> [...]
> But it can waste space (-> "space leak"), for instance by
> accumulating a big expression like
>
>  (..) -> ((..)+1) -> (((..) + 1) + 1) -> etc.
>
> instead of evaluating  x+1  immediately
>
>   5   -> 6        -> 7                -> etc.

So, it is called a "space leak" because the asymptotic space required
is greater in a lazy setting compared to a strict setting. Then, what
about:

sum . map (\x -> 2 * x + 42) $ [1..9999999]

Provided sum works in constant space (needs proper tail calls and the
right level of stricness), this runs in constant space in Haskell,
deforestation or not. However, the equivalent code in, say, Ocaml,
will work in linear space in the absence of deforestation. So, in this
case, I find legitimate to talk about a "strictness space leak". Well,
is it? Of course it uses linear space, there is no "leak"! hummm.

It feels like only lazy evaluation can be accused of space leak, while
strict evaluation cannot. Are we biased in favour of strict
evaluation? I mean, if we take strict evaluation as the default
(because it's mainstream), it is easy to think that lazy evaluation is
cool when better, but unacceptable when worse. Hence the word "leak".

Just my two cents,
Loup