The Fibonacci sequence
From HaskellWiki
(Difference between revisions)
(Another fast fib) |
(→See also) |
||
| Line 81: | Line 81: | ||
== See also == | == See also == | ||
| - | + | * [http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 Discussion at haskell cafe] | |
| - | + | * [http://www.cubbi.org/serious/fibonacci/haskell.html Some other nice solutions] | |
| - | http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 | + | |
[[Category:Code]] | [[Category:Code]] | ||
Revision as of 12:35, 7 May 2007
Implementing the fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
Contents |
1 Naive solution
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
2 Canonical zipWith implementation
fib = 1 : 1 : zipWith (+) fib (tail fib)
3 With scanl
fib = fix ((1:) . scanl (+) 1)
4 With unfoldr
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
5 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)
6 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
7 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)
