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