Fibonacci Sequence in Haskell
Fibonacci Function - Slow but Easy
fibSlow :: Int -> Int fibSlow 0 = 0 fibSlow 1 = 1 fibSlow n = fibSlow (n - 1) + fibSlow (n - 2)
Let’s look at this example line by line.
fibSlow :: Int -> Int- Function declaration. This declares the name of the function and the input/output types.
fibSlow 0 = 0- Haskell has powerful pattern matching. This line says when
fibSlowis called with a zero return a zero.
fibSlow 1 = 1- Same as line 2, but when we see 1 we will return 1.
fibSlow n = fibSlow (n - 1) + fibSlow (n - 2)- Recursively define how to find fibonacci numbers bigger than 1.
This is an easy way to define a Fibonacci function, but it isn’t very efficent. I tried calculating
fibSlow 1000 and I got tired of waiting for it to finish.
Fibonacci Function - Fast but Harder
fibFast :: Int -> Int fibFast n = let fib = 0:1:zipWith (+) fib (tail fib) in fib!!n
Let’s take this example line by line.
fibFast :: Int -> Int- Function declaration just like the first example.
fibFast n =- Start of the function definition. Nothing really to see here.
let fib = 0:1:zipWith (+) fib (tail fib)- This is the meat of the function. It basically defines a lazy fibonacci sequence that starts at zero and goes on forever. This line is also a great example of the laziness of Haskell. This stackoverflow post gives a great explanation of how this works in Haskell.
in fib!!n- Given the fibonacci sequence defined on line 3, get the nth item out of that sequence.
This function is much faster than the first. Here is my calculation of
ghci> fibFast 1000 817770325994397771
I glossed over how
!! works, so let’s look at some examples of their usage.
ghci> [1,2,3] !! 1 2 ghci> [1,2,3] !! 0 1
ghci> zipWith (+) [0,1,1] [1,1,2] [1,2,3] ghci> zipWith (-) [1,1,2] [0,1,1] [1,0,1]
I am sure I will look back at this post in a few months and think I really didn’t understand Haskell, but I feel like writing about it is starting to put me on the right path.