Fibonacci infinite list in Haskell

Question

I want to create a list of Fibonacci numbers. I want to call fib x and it should give me a list till the xth element. How do I achieve that.

I would calculate fib numbers like this:

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

How do I put the result in a list to call the list till the element I need?

The above is not an efficient implementation, it will run in exponential time. — Willem Van Onsem, Apr 30 '18 at 13:19
like [this](https://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized). — Will Ness, Apr 30 '18 at 19:03

Willem Van Onsem · Accepted Answer · 2018-04-30T14:20:36.320

A compact definition (that scales linear) is the following:

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

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

What we here do is constructing a list fib that is "cons" of 0 and nxt (the rest of the lists). nxt is defined in the where clause as a "cons" of 1 and and the result of zipWith (+) fib nxt. The zipWith elementwise adds the elements of fib and nxt together, since nxt is always one element "ahead" of fib, we thus add the two last elements together. We then take the first n elements in the fibN function.

So we obtain a list like:

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

In case we thus evaluate up to the third element, this means that we call zipWith, and this will produce the sum of the head of fib and nxt and advance both points, like:

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

and so on.

Thank you for your example. The graphic is also a very good help. I ask myself how did you do that graphic? :D Do you have a program to help you create such kind of graphics or did you do it yourself? — CoreNoob, Apr 30 '18 at 13:38

Probie · Answer 2 · 2018-04-30T13:22:44.680

3

Not a fast way (because your function runs in exponential time), but using your function fib

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

edited Apr 30 '18 at 13:22

answered Apr 30 '18 at 13:21

Probie

1,371
7
15

You can drop the `Int ->` part of the signature :) – Willem Van Onsem Apr 30 '18 at 13:22
No, I just forgot to include it on the LHS (he wants up to the nth element) – Probie Apr 30 '18 at 13:23
2

`take` + an infinite list is very modular, but when it's this local, I'd just do the rewrite to `map fib [0..n-1]`, personally. – Daniel Wagner Apr 30 '18 at 13:36
You're right, but I think this has more utility as a pedagogical example. Perhaps moving `map fib [0..]` to a `where` clause would have made that clearer? – Probie Apr 30 '18 at 13:44

Fibonacci infinite list in Haskell

2 Answers2