Evaluation order, ghc versus hugs, lazy vs. strict

[Alastair Reid]

> main = print $ sum [0..1000000]

> When you use a sufficiently large number (perhaps 10000000 instead
> of 1000000), both ghci and ghc terminate with "Stack space
> overflow".  On the other hand, Hugs (dated December 2001) runs the
> example OK and produces the result of 500000500000.

> I have the following questions:

> 1. Why does this happen? Why does not ghc Haskell generate the list
> lazily, summing as he goes and forgetting what he no longer needs?

As you've apparently discovered, the trick is to be lazy but not too
lazy.  That is, you want to generate the list lazily but compute a
partial result (i.e., the running total of that part of the list
processed so far) strictly.

GHC and Hugs both produce the list lazily.

Hugs uses foldl' instead of foldl to define sum:

  foldl'           :: (a -> b -> a) -> a -> [b] -> a
  foldl' f a []     = a
  foldl' f a (x:xs) = (foldl' f $! f a x) xs
  
  sum               = foldl' (+) 0
  
foldl' behaves exactly like foldl except that it is a little stricter.
(To turn foldl' into foldl, replace the $! on the 3rd line with $.  $!
is the strict version of 'apply' ($).)

With a great deal of effort, one could construct examples where Hugs
fails to behave as the Haskell report requires.  

My guess is that GHC doesn't have this optimization.  But I'd also
have guessed that GHC would have automatically inferred this
optimization if you compile with -O2 

> 3. How can I tell Haskell what I want ?  a) that the (+) in sum is
> strict. It is in this case but in other more complex, like "foldl1 f
> [0..1000000]" I end up with closures f ( f ( f ( f ( ....)))) which
> are not evaluated until the end.

Use foldl'

More importantly, understand how foldl' works and be ready to
apply the same analysis and fix to any similar function.  


--
Alastair Reid                 alastair@reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/