[Haskell-cafe] Stack, Heap and GHC

[Felix Breuer]

On Thu, 14 Dec 2006 15:31:54 -0800, David Roundy <droundy at darcs.net> wrote:
> import Data.List
> 
> largenum = 1000000
> 
> main = do putStrLn "strict foldl1"
>           print $ foldl1' (\a b -> a + 1) $ [1..largenum]
>           putStrLn "lazy foldl1"
>           print $ foldl1 (\a b -> a + 1) $ [1..largenum]
> 
> 
> It gets through the first one, but not the second call, which differs only
> in the strictness of the foldl.  You can make it use up more memory by
> making largenum a hundred times bigger, in which case for some reason it
> doesn't seem to have a stack error (although it hasn't completed on my
> computer, and uses something like 2G of memory).  Perhaps the thunks are
> placed on the heap, and only when they are actually evaluated does
> anything
> go onto the stack?

1) What precisely is a thunk?

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 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?


Thanks for your help!

Felix