[Haskell-cafe] Optmiization of recursion

Adrian Hey ahey at iee.org
Tue Sep 28 17:01:09 EDT 2004

On Tuesday 28 Sep 2004 8:17 pm, John Goerzen wrote:
> On Tuesday 28 September 2004 01:54 am, Iavor S. Diatchki wrote:
> > OTOH there are a few classical cases in haskell where you run out of
> > space even if you have a tail
> > recursive function: e.g.
> > sum n [] = n
> > sum n (y:ys) = sum (n + y) ys
> > the reason for this that the n+y expression never gets evaluated
> > until the very end,
> > so you create many suspensions in memory.
> Eep.  So that seems like being stuck between a rock and a hard place.
> (Thanks for mentioning it, btw)

You can fix this kind of problem with "seq"
sum n [] = n
sum n (y:ys) = let n' = n + y in n' `seq` sum n' ys

But AFAIK this should be unnecessary in this case with ghc (and others
probably) because sum is strict in it's first argument and the strictness
analyser should detect this and avoid pointless laziness. You probably
need to compile with -O to get this to happen though.

But in cases where the function isn't strict (or you're not sure,
or you're not sure about the compilers ability to infer strictness)
you can get rid of unwanted laziness for sure using seq.
Using $! is an alternative.

Adrian Hey 

More information about the Haskell-Cafe mailing list