On Fri, Dec 15, 2006 at 10:05:38AM +0000, Felix Breuer wrote: > On Thu, 14 Dec 2006 15:31:54 -0800, David Roundy <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe