Re: [Haskell-cafe] Stack, Heap and GHC

On Fri, Dec 15, 2006 at 10:05:38AM +0000, Felix Breuer wrote:

On Thu, 14 Dec 2006 15:31:54 -0800, David Roundy 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