Strict foldl

Jan Kort kort@science.uva.nl
Fri, 07 Dec 2001 12:05:20 +0100


"Ch. A. Herrmann" wrote:
> 
> Hi Haskellers,
> 
> 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
> 
> Of course, one could define a strict foldl oneself:
> 
> > sfoldl f e [] = e
> > sfoldl f e (x:xs) = (sfoldl f $! (f e x)) xs

There is a foldl' in the Hugs Prelude that does this:

foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = (foldl' f $! f a x) xs

There are some functions in the Hugs Prelude that use
foldl (or foldl1) and some use foldl'. Maybe someone
can explain why certain functions use foldl: reverse,
maximum, minimum and readInt, while others use foldl':
length, sum and product.
I can understand why reverse would use foldl, but
why do maximum, minimum and readInt use foldl ? Maybe
the function foldl1 was based on foldl' at one time ?

  Jan