Haskell 中的斐波那契无限列表

Question

我想创建一个斐波那契数列。我想调用 fib x，它应该给我一个列表，直到第 x 个元素。我该如何实现。

我会这样计算 fib 数：

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

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

Answer 1

不是一个快速的方法（因为你的函数以指数时间运行），但使用你的函数 fib

nfibs :: Int -> [Integer]
nfibs n = take n (map fib [0..])

Answer 2

紧凑的定义（线性缩放）如下：

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

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

我们在这里做的是构建一个列表 fib，它是 0 和 nxt（列表的其余部分）的 "cons"。 nxt 在 where 子句中定义为 "cons" 的 1 和 zipWith (+) fib nxt 的结果。 zipWith 按元素将 fib 和 nxt 的元素相加，因为 nxt 始终是 fib 的一个元素 "ahead"，因此我们添加最后两个元素在一起。然后我们 take fibN 函数中的前 n 个元素。

所以我们得到了一个列表：

   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 |
+---+---+    +---+---+    +---+---+    +-----+-|-+-|-+
               ^            ^                  |   |
               |            `------------------|---'
               `-------------------------------'

等等。

Haskell 中的斐波那契无限列表

Fibonacci infinite list in Haskell

haskell

list-comprehension

list

fibonacci