Create a simple function in Haskell to generate the Fibonacci series.

(Based on a class taught by a teacher of mine.)

Haskell is a ** purely functional**
programming language.

There are no statements. Only expressions. For a discussion about the difference between the two, see here.

This means a function cannot change the value of any of its parameters. They can only return values.

There are ** no side effects**. Each
expression is sort of self-contained. Whatever happens in an expression
cannot affect other unrelated expressions.

So it's possible, and often helpful, to think of a Haskell program as simply a set of equations.

(No wonder mathematicians like functional programming languages like Haskell :D)

We can 'store equations' into variables in a sense. This is possible Haskell does lazy evaluation. The equation won't be evaluated till it is needed.

Let's see a few built-in functions in Haskell which can help us in our venture.

`zipWith`

```
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
```

Combines two lists by applying a function to their elements position-wise. The size of the resultant list is min(len(list1, list2)).

Examples:

```
> zipWith (+) [1,2,3] [1,2]
[2,4]
> zipWith (*) [2,3] [4,5,6]
[8,15]
> zipWith (*) [2,3,4] [5,6,7,8]
[10,18,28]
> zipWith (-) [2,3,4] [5,6,7,8]
[-3,-3,-3]
```

`tail`

```
tail :: [a] -> [a]
```

Returns everything except the first element of a list.

Passing an empty list to `tail`

would cause exception.

```
> tail []
*** Exception: tail: empty list
> tail [1]
[]
> tail [1,2,3,4]
[2,3,4]
```

`take`

```
take :: Int -> [a] -> [a]
```

Accepts an integer (`n`

) along with a list and returns the
first `n`

elements of the list.

```
> take 2 [1,2,3,4]
[1,2]
> take 3 [1,2,3,4]
[1,2,3]
> take 10 [1..100]
[1,2,3,4,5,6,7,8,9,10]
```

Now that we have seen the built-in Haskell functions we'll use, let's make the Fibonacci series.

The 'equation' for the Fibonacci series may be written as:

```
fibo = 1 : 1 : zipWith (+) fibo (tail fibo)
```

Here, a list is being made. The first two elements are explicitly
given (`1`

and `1`

) and the remaining elements are
found based on that.

The `zipWith (+) fibo (tail fibo)`

part basically takes
two 'copies' (not really copies) of `fibo`

, removes the first
element from one of them with `tail fibo`

and adds elements
of `fibo`

and `tail fibo`

position-wise.

The result is the list of Fibonacci numbers.

It works something like this:

```
fibo : 1 1 ... | 1 1 2 ... | 1 1 2 3 ... | 1 1 2 3 5 ...
tail fibo: 1 ... | 1 2 ... | 1 2 3 ... | 1 2 3 5 ...
--------- → ---------- → ------------ → --------------
zipWith : 2 | 2 3 | 2 3 5 | 2 3 5 8
```

`fibo`

denotes the infinite list of Fibonacci numbers. But
thanks to lazy evaluation, its expansion is done only to the extent that
is asked for.

Getting the first 10 Fibonacci numbers is as easy doing:

```
> take 10 fibo
[1,1,2,3,5,8,13,21,34,55]
```

And we can use list indexing syntax of Haskell (ie, `!!`

)
to get the `i`

-th Fibonacci number.

```
fibo !! i
```

where indexing starts from zero.

```
> fibo !! 3
3
> fibo !! 13
377
> fibo !! 15
987
> fibo !! 150
16130531424904581415797907386349
```

Neat, isn't it? And this is basically just a single-line program!

- http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
- https://www.haskellforall.com/2013/07/statements-vs-expressions.html
- https://wiki.haskell.org/Functional_programming
- https://hackage.haskell.org/package/base-4.15.0.0/docs/Data-List.html#g:16
- https://wiki.haskell.org/Lazy_evaluation
- https://www.haskell.org/
- https://en.wikipedia.org/wiki/List_of_programming_languages_by_type#Pure