Бесконечный список Фибоначчи в Хаскеле

Question

Я хочу создать список чисел Фибоначчи. Я хочу вызвать fib x, и он должен дать мне список до x-го элемента. Как мне этого добиться.

Я бы вычислил числа фиби так:

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, который является «минусами» из 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 |
+---+---+    +---+---+    +---+---+    +-----+-|-+-|-+
               ^            ^                  |   |
               |            `------------------|---'
               `-------------------------------'

и т. Д.

Answer 2

Не быстрый способ (потому что ваша функция работает в экспоненциальном времени), но с использованием вашей функции fib

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