The Fibonacci sequence
Revision as of 18:12, 12 March 2007 by CaleGibbard (talk | contribs)
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Implementing the fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
Naive solution
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Canonical zipWith implementation
fib = 1 : 1 : zipWith (+) fib (tail fib)
With scanl
fib = fix ((1:) . scanl (+) 1)
With unfoldr
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
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)
Fastest Fib in the West
This was contributed by wli
import System.Environment
import Data.List
fib 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))
main = getArgs >>= mapM_ (print . fib . read)
See also
Discussion at haskell cafe:
http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623