Wednesday, November 11, 2009

An elegant Fibonacci solution with Haskell

Here's a very elegant Fibonacci solution I found in Simon Thompson's book, The Craft of Functional Programming:

--Given a tuple with a fibonacci pair, this function returns another tuple with
--the next two numbers in the sequence
fibStep :: (Int, Int) -> (Int, Int)
fibStep (u,v) = (v, u + v)

--The Definition for the Fibonacci pair
fibPair :: Int -> (Int, Int)
fibPair n
| n == 0 = (0,1)
| otherwise = fibStep (fibPair (n - 1))

--Pass the output of the fibPair function to Haskell's fst function,
--which returns the first item in the given tuple
fastFib :: Int -> Int
fastFib = fst . fibPair