Haskell 中的内置阶乘函数

Question

我知道这听起来像是一个愚蠢的问题，但问题是：Haskell 中有内置阶乘吗？

Google 为我提供了有关 Haskell 的教程，解释了我如何自己实现它，但我在 Hoogle 上找不到任何内容。我不想每次需要的时候都重写它。

我可以使用

product [1..n]

作为替代品，但是有真正的

Int -> Int

阶乘内置函数吗？

Answer 1

尽管阶乘函数在示例中很常用，但在实践中并不是那么有用。数字增长得非常快，大多数包含阶乘函数的问题都可以（并且应该）以更有效的方式计算。

一个简单的例子是计算二项式系数。虽然可以将它们定义为

choose n k = factorial n `div` (factorial k * factorial (n-k))

不使用阶乘会更有效：

choose n 0 = 1
choose 0 k = 0
choose n k = choose (n-1) (k-1) * n `div` k 

所以，不，它不包含在标准前奏中。斐波那契数列、阿克曼函数或许多其他函数虽然理论上很有趣，但在实践中使用得不够普遍，不足以在标准库中占有一席之地。

话虽如此，Hackage 上有许多数学库可用。

Answer 2

据我所知，Hackage 中阶乘的最佳实现是

Math.Combinatorics.Exact.Factorial.factorial

包中的

exact-combinatorics

。它使用比

product [1..n]

渐近更快的算法。

http://hackage.haskell.org/package/exact-combinatorics

Answer 3

不，但你可以轻松地写一个。如果您担心每次需要时都必须重写该函数，那么您始终可以将其编写为模块或库的一部分（取决于您想要实现的程度，以及您拥有多少其他类似函数）。这样您只需要编写一次，并可以在需要时快速将其拉入任何其他项目。

Answer 4

试试哈尤！搜索（hackage 顶部的链接）；例如，它想出了这个

http://hackage.haskell.org/packages/archive/statistics/latest/doc/html/Statistics-Math.html#v:factorial

Answer 5

fac = product . flip take [1..]

Answer 6

您拥有标准前奏中的

product

功能。与范围相结合，您可以轻松获得阶乘函数。

factorial n = product [n, n-1 .. 1]
nCr n r = n' `div` r'
    where
    -- unroll just what you need and nothing more
    n' = product [n, n-1 .. n-r+1]
    r' = factorial r

Answer 7

fact n = if n == 0 then 1 else n * fact(n-1)
fact n = foldl(*) 1 [1..n]
fact n = product [1..n]

您可以选择其中一个

Answer 8

如果您正在寻找 lambda 表达式，那么您始终可以使用经典的

fix (\f x -> if x == 0 then 1 else x * (f (x - 1)))

。

Answer 9

因为我没有足够的声誉来评论@hammar 答案。请注意，div 函数是取整除法，因此它会截断商的小数部分，这可能会导致问题，正确的除法函数应该是 (/)

choose n 0 = 1
choose 0 k = 0
choose n k = choose (n-1) (k-1) * n / k 

示例：

choose 3 2 = 2 (with the original implementation) instead of 3
(3 div 2) * (2 div 1) * 1 (base case) = 1 * 2 * 1 = 2

希望这能帮助人们节省时间。