[Haskell-cafe] Space and time leaks

Dan Weston westondan at imageworks.com
Thu Oct 4 14:59:36 EDT 2007


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?

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?



More information about the Haskell-Cafe mailing list