[Haskell-cafe] Stack, Heap and GHC
Ian Lynagh
igloo at earth.li
Sat Dec 16 12:39:24 EST 2006
On Fri, Dec 15, 2006 at 10:05:38AM +0000, Felix Breuer wrote:
> On Thu, 14 Dec 2006 15:31:54 -0800, David Roundy <droundy at darcs.net> wrote:
> >
> > main = do putStrLn "strict foldl1"
> > print $ foldl1' (\a b -> a + 1) $ [1..largenum]
> > putStrLn "lazy foldl1"
> > print $ foldl1 (\a b -> a + 1) $ [1..largenum]
>
> 2) Let me see if I get this right. The strict version runs in constant
> space because in the expression
>
> (((1 + 1) + 1) ... + 1)
>
> the innermost (1 + 1) is reduced to 2 right away.
The strict version never creates the expression (((1 + 1) + 1) ... + 1).
It's easier to see with foldl':
foldl' (\a b -> a + 1) 0 [1..3]
{ evaluates 0+1 = 1 }
-> foldl' (\a b -> a + 1) 1 [2..3]
{ evaluates 1+1 = 2 }
-> foldl' (\a b -> a + 1) 2 [3..3]
{ evaluates 2+1 = 3 }
-> foldl' (\a b -> a + 1) 3 []
-> 3
> The lazy version first
> uses a huge amount of heap space by building the entire expression
>
> (((1 + 1) + 1) ... + 1)
>
> on the heap. The evaluation of this expression starts by placing the
> outermost + 1 on the stack and continues inward, not actually reducing
> anything, before everything has been placed on the stack, which causes
> the overflow. Correct?
Right, foldl doesn't evaluate its argument as it goes, so it builds
(((0+1)+1)+1) (on the heap):
foldl (\a b -> a + 1) 0 [1..3]
-> foldl (\a b -> a + 1) (0+1) [2..3]
-> foldl (\a b -> a + 1) ((0+1)+1) [3..3]
-> foldl (\a b -> a + 1) (((0+1)+1)+1) []
-> (((0+1)+1)+1)
Now we need to evaluate (((0+1)+1)+1) to get the final answer. You can
imagine a simple recursive evaluation function which, in the call
evaluate (((0+1)+1)+1)
recursively calls
evaluate ((0+1)+1)
which recursively calls
evaluate (0+1)
and it is this recursion that has a stack that overflows.
Thanks
Ian
More information about the Haskell-Cafe
mailing list