On Sat, Apr 17, 2010 at 8:22 AM, Jason Dagit <da...@codersbase.com> wrote: > ... > One place where lazy accumulators is bad are the left folds. There is the > lazy foldl and the version which is strict in the accumulator, foldl'. Try > summing big lists of integers, let's use ghci and limit the heap to 1 meg:
> ghci +RTS -M1M > Prelude> foldl (+) 0 [1..10000000] > Heap exhausted; > Current maximum heap size is 6291456 bytes (6 MB); > use `+RTS -M<size>' to increase it. If we define foldl as: foldl :: (b -> a -> b) -> b -> [a] -> b foldl f z [] = z foldl f z (x:xs) = let z' = f z x in foldl f z' xs and: sum :: [Int] -> Int sum = foldl (+) 0 Then the program: 'sum 1000000' will indeed use a lot of heap space (and will run out of it if you limit the heap to 1MB). The reason for this is explained in [1]. In short: foldl will start allocating thunks on your heap which each add an element of the list to a previous thunk as in: let z1 = 0 + 1 z2 = z1 + 2 z3 = z2 + 3 z4 = z3 + 4 ... z999997 = z999996 + 999997 z999998 = z999997 + 999998 z999999 = z999998 + 999999 z100000 = z999999 + 1000000 in z1000000 This can be visualized if we generate a heap profile: $ ghc --make FoldlProfile.hs -o foldlProfile -O2 -prof $ ./foldlProfile 1000000 +RTS -hy Stack space overflow: current size 8388608 bytes. $ hp2ps -c foldlProfile.hp $ ps2pdf foldlProfile.ps Result: http://bifunctor.homelinux.net/~bas/foldlProfile.pdf You clearly see that this program allocates well over 22MB of heap space! This is not a problem if you can give the program a big enough heap. However have you noticed the more serious problem? The problem starts when we finally evaluate z1000000: Note that z1000000 = z999999 + 1000000. So 1000000 is pushed on the stack. Then z999999 is evaluated. Note that z999999 = z999998 + 999999. So 999999 is pushed on the stack. Then z999998 is evaluated: Note that z999998 = z999997 + 999998. So 999998 is pushed on the stack. Then z999997 is evaluated: So ... ...your limited stack will eventually run full when you evaluate a large enough chain of (+)s. This then triggers a stack overflow exception! Interestingly, when we define foldl as: foldl :: (b -> a -> b) -> b -> [a] -> b foldl f = foldl_f where foldl_f z [] = z foldl_f z (x:xs) = let z' = f z x in foldl_f z' xs then both the heap and stack overflow problems go away. (this is how foldl is actually implemented[2] in GHC) I don't know why the heap and stack overflow problems go away. So lets look at the core output of the latter program: $ ghc-core -- -O2 FoldlProfile.hs $wsum :: [Int] -> Int# $wsum = \ (w_s1rS :: [Int]) -> $wfoldl_f 0 w_s1rS $wfoldl_f :: Int# -> [Int] -> Int# $wfoldl_f = \ (ww_s1rK :: Int#) (w_s1rM :: [Int]) -> case w_s1rM of _ { [] -> ww_s1rK; : x_aeb xs_aec -> case x_aeb of _ { I# y_aUb -> $wfoldl_f (+# ww_s1rK y_aUb) xs_aec } } Apparently, because of the latter foldl definition, GHC is able to optimize the foldl for uboxed ints. But why doesn't the recursive call: $wfoldl_f (+# ww_s1rK y_aUb) xs_aec allocate (+# ww_s1rK y_aUb) on the heap? Are unboxed values always evaluated strictly? For reference, this is the core output of the former foldl: sum :: [Int] -> Int sum = foldl @ Int @ Int plusInt main3 main3 = I# 0 foldl :: forall b_aer a_aes. (b_aer -> a_aes -> b_aer) -> b_aer -> [a_aes] -> b_aer foldl = \ (@ b_afF) (@ a_afG) (f_aet :: b_afF -> a_afG -> b_afF) (z_aeu :: b_afF) (ds_drS :: [a_afG]) -> case ds_drS of _ { [] -> z_aeu; : x_aex xs_aey -> foldl @ b_afF @ a_afG f_aet (f_aet z_aeu x_aex) xs_aey } regards, Bas [1] http://haskell.org/haskellwiki/Foldr_Foldl_Foldl' [2] http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/GHC-List.html#foldl _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe