haskell - 是否可以以不同的方式编写与 "textbook"一样快的阶乘函数？

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 进行优化。特别是，product uses foldl :

product = foldl (*) 1

当应用于 [1..n] (这只是 1 `enumFromTo` n )它受 fusion 的约束.简而言之，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 .