Isn't this tail recursive?

Simon Marlow [email protected]
Mon, 11 Mar 2002 11:54:18 -0000


> On 10 Mar 2002, Jyrinx wrote:
>=20
> > In the case expression at the end of countAll, each of the=20
> values looks
> > to me like a recursive tail call - I should think (hope?)=20
> that it would
> > be optimized by GHC into a goto statement (a la Scheme). Instead, my
> > program eats up memory (I've got 256 MB) until the RTS=20
> whines about a
> > stack overflow.
>=20
> It is tail recusive. unfortunately, that's not the problem.
> apparently ghc is not smart enough to realize that countAll' should
> really be strict in basically all arguments.  (hell, I'm not=20
> quite sure I
> can claim to be smart enough to say that!)

The function as written is only strict in its list argument, and its
usage site only demands the 'l' argument strictly.  So unless the
compiler were to make use of the "can't fail" property of '+' on Int
(which might not even hold if overflow checking is used), the compiler
can't possibly evaluate the accumulating parameters of countAll'
strictly.

It would be possible to do strict evaluation in the case that the
suspended computation is known to take a small bounded amount of time
and space and can't fail - GHC doesn't do this, but we've wondered about
it from time to time.

I do wonder how often similar patterns crop up in practice - I've
certainly encountered this pattern in my own code several times, and
solved it using seq or strict constructor fields.

> Never fear,
> -fall-strict is here!

I had no idea this flag still worked.  As I recall, it was an experiment
that turned out to be a bad idea - you're probably just better off using
seq.

Cheers,
	Simon