[Haskell-cafe] Stack, Heap and GHC

Felix Breuer felix at fbreuer.de
Fri Dec 15 05:05:38 EST 2006


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




More information about the Haskell-Cafe mailing list