Trace: Debugging Simple Factorial Function (using accumulator)

Question

So I was going through this video (see 4:07) and noticed that the function described doesn't actually properly calculate factorials (it seems to never multiply by 2). I fixed the function itself by changing n <= 1 to n <= 0 but I can't seem to figure out why the original function doesn't work.

I then decided to have my first go at Haskell debugging using trace, and the output just baffled me more. Here is the full code I'm using right now:

factorial n = auxiliaryFunction n 1
where
    auxiliaryFunction n accumulator | trace ("n:" ++ show(n) ++ " n*acc: " ++ show (n*accumulator)) False = undefined
        | n <= 1 = 1
        | otherwise = auxiliaryFunction (n-1) n*accumulator 

This outputs:

n:1 n*acc: 5
n:5 n*acc: 20
n:4 n*acc: 12
n:3 n*acc: 6
n:2 n*acc: 2

Firstly, why does n=1 get output by trace first? Shouldn't it be n=5? Interestingly, the same thing happens when using n <= 0 = 1, and the output is like this:

n:1 n*acc: 5
n:5 n*acc: 20
n:4 n*acc: 12
n:3 n*acc: 6
n:2 n*acc: 2
n:1 n*acc: 0

This seems to make a bit more sense, as that n=1 case is being evaluated after all the others (but also at the beginning?), which lets the accumulated value of 2 from the last call be properly multiplied and added to the final output of the function. Something just doesn't seem to be clicking for me.

I also feel like I'm missing something critical about how the values actually accumulate. I'm sorry if this question seems a bit like gobbledygook but I'm just confused.

Answer 1

You should return the accumulator in case n <= 1, and also put brackets like auxiliaryFunction (n-1) (n*accumulator): by writing auxiliaryFunction (n-1) n*accumulator, this is interpreted as (auxiliaryFunction (n-1) n)*accumulator.

factorial :: Integral i => i -> i
factorial n = go n 1
  where go n acc
          | n <= 1 = acc
          | otherwise = go (n-1) (n*acc)