"Ch. A. Herrmann" <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
