Wow! If Ralf is right, then foldl in a lazy language always generates a
space leak and should be avoided in favor of strictFoldl.
However, I still am not clear why explicity strictness is required for
foldl to behave properly. In fact it seems like the problem is
insufficient laziness.
If you use a different (but still lazy) definition of foldl:
> myFoldl f s [] = s
> myFoldl f s (x:xs) = f s (foldl f x xs)
Alastair and Ralf say you get this spaceleak:
total = myFoldl (+) 0 [1..100000]
...
total = 0 + 1 + 2 + (myFoldl (+) 3 [4..100000])
...
But, why isn't foldl evaluated lazily?
Addition is left associative so computation of total should consume
addition operations until it needs to make the next fold. So you would
have:
> total = 3 + (myFoldl (+) 3 [4..100000])
Folding again generates another addition to consume:
> total = 3 + 4 + (myFoldl (+) 4 [5..100000])
Then Haskell should add 3+4 and then call myFoldl again.
My alternative definition of foldl also causes both hugs and ghc to fail
so either Haskell is insufficiently lazy or my analysis in incorrect.
I assume the later, but I don't understand why. (The explanation is
Paulson didn't help and I don't have Bird)
As an aside, I think strictFoldl is not automatically paralellizable, but
myFoldl may be. Specifically, if the compiler can deduce that addition is
fully associative, it would know that:
> total = (myFoldl (+) 0 [1..50000]) + (myFoldl (+) 50001 [50002..100000])
And compute the individual myFoldls on separate processors.
(I know very little about parallel computing so this is just an intuition)
-Alex-
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-212-697-0184 voice 1-212-697-1427 fax
On Fri, 26 Jun 1998, Ralf Hinze wrote:
> > When I try to execute this:
> >
> > > result = foldl (+) 0 [1..100000]
> > > main = putStr $show (result `mod` 10)
> >
> > Hugs gives: ERROR: Garbage collection fails to reclaim sufficient space
> > GHC gives: Stack space overflow: current size 262152 bytes.
> >
> > Why would this have an error? The list should be constructed lazily as it
> > is consumed by the sum. I assume I have a space leak but I can't figure
> > out why.
>
> `foldl' constructs the expression ... 3+(2+(1+0)) but does not evaluate
> it. A common space leak with lazy evalution, see Paulson, ML for the
> working programmer, p.47. Try this one
>
> > strictFoldl :: (Eval b) => (b -> a -> b) -> b -> [a] -> b
> > strictFoldl (*) = f
> > where f e [] = e
> > f e (a:x) = strict f (e * a) x
>
> > result = strictFoldl (+) 0 [1..100000]
> > main = putStr $ show (result `mod` 10)
>
> Cheers, Ralf
>
