wei2912/intro.lhs

## intro.lhs
# Shifted this file to my blog

The new link is on my blog: https://wei2912.github.io/index.html#introduction_to_haskell

I'll update the post on my blog from now on.

---

Introduction to Haskell
---

This document is in Literate Haskell. This means that you can download and run this file with `ghci intro.lhs`, and be able to run the functions defined in this file.

Haskell is a pure functional programming language that comes with lazy evaluation (in GHC, that is). Its elegance is why many programmers like writing code in Haskell. In this document, I'll give a couple of examples.

This document assumes that the reader has at least an intermediate knowledge in an imperative programming language, but does not assume knowledge of functional programming.

Also, this document is not intended to teach Haskell. This document is intended to explain the code just briefly, such that the reader understands what the code is doing.

Take a look at [Why Haskell Matters](https://www.haskell.org/haskellwiki/Why_Haskell_matters) and [Why Functional Programming Matters](http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf). You may also wish to follow [bitemyapp's guide](https://github.com/bitemyapp/learnhaskell) before continuing on this. Preferably, you should have a bit of knowledge about Haskell's basics before continuing.

Haskell's Elegance
===

Haskell's laziness lets us do a lot of stuff (what is laziness? I'll explain later.) Here's one that I find particularly elegant.

> pows :: Integer -> [Integer]
> pows pow = 1 : map (* pow) (pows pow)

