Personal tools

The Fibonacci sequence

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
Line 29: Line 29:
 
== A fairly fast version, using some identities ==
 
== A fairly fast version, using some identities ==
   
  +
<haskell>
 
fib 0 = 0
 
fib 0 = 0
 
fib 1 = 1
 
fib 1 = 1
Line 37: Line 38:
 
f1 = fib k
 
f1 = fib k
 
f2 = fib (k-1)
 
f2 = fib (k-1)
  +
</haskell>
   
 
== Fastest Fib in the West ==
 
== Fastest Fib in the West ==

Revision as of 18:12, 12 March 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 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)

7 See also

Discussion at haskell cafe:

http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623