Fibonacci numbers (Haskell)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Erlang | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by


 F(n) =
 \begin{cases}
   0             & n = 0 \\
   1             & n = 1 \\
   F(n-1)+F(n-2) & n > 1 \\
  \end{cases} .

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.


[edit] Recursion

A recursive implementation that calculates the nth Fibonacci number can be written remarkably close to the mathematical definition:

<<fibonacci.hs>>=
fib :: Integer -> Integer
fib n
    | n == 0  = 0
    | n == 1  = 1
    | n > 1   = fib (n-1) + fib (n-2)

[edit] Infinite Lists

The recursive definition is elegant but inefficient since for each call of fib with n > 1 we are recalculating Fibonacci numbers that had already been calculated before. Another issue is the stack, fib is not tail recursive and so we risk a stack overflow.

We can utilize Haskell's laziness and define our Fibonacci numbers as an infinite lazy list. This is less readable, but takes only linear time.

<<fibonacci.hs>>=
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fastfib n = fibs !! n

where zipWith is a function defined in the Haskell prelude which builds a new list by taking the head element of each list and applying a function (here +) to them. For example:

*Main> zipWith (+) [0,1,2] [3, 4, 5] 
[3,5,7]

As the list is being calculated, zipWith unfolds as follows:

0 : 1 : zipWith (+) (0 : 1 : ...) (1 : ...)
0 : 1 : (0 + 1) : zipWith (+) (1 : 1 : ...) (1 : ...)
0 : 1 : 1 : (1 + 1) : zipWith (+) (1 : 2 : ...) (2 : ...)
0 : 1 : 1 : 2 : (1 + 2) : zipWith (+) (2 : 3 : ...) (3 : ...)

You can compare the speed yourself if you calculate the 25th Fibonacci number at the Haskell interactive prompt using fib and fastfib. fib will take some time while fastfib will give you the result instantly.

Download code
hijacker
hijacker
hijacker
hijacker