haskell - haskell中的斐波那契序列返回所有值

Question

我需要帮助我使用 haskell 进行分配，它返回一个列表，直到斐波那契数列中的第 n 个数字。

像

Main> fib 5
[0,1,1,2,3,5]
Main> fib 15
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

我明白这一点

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

但我不知道如何生成包含直到第 n 个数字的所有值的列表。

谢谢

Answer 1

有一些很酷的方法可以做到这一点，首先是最简单的

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibList n = map fib [1..n]

或者我们可以将其合并为一个

fib::Int->[Int]
fib 0 = [0]
fib 1 = [1, 0]
fib n = (head (fib (n-1)) + head (fib (n-2))) : fib (n-1)

所以在这里我们只是将列表构建与递归结合起来。现在我们向疯狂迈出一步

fib n = take n fiblist
  where fiblist = 0:1:(zipWith (+) fiblist (tail fiblist))

这fiblist是斐波那契数列的无限列表。我们所做的只是抓住适当的数量。这是可能的，因为 Haskell 是“懒惰的”。如果你是 Haskell 的新手，只需微笑和点头。

最后，为了踢腿和咯咯笑

fib = flip take . fix $ \f -> 0 : 1 : (zipWith (+) f (tail f))

除了无点和固定点而不是递归之外，这与上述相同。

同样，如果您是 haskell 的新手，前 2 个更容易理解，几周后回到最后 2 个 :)