In here, we define a function that takes in an integer and returns a list of integers (that's what the first line shows: a type signature).

In Haskell, parameters are separated by spaces (not enclosed in brackets and seperated by commas). The first and only parameter we take in is `pow`.

The `:` operator is known as the cons operator. It appends an element to a list of the same type. In here, we prepend `1` to `map (* pow) (pows pow)`.

Now, what does `map (* pow) (pows pow)` do? The `map` function takes a function, applies it to every element in a list and returns the resulting list. It may be a good idea to look at the source:

    map :: (a -> b) -> [a] -> [b]
    map _ [] = []
    map f (x:xs) = f x : map f xs

We take in a function `(a -> b)` which has an input of type `a` and output of type `b`. The map function separates the provided list into the `head` and the `tail`. This is a common pattern in Haskell (and is called pattern matching)! Here's a representation of the `head` and `tail`:

    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
     ^  +-----------------------+
    head            tail

In other words, the `head` is the first element, and the `tail` is everything after the head.

In `map`, if we get an empty array, since the values are already exhausted, we return an empty array too. If we get an array of at least one element, we apply the function `f` to the `head` of the list and prepend that to `map f xs`.

Here's a trace of the following function:

      map (* 3) [1, 2, 3]
    = 3 : map (* 3) [2, 3]
    = 3 : 6 : map (* 3) [3]
    = 3 : 6 : 9 : map (* 3) []
    = 3 : 6 : 9 : []
    = [3, 6, 9]

Consider it as a `for` loop which iterates through the whole list and builds up a list of results.

Hence, our original function multiplies every element of `pows pow` by `pow`.

Here's our trace of the function:

      pows 2
    = 1 : map (* 2) (pows 2)
    = 1 : map (* 2) (1 : map (* 2) (pows 2))
    = 1 : map (* 2) (1 : map (* 2) (1 : map (* 2) (pows 2)))
    = ...

If we cheat a bit and make a few changes (assuming that the elements are evaluated directly and the maps are "joined" together), perhaps we can see a pattern emerging:

      pows 2
    = 1 : map (* 2) (pows 2)
    = 1 : map (* 2) (1 : map (* 2) (pows 2))
    = 1 : 2 : map (* 4) (pows 2)
    = 1 : 2 : map (* 4) (1 : map (* 2) (pows 2))
    = 1 : 2 : 4 : map (* 8) (pows 2)
    = ...

We can see that we'll get a list of powers of 2.

But wait! Isn't that an infinite loop? In Haskell, executing that would have given us an infinite list of the powers of 2 (try it and see what happens by typing `pows 2` into GHCi!). Notice that the list will keep on growing. That looks like a horrible thing.

But somehow, we can do stuff with an infinite list, thanks to laziness. We need not evaluate the whole list when we run `pows 2`. We only need to evaluate the items that we need to. That is the crux of laziness.

That means that from our infinite list:

    [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ...]

We can do stuff like get the first 5 powers of 2:

    take 5 (pows 2)

and get:

    [1, 2, 4, 8, 16]

or maybe get all powers of 2 below 100:

    takeWhile (< 100) (pows 2)

and get:

    [1, 2, 4, 8, 16, 32, 64]

The elegance of this solution is the fact that we easily did this with recursion, in a rather "mathematical" way.

Furthermore, we need not take in additional parameters to limit the number of elements such that we don't evaluate an infinite list. That would have been a rather hackish solution. In fact, we leave that to the programmer.

It was as simple as that. This ability to reuse functions like this grants us a lot of power in Haskell.

It may not be the most efficient for our purpose (if we wanted to just check if a number is a power of 2, there're more efficient ways; look at [How to check if a number is a power of 2](https://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2) for more details). That's beside the point, though, as we don't often need to write performance critical code. we just need code that runs fast enough.

That allows us to reason about code in a very powerful way.

Fibonacci Numbers
===

Fibonacci numbers start with 0 and 1. Each number is the sum of the previous two numbers. In this example, we'll handle only positive integers.

Here's how the sequence looks like:

    0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ...

As you can see, the third number, 1, is the sum of 0 and 1. The fourth number, 2 is the sum of 2 and 2. This goes on forever (and hence is a perfect fit for another infinite list).

On to the code:

> fibs :: [Integer]
> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

This time round, we define `fibs` as a list of integers. We then prepend 0 and 1 to `zipWith (+) fibs (tail fibs)` (note the familiar looking `tail` function!).

What does `zipWith` do? It takes a function and applies them to the values of both of the lists. Once again, the source says a lot on its own:

    zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
    zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
    zipWith _ _ _ = []

For the following example:

    zipWith (+) [1, 2, 3] [4, 5, 6]
    = 5 : zipWith (+) [2, 3] [5, 6]
    = 5 : 7 : zipWith (+) [2] [6]
    = 5 : 7 : 8 : zipwith (+) [] []
    = 5 : 7 : 8 : []
    = [5, 7, 8]

While we now know what `zipWith` does, `zipWith (+) fibs (tail fibs)` is still a mystery to us. What could it possibly mean? Let's look at `fibs` and `tail fibs` first (with the values that we're certain of):

    fibs:      0 1 ...
    tail fibs: 1 ...

Adding up the numbers on the first column, 0 and 1, gives us 1, our third number. We append this to the list. When we evaluate the fourth number, here's what our list looks like:

    fibs:      0 1 1 ...
    tail fibs: 1 1 ...

We get the fourth number, 2, and it's appended to the list. This continues, eventually building up a list of values.

This algorithm, while a bit hard to comprehend, is inherently elegant and simple.

Conclusion
===

I hope this has showed you how elegant Haskell could be and why many programmers like working in it.

These 2 readings here explain very well why Haskell matters, and why programmers like Haskell:

* [Why Haskell matters](https://www.haskell.org/haskellwiki/Why_Haskell_matters)
* [Why Functional Programming matters](http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf)

Feel free to contact me at wei2912.supp0rt@gmail.com if you have any questions or suggestions about this document (but use the Haskell IRC channels if you have questions with regards to Haskell).
	# Shifted this file to my blog

	The new link is on my blog: https://wei2912.github.io/index.html#introduction_to_haskell

	I'll update the post on my blog from now on.

	---

	Introduction to Haskell
	---

	This document is in Literate Haskell. This means that you can download and run this file with `ghci intro.lhs`, and be able to run the functions defined in this file.

	Haskell is a pure functional programming language that comes with lazy evaluation (in GHC, that is). Its elegance is why many programmers like writing code in Haskell. In this document, I'll give a couple of examples.

	This document assumes that the reader has at least an intermediate knowledge in an imperative programming language, but does not assume knowledge of functional programming.

	Also, this document is not intended to teach Haskell. This document is intended to explain the code just briefly, such that the reader understands what the code is doing.

	Take a look at [Why Haskell Matters](https://www.haskell.org/haskellwiki/Why_Haskell_matters) and [Why Functional Programming Matters](http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf). You may also wish to follow [bitemyapp's guide](https://github.com/bitemyapp/learnhaskell) before continuing on this. Preferably, you should have a bit of knowledge about Haskell's basics before continuing.

	Haskell's Elegance
	===

	Haskell's laziness lets us do a lot of stuff (what is laziness? I'll explain later.) Here's one that I find particularly elegant.

	> pows :: Integer -> [Integer]
	> pows pow = 1 : map (* pow) (pows pow)

	In here, we define a function that takes in an integer and returns a list of integers (that's what the first line shows: a type signature).

	In Haskell, parameters are separated by spaces (not enclosed in brackets and seperated by commas). The first and only parameter we take in is `pow`.

	The `:` operator is known as the cons operator. It appends an element to a list of the same type. In here, we prepend `1` to `map (* pow) (pows pow)`.

	Now, what does `map (* pow) (pows pow)` do? The `map` function takes a function, applies it to every element in a list and returns the resulting list. It may be a good idea to look at the source:

	map :: (a -> b) -> [a] -> [b]
	map _ [] = []
	map f (x:xs) = f x : map f xs

	We take in a function `(a -> b)` which has an input of type `a` and output of type `b`. The map function separates the provided list into the `head` and the `tail`. This is a common pattern in Haskell (and is called pattern matching)! Here's a representation of the `head` and `tail`:

	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	^ +-----------------------+
	head tail

	In other words, the `head` is the first element, and the `tail` is everything after the head.

	In `map`, if we get an empty array, since the values are already exhausted, we return an empty array too. If we get an array of at least one element, we apply the function `f` to the `head` of the list and prepend that to `map f xs`.

	Here's a trace of the following function:

	map (* 3) [1, 2, 3]
	= 3 : map (* 3) [2, 3]
	= 3 : 6 : map (* 3) [3]
	= 3 : 6 : 9 : map (* 3) []
	= 3 : 6 : 9 : []
	= [3, 6, 9]

	Consider it as a `for` loop which iterates through the whole list and builds up a list of results.

	Hence, our original function multiplies every element of `pows pow` by `pow`.

	Here's our trace of the function:

	pows 2
	= 1 : map (* 2) (pows 2)
	= 1 : map (* 2) (1 : map (* 2) (pows 2))
	= 1 : map (* 2) (1 : map (* 2) (1 : map (* 2) (pows 2)))
	= ...

	If we cheat a bit and make a few changes (assuming that the elements are evaluated directly and the maps are "joined" together), perhaps we can see a pattern emerging:

	pows 2
	= 1 : map (* 2) (pows 2)
	= 1 : map (* 2) (1 : map (* 2) (pows 2))
	= 1 : 2 : map (* 4) (pows 2)
	= 1 : 2 : map (* 4) (1 : map (* 2) (pows 2))
	= 1 : 2 : 4 : map (* 8) (pows 2)
	= ...

	We can see that we'll get a list of powers of 2.

	But wait! Isn't that an infinite loop? In Haskell, executing that would have given us an infinite list of the powers of 2 (try it and see what happens by typing `pows 2` into GHCi!). Notice that the list will keep on growing. That looks like a horrible thing.

	But somehow, we can do stuff with an infinite list, thanks to laziness. We need not evaluate the whole list when we run `pows 2`. We only need to evaluate the items that we need to. That is the crux of laziness.

	That means that from our infinite list:

	[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ...]

	We can do stuff like get the first 5 powers of 2:

	take 5 (pows 2)

	and get:

	[1, 2, 4, 8, 16]

	or maybe get all powers of 2 below 100:

	takeWhile (< 100) (pows 2)

	and get:

	[1, 2, 4, 8, 16, 32, 64]

	The elegance of this solution is the fact that we easily did this with recursion, in a rather "mathematical" way.

	Furthermore, we need not take in additional parameters to limit the number of elements such that we don't evaluate an infinite list. That would have been a rather hackish solution. In fact, we leave that to the programmer.

	It was as simple as that. This ability to reuse functions like this grants us a lot of power in Haskell.

	It may not be the most efficient for our purpose (if we wanted to just check if a number is a power of 2, there're more efficient ways; look at [How to check if a number is a power of 2](https://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2) for more details). That's beside the point, though, as we don't often need to write performance critical code. we just need code that runs fast enough.

	That allows us to reason about code in a very powerful way.

	Fibonacci Numbers
	===

	Fibonacci numbers start with 0 and 1. Each number is the sum of the previous two numbers. In this example, we'll handle only positive integers.

	Here's how the sequence looks like:

	0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ...

	As you can see, the third number, 1, is the sum of 0 and 1. The fourth number, 2 is the sum of 2 and 2. This goes on forever (and hence is a perfect fit for another infinite list).

	On to the code:

	> fibs :: [Integer]
	> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

	This time round, we define `fibs` as a list of integers. We then prepend 0 and 1 to `zipWith (+) fibs (tail fibs)` (note the familiar looking `tail` function!).

	What does `zipWith` do? It takes a function and applies them to the values of both of the lists. Once again, the source says a lot on its own:

	zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
	zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
	zipWith _ _ _ = []

	For the following example:

	zipWith (+) [1, 2, 3] [4, 5, 6]
	= 5 : zipWith (+) [2, 3] [5, 6]
	= 5 : 7 : zipWith (+) [2] [6]
	= 5 : 7 : 8 : zipwith (+) [] []
	= 5 : 7 : 8 : []
	= [5, 7, 8]

	While we now know what `zipWith` does, `zipWith (+) fibs (tail fibs)` is still a mystery to us. What could it possibly mean? Let's look at `fibs` and `tail fibs` first (with the values that we're certain of):

	fibs: 0 1 ...
	tail fibs: 1 ...

	Adding up the numbers on the first column, 0 and 1, gives us 1, our third number. We append this to the list. When we evaluate the fourth number, here's what our list looks like:

	fibs: 0 1 1 ...
	tail fibs: 1 1 ...

	We get the fourth number, 2, and it's appended to the list. This continues, eventually building up a list of values.

	This algorithm, while a bit hard to comprehend, is inherently elegant and simple.

	Conclusion
	===

	I hope this has showed you how elegant Haskell could be and why many programmers like working in it.

	These 2 readings here explain very well why Haskell matters, and why programmers like Haskell:

	* [Why Haskell matters](https://www.haskell.org/haskellwiki/Why_Haskell_matters)
	* [Why Functional Programming matters](http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf)

	Feel free to contact me at wei2912.supp0rt@gmail.com if you have any questions or suggestions about this document (but use the Haskell IRC channels if you have questions with regards to Haskell).