The Fibonacci sequence
Jump to navigation
Jump to search
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)
See also
Discussion at haskell cafe:
http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623