Personal tools

The Fibonacci sequence

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(→Canonical zipWith implementation)
(→With scanl)
Line 13: Line 13:
<haskell>
<haskell>
fib = 1 : 1 : zipWith (+) fib (tail fib)
fib = 1 : 1 : zipWith (+) fib (tail fib)
 +
</haskell>
 +
 +
== With fix points ==
 +
 +
<haskell>
 +
fix $ \fib -> 1 : 1 : zipWith (+) fib (tail fib)
</haskell>
</haskell>

Revision as of 05:22, 15 December 2006

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 fix points 

fix $ \fib -> 1 : 1 : zipWith (+) fib (tail fib)

4 With scanl 

fib = fix ((1:) . scanl (+) 1)

5 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)
Retrieved from "http://www.haskell.org/haskellwiki/The_Fibonacci_sequence"

Category: Code