"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