[Haskell-cafe] Re: Space and time leaks

[ChrisK]

Dan Weston wrote:
> Ronald Guida wrote:
>> I need some help with space and time leaks.
>>
>> I know of two types of space leak.  The first type of leak occurs when
>> a function uses unnecessary stack or heap space.
>>
>> GHCi> sum [1..10^6]
>> *** Exception: stack overflow
>>
>> Apparently, the default definition for "sum" has a space leak.
>> I can define my own sum in terms of strict foldl ...
>>
>>  > sum' xs = foldl' (+) 0 xs
>>
>> ... and it doesn't overflow the stack.
>>
>> GHCi> sum' [1..10^6]
>> 500000500000
>> (0.27 secs, 112403416 bytes)
> 
> But it fills the heap? My intuition is that
> 
>   foldr (+) 0 [1..10^6]
> 
> is the fusion of a good producer and consumer so no heap is wasted
> constructing [1..10^6] but the stack is instead filled with
> (1+),(2+),...,(999999+) unary functions, whereas
> 
>   foldl' (+) 0 [1..10^6]
> 
> does not fill the stack with anything but does fill the heap with
> [1..10^6] because foldl' is no longer a good consumer?

Nope, it runs in small space.  The [1..10^6] is evaluated lazily, it is never
larger than the thunk that represent the rest of the list.  If foldl' is a "good
consumer" then GHC can avoid making the list's cons-cells (:).  If foldl' is not
a "good consumer" then then each cons cell is created and then quickly garbage
collected.

> 
> If so, it seems that the stack is smaller than the heap (or else the
> size of (1+) is much larger than that the element of an [Int].
> 
> Anyone know the truth of any of this?