Strict foldl

[Manuel M. T. Chakravarty]

"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