11

I see this as the general form of a factorial function in Haskell:

factorial :: (Integral a) => a -> a
factorial n = product [1..n]

I understand this is the most elegant way, but when I write my own recursive function to do it, it's significantly slower:

factorial :: (Integral a) => a -> a
factorial 1 = 1
factorial n = n * factorial (n - 1)

Doesn't the first solution have to do pretty much everything that the first one does, internally? How is it so much faster? Is it possible to write something as fast as the first solution without using the fancy list notation or the product function?

Alexis King
  • 43,109
  • 15
  • 131
  • 205
markasoftware
  • 12,292
  • 8
  • 41
  • 69

2 Answers2

10

The first version is easier for GHC to optimize than the second one. In particular, product uses foldl:

product = foldl (*) 1

and when applied to [1..n] (which is just 1 `enumFromTo` n) it is subject to fusion. In short, GHC has carefully crafted re-write rules that are meant to optimize away intermediate data structures from pieces of code where the lists created are immediately consumed (in the case of factorial, foldl (*) 1 is the consumer and 1 `enumFromTo` n the producer).

Note that you can do what GHC does (factorial = foldl (*) 1 . enumFromTo 1) and get the same performance.

Also, your second function isn't even tail recursive. That part you could fix pretty easily by passing in an accumulator:

factorial :: (Integral a) => a -> a
factorial n = go n 1
  where
    go 0 m = m
    go n m = go (n-1) (n*m)

Hand in hand with this, is the fact that for most numeric types you will want the arithmetic to be strict. That boils down to adding BangPatterns to n and m.

Community
  • 1
  • 1
Alec
  • 31,829
  • 7
  • 67
  • 114
  • 2
    Fusion, while important, is much *less* important in this case than the combination of tail-call optimization and strictness analysis. Fusion probably makes it several times faster, but the others keep it from blowing up altogether. Using `foldl'` avoids such heavy reliance on strictness analysis. – dfeuer Nov 08 '16 at 06:59
  • @dfeuer I agree, but OP is looking for a reason why the `product` version is faster. The tail-call optimization is a blessing to the other version, and strictness analysis applies to both variants. That leaves fusion as the main strength of the `foldl` version. – Alec Nov 08 '16 at 07:20
  • 1
    Their recursive version is not tail recursive. Compare the speed of their recursive version to the faster version with a non-fusing product: `{-# NOINLINE product_ni #-} product_ni :: [Integer] -> Integer; product_ni = product`. – dfeuer Nov 08 '16 at 07:39
  • @dfeuer Oh wow yeah - for some reason I had it in my head that they were using an accumulator version. The non-tail recursive-ness is indeed a big deal. – Alec Nov 08 '16 at 07:41
2

Maybe something like that:

f n = foldl (*) 1 [1..n]

You can change foldl on foldr or foldl' it will change speed

Alex Aparin
  • 4,393
  • 5
  • 25
  • 51