# The Fibonacci sequence

### From HaskellWiki

(Difference between revisions)

DonStewart (Talk | contribs) (→With scanl) |
m (added unfoldr version, removed so-called "fix point" solution) |
||

Line 15: | Line 15: | ||

</haskell> |
</haskell> |
||

− | == With fix points == |
+ | == With scanl == |

<haskell> |
<haskell> |
||

− | fix $ \fib -> 1 : 1 : zipWith (+) fib (tail fib) |
+ | fib = fix ((1:) . scanl (+) 1) |

</haskell> |
</haskell> |
||

− | == With scanl == |
+ | == With unfoldr == |

<haskell> |
<haskell> |
||

− | fib = fix ((1:) . scanl (+) 1) |
+ | unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1) |

</haskell> |
</haskell> |
||

## Revision as of 22:49, 20 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 scanl

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

## 4 With unfoldr

unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,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)