foldl looks like this:
foldl k z [] = z
foldl k z (x:xs) = foldl k (z `k` x) xs
To work in constant space, foldl needs to evaluate its second argument
before the call, rather than building a thunk that is later forced
(which in turn builds stack). But in general, foldl is not strict in z.
What's needed is either to inline foldl, or to have a version
that's suitable for a strict argument, such as (+). GHC currently lacks
a way to exploit such a version (side conditions on a rewrite rule?)
and does not do the former since foldl is recursive.
Alternatively, you can write
foldl_strict k z [] = z
foldl_strict k z (x:xs) = z1 `seq` foldl k z1 xs
where
z1 = z `k` x
and then define
sm = foldl_strict (+) 0
And you should get what you want. I hope.
Simon
> -----Original Message-----
> From: [EMAIL PROTECTED]
> Sent: Thursday, May 27, 1999 6:17 AM
> To: [EMAIL PROTECTED]
> Subject: `sum' in ghc-4.02
>
>
> ghc-4.02 treats sum strangely.
> In the below program, sum xs needs small, constant size stack,
> sm xs needs stack proportional to length xs.
> And sm is the implementation of sum shown in src/.../PrelList.lhs
> I apply ghc -c -O.
> What keys are needed to code sum like it is in this
> ghc-4.02-linux-i386-unknown binary?
>
> Generally, how to make the compiler to save stack in the simplest
> functions, like sum, specialized to Integer?
> (apart of strictness annotations).
>
> ------------------
> Sergey Mechveliani
> [EMAIL PROTECTED]
>
>
>
> -------------------------------------
> sm = foldl (+) 0
> {-# SPECIALISE sm :: [Int] -> Int #-}
>
> main = let xs = [1..789000] :: [Int]
> s1 = sum xs
> s2 = sm xs
> in putStr (shows s2 "\n")
>
>
>
>
>
>
