Difference between revisions of "The Fibonacci sequence"
From HaskellWiki
(Another fast fib) 
DonStewart (talk  contribs) (→See also) 

Line 81:  Line 81:  
== See also == 
== See also == 

−  Discussion at haskell cafe 
+  * [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
Naive solution
fib 0 = 0
fib 1 = 1
fib n = fib (n1) + fib (n2)
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 (k1)
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
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*fg))
main = getArgs >>= mapM_ (print . fib . read)