Generating Fibonacci numbers in Haskell?

Question

In Haskell, how can I generate Fibonacci numbers based on the property that the nth Fibonacci number is equal to the (n-2)th Fibonacci number plus the (n-1)th Fibonacci number?

I've seen this:

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

I don't really understand that, or how it produces an infinite list instead of one containing 3 elements.

How would I write haskell code that works by calculating the actual definition and not by doing something really weird with list functions?

Answer 1

The picture illustrates the evaluation order of the (zipWith ...). List is haskell is a sequence of cons cells joined together, from left to right. I labelled each cons cell with alphabet a, b, c, d .. below. _ means unevaluated cells.

fibs is the first cons cell, namely a.

tail fibs is merely saying "points one cons cell to the right", so (tail fibs) is the node right to a, namely b.

As zipWith proceeds, it takes the value of the last two evaluated nodes, add them up and the result is the evaluated value of the new node. Then the process continue.

-- node a = fibs 
-- node b = (tail fibs)

1:1:(zipWith (+) (node a) (node b))

  a   b   c
  ↓   ↓   ↓
 -----------
  |   |   |
  1   1   _


1:1:2:(zipWith (+) (node b) (node c))

  a   b   c   d
  ↓   ↓   ↓   ↓
 ---------------
  |   |   |   |
  1   1   2   _


1:1:2:3:(zipWith (+) (node c) (node d))

  a   b   c   d   e
  ↓   ↓   ↓   ↓   ↓
 ------------------
  |   |   |   |   |
  1   1   2   3   _

Answer 2

I tried to reimplement this in python3. The goal was to get a similar algorithm in python which is obviously the same, but not to mimic all aspects of Haskell.

I came up with the following code.

fibs.py:

# python version of Haskell's code
#    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

from operator import add

fibsList = [1, 1]  # growing

def fibs(n):
  if n >= len(fibsList):                # lazy evaluation
    x=zipWith(n-2,add,fibs,tail(fibs))  # or: ...,fibs,tailfibs)
    fibsList.append(x)
  return fibsList[n]

def zipWith(n,op,list1,list2):
  return op(list1(n),list2(n))

def tail(list):                         # or: def tailfibs(n):
  return lambda n : list(n + 1)         #       return fibs(n+1)

# test
print (fibs(10))
print (*fibsList)

Running it will output

$ python fibs.py
89
1 1 2 3 5 8 13 21 34 55 89

This will do the same as the Haskell code, but it is a step by step version where you can add some logging

Answer 3

I was doing the homework6 of CIS194 and find that you could write this way. Computing the first n elements requires only O(n) addition operations.

fibs2 :: [Integer]
fibs2 = [0, 1] ++ [fibs2 !! (n-1) + fibs2 !! (n-2) | n <- [2..]]

Answer 4

Put in code, your definition is

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
  -- i.e.
  -- fib (n+2) = fib (n+1) + fib n

Int -> a ~= [a] because

from f = map f [0..]     -- from :: (Int -> a) -> [a]
to = (!!)                -- to :: [a] -> (Int -> a)

Thus

fibs :: [Integer]
fibs = from fib 

fibs !! 0 = 1
fibs !! 1 = 1
fibs !! (n+2)    = fibs !! (n+1)     +  fibs !! n
-- or,
drop 2 fibs !! n = drop 1 fibs !! n  +  fibs !! n
                 = zipWith (+) (tail fibs) fibs !! n
-- i.e.
take 2 fibs = [1,1]
drop 2 fibs = zipWith (+) (tail fibs) fibs
-- hence, 
fibs = take 2 fibs ++ drop 2 fibs
     = 1 : 1 : zipWith (+) (tail fibs) fibs

Or, as a, b = (0,1) : (b, a+b):

fibs :: [Integer]
fibs = a
  where
  (a,b) = unzip $ (0,1) : zip b (zipWith (+) a b)

Answer 5

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

at first, with fibs and tail fibs, we can get the 3rd element:

