# Strict foldl

**Manuel M. T. Chakravarty
**
chak@cse.unsw.edu.au

*Fri, 07 Dec 2001 10:34:40 +1100*

"Ch. A. Herrmann" <herrmann@infosun.fmi.uni-passau.de> wrote,
>* which compiler settings do I have to pass to ghc-5.02
*>* in order to achieve that the strictness analyzer
*>* recognizes strictness of (+) in foldl and computes
*>* sum in constant space?
*>*
*>* Prelude> sum [1..10000000]
*>*
*>* had the following effect:
*>*
*>* PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND
*>* 23542 herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02
*
Is this what I think it is? Do you benchmark the
interpreter? Interpreted code isn't optimised. When I
compile
main = print $ sum [1..10000000]
with -O2, it takes 13s on a 600MHz P3 and runs in 1.5MB of
space.
Now, you may think that `sum' should have been compiled
optimised in the Prelude and you just call this optimised
version from the interpreter. However, this reasoning is
flawed for a number of reasons (one being that you won't
make use of specialised versions of Prelude functions in
this way).
>* Of course, one could define a strict foldl oneself:
*>*
*>* > sfoldl f e [] = e
*>* > sfoldl f e (x:xs) = (sfoldl f $! (f e x)) xs
*>*
*>* ( > sfoldl (+) 0 [1..10000000]
*>* returns 50000005000000 in about a minute interpreted
*>* using 18MB of total space.)
*>*
*>* But with the own definition one has to redefine many of the prelude functions.
*
GHC's Prelude does not define `sum' in terms of foldl;
instead, it uses the definition
sum :: (Num a) => [a] -> a
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
The Prelude also defines a specialisation of the function
for `Integer' (which is what you get in your example) by way
of
{-# SPECIALISE sum :: [Integer] -> Integer #-}
I haven't checked the Core code produced for the above
definition, but as I know GHC, I am pretty sure that it
compiles the Prelude definition into a nice tight loop
making use of all available strictness.
Cheers,
Manuel