Isn't this tail recursive?

[Jay Cox]

On 10 Mar 2002, Jyrinx wrote:

> In the case expression at the end of countAll, each of the values looks
> to me like a recursive tail call - I should think (hope?) 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 whines about a
> stack overflow.

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 quite sure I
can claim to be smart enough to say that!)

One way you could fix it up would be to do as Hal did and sprinkle
seq and/or $! throughout your code.  That would have been my solution as
well, but I then realized this happens just too often to have been
ignored by the haskell literati. I decided to muck around in the
haskell manual and I think I may have found another way.

Never fear,
-fall-strict is here!

Anyway compiling with that ghc option seams to make the problem go
away.  I just ran your code compiled with it over a 47M file and
the heap size hits a max of 16 and stays constant throughout execution.

I wish I knew more about what -fall-strict really means.  The ghc 5.00
manual hardly explains it.  It doesn't have the semantics I would have
thought it should have.  for instance:

main = print foo
  where foo = let a = error "do I happen?"
                  b = 3
              in "foo" ++ show b

I would have thought that the execution of that code compiled with the
all-strict flag would have raised the error.  a strict language would do
that, right?   Perhaps it is something to do purely with function
application.  I dont know.

Anyway, I guess a fix would be to put in a pragma into your code
to quote Malcolm Wallace <Malcolm.Wallace@cs.york.ac.uk>

>ghc and nhc98 already support this.  ghc's mechanism is
>    {-# OPTIONS -fglasgow-exts ... etc #-}
>at the top of the file - but there are quite a few restrictions on
>what flags are accepted in that pragma.  nhc98's mechanism is
>    {-# OPTIONS_COMPILE -nkpat ... etc #-}
>anywhere in the file, which has no restrictions on the options it
>accepts - you can use anything that can appear on the commandline.

o just maybe you could exchange -fall-strict for -fglasgow-exts and pray
to the haskell gods that it happens to be an acceptable option?


Jay Cox