# Implement Fibonacci with iterate

I implemented the Fibonacci sequence using iterate.

import Data.List

fib :: Int -> Maybe Int
fib n
| n < 0     = Nothing
| otherwise = (fmap (snd . fst)) $find (\(_,i) -> n == i) (zip res [0..]) res :: [(Int, Int)] res = iterate f (0,1) f :: (Num a, Num b) => (a, a) -> (a, a) f (x, y) = (y,x+y)  Testing > fib (-1) Nothing > fib 0 Just 1 > fib 2 Just 2 > fib 3 Just 3 > fib 4 Just 5 > fib 5 Just 8 > fib 6 Just 13  Please review it. ## 1 Answer In my opinion, Maybe is too cumbersome here. I'd consider fib (-1) to be ill-defined, and I'd let it just crash with an error. By your convention, the Fibonacci sequence is 1, 2, 3, 5, 8, 13, … I would prefer to see it start earlier, such that fib 0 is 0: 0, 1, 1, 2, 3, 5, 8, 13, …. The outputs can get pretty big. I suggest using Integer instead of Int. You're using a very convoluted way to extract the nth item from a list. ## Suggested solution import Data.List (iterate) fib :: Int -> Integer fib n = fst$ sequence !! n
where
sequence = iterate (\(x, y) -> (y, x + y)) (0, 1)


You could also use the point-free style:

fib :: Int -> Integer
fib = (!!) $map fst$ iterate (\(x, y) -> (y, x + y)) (0, 1)


For that matter, you could just define the infinite sequence

fibonacciSequence = map fst \$ iterate (\(x, y) -> (y, x + y)) (0, 1)


… and let the caller do whatever they want with it, including extracting specific entries using !!.

### Behaviour

*Main> fib (-1)
*** Exception: Prelude.!!: negative index
*Main> fib 0
0
*Main> fib 1
1
*Main> fib 2
1
*Main> fib 3
2
*Main> fib 4
3
*Main> fib 5
5