CODEWITHSUNDEEP
listhaskelllist-comprehensionfibonacci
CoreNoob
CoreNoob

Reputation: 115

Fibonacci infinite list in Haskell

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?

Upvotes: 1

Views: 3725

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476537

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.

Upvotes: 8

Probie
Probie

Reputation: 1361

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..])

Upvotes: 3

Related Questions