On Thu, 2008-05-29 at 23:48 -0400, Tyson Whitehead wrote:
main = print $ foldl' (+) 0 [1..]
with
foldl' f y xs = foldl' y xs where foldl' y [] = y foldl' y (x:xs) = foldl' (f y x) xs
runs indefinitely with very little memory consumption, while
foldl' f y [] = y foldl' f y (x:xs) = foldl' f (f y x) xs
rapidly consumes all the machine's memory and dies.
This is for two reasons. One is because your second foldl' is directly recursive so does not get inlined. The static argument transformation it what you're doing manually to turn the latter into the former. The SAT is implemented in ghc 6.9 (though it seems to be having integration problems). The reason the second version consumes all the memory is because it is not strict in the accumulator. You're misleading yourself by calling it foldl', you've actually written the standard foldl. The reason the first version does not consume all the memory is because once foldl' got inlined there is enough information for the strictness analyser to see that it is indeed all strict (for the particular parameters, not for all possible parameters as is the case with the real foldl'). Duncan