Haskell中的Fibonacci无限列表

Question

我想创建一个Fibonacci数列表.我想调用fib x,它应该给我一个列表,直到第x个元素.我如何实现这一目标.

我会像这样计算fib数:

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

如何将结果放入列表中以调用列表直到我需要的元素？

Answer 1

紧凑的定义(线性缩放)如下:

fib :: Num n => [n]
fib = 0 : nxt
    where nxt = 1 : zipWith (+) fib nxt

fibN :: Num n => Int -> [n]
fibN = flip take fib

我们这里要做的是构建一个列表fib,该列表是"cons" 0和nxt(其余列表).nxt在该where条款中定义为1的"缺点"和结果zipWith (+) fib nxt.该zipWith按元素添加的元素fib和nxt在一起,因为nxt始终是一个元素"超前"的fib,因此,我们添加了最后两个元素结合在一起.然后我们在函数中take的第一个n元素fibN.

所以我们得到一个列表:

   fib          nxt
    |            |
    v            v
+-------+    +-------+    +-------------+
|  (:)  | ,->|  (:)  | ,->|   zipWith   |
+---+---+ |  +---+---+ |  +-----+---+---+
| 0 | o---'  | 1 | o---'  | (+) | o | o |
+---+---+    +---+---+    +-----+-|-+-|-+
  ^            ^                  |   |
  |            `------------------|---'
  `-------------------------------'

如果我们这样评价到第三个元素,这意味着我们打电话zipWith,这将产生头部的总和fib,并nxt和推进这两个点,如:

   fib          nxt
    |            |
    v            v
+-------+    +-------+    +-------+    +-------------+
|  (:)  | ,->|  (:)  | ,->|  (:)  | ,->|   zipWith   |
+---+---+ |  +---+---+ |  +---+---+ |  +-----+---+---+
| 0 | o---'  | 1 | o---'  | 1 | o---'  | (+) | o | o |
+---+---+    +---+---+    +---+---+    +-----+-|-+-|-+
               ^            ^                  |   |
               |            `------------------|---'
               `-------------------------------'

等等.