# Fibonacci Sequence in Haskell

I have finished the first 5 chapters in “Learn You a Haskell for Great Good!”. I enjoy learning Haskell. Let’s look at a couple of implementations of the 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`fibSlow`

is 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 `fibFast 1000`

.

```
ghci> fibFast 1000
817770325994397771
```

I glossed over how `zipWith`

and `!!`

works, so let’s look at some examples of their usage.

#### !! Examples

```
ghci> [1,2,3] !! 1
2
ghci> [1,2,3] !! 0
1
```

#### zipWith Examples

```
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.