tail recursion - Accumulators in haskell

Question

In Haskell, if I write

 fac n = facRec n 1
   where facRec 0 acc = acc
         facRec n acc = facRec (n-1) (acc*n)

and compile it with GHC, will the result be any different than if I used

 fac 0 = 1
 fac n = n * fac (n-1)

I could easily do fac n = product [1..n] and avoid the whole thing, but I'm interested in how an attempt at tail recursion works out in a lazy language. I get that I can still get a stack overflow because thunks are building up, but does anything actually happen differently (in terms of the resulting compiled program) when I use an accumulator than when I just state the naive recursion? Is there any benefit to leaving out the tail recursion other than improved legibility? Does the answer change at all if I'm using runhaskell to run the computation instead of compiling it first?

Answer 1

Tail recursion does make sense in (GHC) Haskell if your accumulator is strict. To demonstrate the problem, here is a "trace" of your tail-recursive definition of fac:

   fac 4
~> facRec 4 1
~> facRec 3 (1*4)
~> facRec 2 ((1*4)*3)
~> facRec 1 (((1*4)*3)*2)
~> facRec 0 ((((1*4)*3)*2)*1)
~> (((1*4)*3)*2) * 1
  ~> ((1*4)*3) * 2
    ~> (1*4) * 3
      ~> 1*4
    ~> 4 * 3
  ~> 12 * 2
~> 24 * 1
~> 24

The indentation level corresponds (roughly) to stack level. Note that the accumulator is only evaluated at the very end, and that may cause a stack overflow. The trick, of course, is to make the accumulator strict. It's theoretically possible to show that facRec is strict if it is called in a strict context, but I am not aware of any compiler that does that, ATM. GHC does do tail call optimisation, though, so the facRec calls use constant stack space.

For the same reason foldl' is usually preferred over foldl, since the former is strict in the accumulator.

Regarding your second part, runhaskell/runghc is just a wrapper over GHCi. If GHCi finds compiled code it will use that, otherwise it will use the bytecode interpreter which performs few optimisations, so don't expect any fancy optimisations to happen.