Haskell 中的无限惰性阶乘

Question

以与斐波那契数列类似的方式可以如下生成，

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

如何定义阶乘的级数。

更新

令人尴尬的是，在添加这个问题之前就尝试过这个，

Prelude> let factorial = 2 : 6 : zipWith(*) factorial (tail factorial)
Prelude> take 5 factorial
[2,6,12,72,864]

事实上，从一开始，尾部的数字就不是连续的值。

Answer 1

让我们退后一步，记住这个懒惰版本实际上来自哪里：

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

我们也可以类似地定义阶乘：

factorial 0 = 1
factorial n = factorial (n - 1) * n

如你所见，我们的压缩操作实际上是

(*)

，第二个列表不会是

factorials

的子列表，而是带有适当的

[x..]

的

：

factorials = 1 : zipWith (*) factorials [x..]

应该是什么值？嗯，第二个元素应该是

1 = 1 * 1

，所以它是

，自然是：

factorials = 1 : zipWith (*) factorials [1..]

请注意，我们只需要给出第一个元素，因为我们不使用

tail

或类似的东西。正如您所看到的，您的尝试几乎是正确的。您只是在左侧使用了错误的值：

Prelude> let factorial = 2 : 6 : zipWith (*) [4..] (tail factorial)
Prelude> take 10 $ factorial
[2,6,24,120,720,5040,40320,362880,3628800,39916800]

备注：阶乘序列为 0!, 1!, 2!, ...，因此如果您想符合 OEIS 标准，请从

[1,1,...]

开始。

Answer 2

阶乘惰性列表的惯用定义根本不是递归的：而是使用 Prelude 函数 scanl。

factorials = scanl (*) 1 [1..]

Answer 3

给出

factorial

的通常定义：

factorial :: Integer -> Integer 
factorial 0 = 1
factorial i = foldr (*) 1 [2..i]

我们可以通过简单地在所有正数的无限列表上运行

factorial

函数来生成所有阶乘的无限列表：

inFact :: [Integer]
inFact = map factorial [0..]

Answer 4

factorials = helper [1..]

helper (x:xs) = x : help ([x * (head xs)] ++ (tail xs))