Fibonacci numbers (Haskell)
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)
 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
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 will take some time while
fastfib will give you the result instantly.