The Fibonacci sequence
Revision as of 22:49, 20 December 2006 by JohannesAhlmann (talk | contribs) (added unfoldr version, removed so-called "fix point" solution)
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)
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)