是否有可能以不同的方式编写与"教科书"一样快的阶乘函数？

Question

我认为这是Haskell中阶乘函数的一般形式:

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

我知道这是最优雅的方式,但是当我编写自己的递归函数时,它会明显变慢:

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

第一个解决方案不是必须在内部完成第一个解决方案所做的一切吗？怎么这么快？是否有可能在不使用花式列表符号或产品功能的情况下编写与第一个解决方案一样快的内容？

Answer 1

第一个版本比第二个版本更容易进行GHC优化.特别是产品用途foldl:

product = foldl (*) 1

当应用于[1..n](只是1 `enumFromTo` n)时,它会融合.简而言之,GHC精心设计了重写规则,旨在优化远离中间数据结构的代码片段(在这种情况下factorial,foldl (*) 1消费者和1 `enumFromTo` n生产者).

请注意,您可以执行GHC所做的(factorial = foldl (*) 1 . enumFromTo 1)并获得相同的性能.

此外,你的第二个功能甚至不是尾递归.通过传递累加器,你可以很容易地解决这个问题:

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

与此相辅相成的是,对于大多数数字类型,您都希望算术是严格的.这归结于添加BangPatterns至n和m.