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个:)