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?