# Difference between revisions of "The Fibonacci sequence"

From HaskellWiki

CaleGibbard (talk | contribs) |
(Another fast fib) |
||

Line 38: | Line 38: | ||

f1 = fib k |
f1 = fib k |
||

f2 = fib (k-1) |
f2 = fib (k-1) |
||

+ | </haskell> |
||

+ | |||

+ | == Another fast fib == |
||

+ | |||

+ | <haskell> |
||

+ | 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 |
||

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

## Revision as of 21:54, 12 March 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 (n-1) + fib (n-2)
```

## 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 (k-1)
```

## 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*f-g))
main = getArgs >>= mapM_ (print . fib . read)
```

## See also

Discussion at haskell cafe:

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