fibs                        : [1, 1, ?
tail fibs                   : [1, ?
zipWith (+) fibs (tail fibs): [2, ?

now, we know the 3rd is 2, we can get the 4th:

fibs                        : [1, 1, 2, ?
tail fibs                   : [1, 2, ?
zipWith (+) fibs (tail fibs): [2, 3, ?

now the 5th:

fibs                        : [1, 1, 2, 3, ?
tail fibs                   : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?

and so on ..

Answer 6

Here's a different and simpler function that calculates the n'th Fibonacci number:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

The implementation you are referring to relays on some observations about how values in Fibonacci relate to each other (and how Haskell can define data structures in terms of themselfs in effect creating infinite data structures)

The function in your question works like this:

Assume you already had an infinite list of the Fibonacci numbers:

   [ 1, 1, 2, 3, 5,  8, 13, .... ]

The tail of this list is

   [ 1, 2, 3, 5, 8, 13, 21, .... ]

zipWith combines two lists element by element using the given operator:

   [ 1, 1, 2, 3,  5,  8, 13, .... ]
+  [ 1, 2, 3, 5,  8, 13, 21, .... ]
=  [ 2, 3, 5, 8, 13, 21, 34, .... ]

So the infinite list of Fibonacci numbers can be calculated by prepending the elements 1 and 1 to the result of zipping the infinite list of Fibonacci numbers with the tail of the infinite list of Fibonacci numbers using the + operator.

Now, to get the n'th Fibonacci number, just get the n'th element of the infinite list of Fibonacci numbers:

fib n = fibs !! n

The beauty of Haskell is that it doesn't calculate any element of the list of Fibonacci numbers until its needed.

Did I make your head explode? :)

Answer 7

LOL, I love Haskell pattern matching but it is rendered useless in standard Fibonacci functions. The standard list is constructed from the right. To use pattern matching and cons, the list must be constructed from the left. Well, one consolation, at least, is this is really fast. ~O(n), it should be. A helper function is needed to reverse the infinite list (things you can only do in Haskell, joy) and this function outputs each subsequent list of the run so 'last' is also used in the helper function pipeline.

f (x:y:xs) = (x+y):(x:(y:xs))

The helper

fib n = reverse . last . take n $ iterate f [1,0]

This is a list version and, I think, it explicates how the list is constructed which is the purpose. I want to do a tuple version.

Edit 3/15/2018

First off, Will Ness enlightened me with the knowledge that an entire list being generated at each iteration was unnecessary and that only the last two values used were needed and that the values for the result list were the first values of each list or pair generated. It was so funny. After Will told me the values for the list were the first values of the lists, I ran it and saw the values 0,1,1,2,3,5,8,13 as each head of each list, I said WTF, did Will change my code on my PC? The values were there but how!? After a while, I realized they were there all along but I just didn't see them. ugh. Will's version of the function and helper function are:

f = (\(x:y:xs) -> (x+y):x:xs) -- notice, no y: put back only x+y & x

and his helper function rewrite

fib n = map head . take n $iterate f [0,1]

I think, too, that they now can be combined:

fib n = take n . map head $ iterate (\(x:y:xs) -> (x+y):x:xs) [0,1]

As an irrelevant aside, the function can be with tuples, too

fib n = take n . map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

Another form, a list comprehension form, can also be written for all:

fib n = take n [ fst t | t <- iterate (\(a,b) -> (b,a+b)) (0,1)]

These are all iterative and robust. The fastest is the map with lists at 12.23 seconds for fib 5000. The tuple comprehension was second fastest for fib 5000 at 13.58 seconds.

Answer 8

The definition of fibonaci(n) is:

fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)

The naive implementation in Haskell

fibonacci :: Integer -> Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci x = fibonacci (x-1) + fibonacci (x-2)

All formulas can be traced back to this definition, some which run very quickly, some of which run very slowly. The implementation above has O(n) = 2^n

In the spirit of your question, let me remove the use of lists and give you something that runs in O(n) I.e. let's not hold all the fibonaccis from 0 to n in a list.

If we have a triple (a tuple with three members) that looks like:

(n, fibonacci[n-1], fibonacci[n])

Remembering the initial definition, we can calculate the next triple from the last triple:

(n+1, fibonacci[n], fibonacci[n-1] + fibonacci[n]) = (n+1, fibonacci[n], fibonacci[n+1])

And the next triple from the last triple: (n+2, fibonacci[n+1], fibonacci[n] + fibonacci[n+1]) = (n+1, fibonacci[n+1], fibonacci[n+2])

And so on...

n = 0 => (0,0,1) 
n = 1 => (1,1,1) - calculated from the previous triple
n = 2 => (2,1,2) - calculated from the previous triple
n = 3 => (3,2,3) - calculated from the previous triple
n = 4 => (4,3,5) - calculated from the previous triple
n = 5 => (5,5,8) - calculated from the previous triple

Let's implement this in Haskell and use self explanatory variable names:

nextTripleIfCurrentNIsLessThanN :: (Int, Integer, Integer) -> Int -> (Int, Integer, Integer)
nextTripleIfCurrentNIsLessThanN (currentN, x, y) n = if currentN < n
then nextTripleIfCurrentNIsLessThanN (currentN + 1, y, x + y) n
else (currentN, x, y)

thirdElementOfTriple :: (x,y,z) -> z
thirdElementOfTriple (x,y,z) = z

fibonacci :: Int -> Integer
fibonacci n = thirdElementOfTriple (nextTripleIfCurrentNIsLessThanN (0,0,1) n)

This will work in O(n) [It is mildly quadratic which shows up in large numbers. The reason for that is that adding big numbers is more costly than adding small ones. But that's a separate discussion about model of computation.]

fibonacci 0
1
fibonacci 1
1
fibonacci 2
2
fibonacci 3
3
fibonacci 4
5
fibonacci 5
8
fibonacci 5000
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626

Answer 9

A lazy way of generating infinite Fibonacci series can easily be achieved by unfoldr as follows;

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)

Answer 10

using iterate

fibonaci = map fst (iterate f (0,1)) where f (x,y) = (y,x+y)

using

take 10 fibonaci

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]

Answer 11

going by the definition, every item of the fibonacci series is the sum of the previous two terms. putting this definition in to lazy haskell gives u this!

fibo a b = a:fibo b (a+b)

now just take n items from fibo starting with 0,1

take 10 (fibo 0 1)

Answer 12

To expand on dtb's answer:

There is an important difference between the "simple" solution:

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

And the one you specified:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The simple solution takes O(1.618^NN) time to compute the Nth element, while the one you specified takes O(N²). That's because the one you specified takes into account that computing fib n and fib (n-1) (which is required to compute it) share the dependency of fib (n-2), and that it can be computed once for both to save time. O(N²) is for N additions of numbers of O(N) digits.

Answer 13

There are a number of different Haskell algorithms for the Fibonacci sequence here. The "naive" implementation looks like what you're after.