The Fibonacci sequence
From HaskellWiki
Implementing the Fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
Contents |
1 Naive definition
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
2 Linear-time implementations
One can compute the first n Fibonacci numbers with O(n) additions.
Iffibs
fib n = fibs!!n
2.1 Canonical zipWith implementation
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
2.2 With scanl
fibs = fix ((0:) . scanl (+) 1)
2.3 With unfoldr
fibs = unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
2.4 With iterate
fibs = map fst $ iterate (\(f1,f2) -> (f2,f1+f2)) (0,1)
3 Log-time implementations
3.1 Using 2x2 matrices
The argument ofiterate
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.
3.2 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)
3.3 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
3.4 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))
