The Fibonacci sequence
Implementing the Fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
- 1 Naive definition
- 2 Linear operation implementations
- 3 Logarithmic operation implementations
- 4 Constant-time implementations
- 5 See also
The standard definition can be expressed directly:
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
This implementation requires O(fib n) additions.
Linear operation implementations
A fairly fast version, using some identities
fib 0 = 0 fib 1 = 1 fib n | even n = f1 * (f1 + 2 * f2) | n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2 | otherwise = (2 * f1 + f2) * (2 * f1 - f2) - 2 where k = n `div` 2 f1 = fib k f2 = fib (k-1)
Using the infinite list of Fibonacci numbers
One can compute the first n Fibonacci numbers with O(n) additions.
fibs is the infinite list of Fibonacci numbers, one can define
fib n = fibs!!n
Canonical zipWith implementation
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = scanl (+) 0 (1:fibs) fibs = 0 : scanl (+) 0 fibs
The recursion can be replaced with
fibs = fix (scanl (+) 0 . (1:)) fibs = fix ((0:) . scanl (+) 1)
fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)
fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)
Logarithmic operation implementations
Using 2x2 matrices
The argument of
iterate above is a linear transformation,
so we can represent it as matrix and compute the nth power of this matrix with O(log n) multiplications and additions.
For example, using the simple matrix implementation in Prelude extensions,
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])
This technique works for any linear recurrence.
Another fast fib
fib = fst . fib2 -- | Return (fib n, fib (n + 1)) fib2 0 = (1, 1) fib2 1 = (1, 2) fib2 n | even n = (a*a + b*b, c*c - a*a) | otherwise = (c*c - a*a, b*b + c*c) where (a,b) = fib2 (n `div` 2 - 1) c = a + b
Fastest Fib in the West
This was contributed by wli (It assumes that the sequence starts with 1.)
import Data.List fib1 n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n where unfoldl f x = case f x of Nothing ->  Just (u, v) -> unfoldl f v ++ [u] divs 0 = Nothing divs k = Just (uncurry (flip (,)) (k `divMod` 2)) fib' (f, g) p | p = (f*(f+2*g), f^2 + g^2) | otherwise = (f^2+g^2, g*(2*f-g))
An even faster version, given later by wli on the IRC channel.
import Data.List import Data.Bits fib :: Int -> Integer fib n = snd . foldl' fib' (1, 0) $ dropWhile not $ [testBit n k | k <- let s = bitSize n in [s-1,s-2..0]] where fib' (f, g) p | p = (f*(f+2*g), ss) | otherwise = (ss, g*(2*f-g)) where ss = f*f+g*g
The Fibonacci numbers can be computed in constant time using Binet's formula. However, that only works well within the range of floating-point numbers available on your platform. Implementing Binet's formula in such a way that it computes exact results for all integers generally doesn't result in a terribly efficient implementation when compared to the programs above which use a logarithmic number of operations (and work in linear time).
Using Binet's formula
fib n = round $ phi ** fromIntegral n / sq5 where sq5 = sqrt 5 :: Double phi = (1 + sq5) / 2
- Naive parallel, multicore version
- Fibonacci primes in parallel
- Discussion at haskell cafe
- Some other nice solutions
- In Project Euler, some of the problems involve Fibonacci numbers. There are some solutions in Haskell (Spoiler Warning: Do not look at solutions to Project Euler problems until you have solved the problems on your own.):