Recursive functions and constant parameter closures (inlining/strictness analyzer question)

[Duncan Coutts]

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