https://github.com/wei2912/misc/blob/1ceef5c/intro.lhs

intro.lhs

Introduction to Haskell
===

*** Introduction ***

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

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

* https://www.haskell.org/haskellwiki/Why_Haskell_matters
* http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

Make sure to read them before reading the rest of this document.

*** Elegance ***

Haskell's laziness lets us do a lot of stuff. 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 seperated by spaces (not enclosed in brackets and
seperated by commas).

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)`. The question, now, is 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. Let's say we have:

> -- map (* 3) [1, 2, 3]

(ignore the 2 dashes infront; that's a comment just to make sure that GHCi
doesn't execute that piece of code)

The result is:

> -- [3, 6, 9]

For those of you familiar with imperative languages, consider it as a `for` loop
which iterates through the whole list and builds up a list of results.

So, what does our original function do? It basically multiplies every element of
`pows pow` by `pow`.

But wait! Isn't that an infinite loop? That's correct. In Haskell, executing:

> -- pows 2

would have given us an infinite list of the powers of 2 (try it and see!).

If we were to execute this directly, we'll notice that the list will keep on
growing. That's 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 a lot. It means we can do stuff like get the first 5 powers of 2:

> -- take 5 (pows 2)

and get back:

> -- [1, 2, 4, 8, 16]

The elegance of this solution is the fact that we easily did this with
recursion, in a rather mathematical way. We need not take in additional
parameters to limit the number of elements. 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 (if we wanted to just check for powers of 2,
there're more efficient ways; look at
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.

*** Primes. ***

> primes :: [Integer]
> primes = sieve [2..]
>     where
>         sieve (p:xs) = p : sieve [n | n <- xs, n `mod` p /= 0]

This is the Sieve of Eratosthenes (more information can be found at
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
). It's a bit hard to see how this code works, so stick with me for a while.

This time round, we have a top-level variable called `primes`, which is a list
of integers.

It's defined to a function `sieve` given an infinite list `[2..]` which looks
like this:

> -- [2, 3, 4, 5, 6, 7, 8, 9, ...]

That's another infinite list! Laziness sure helps a lot.

We use pattern matching to seperate the head (the first element) and the tail
(everything after the first element) into `p` and `xs`. Afterwards, we prepend
`p` to `sieve [n | n <- xs, n `mod` p /= 0]`.

Let's look at the weird thing enclosed in square brackets. It's a list
comprehension (does this remind you of set-builder notation?).

We have 3 parts in a list comprehension:

> -- [value | value <- list, predicate]

In our case, we iterate through `xs`.
We check if the value is divisible by `p`. If it isn't, `n `mod` p` will not be
equal to zero.

What this does is that it iterates through the list and picks out all the values
that aren't divisible by `p`, which is a prime in our first iteration
(specifically, 2). Then, it passes them to `sieve` again.

However, how could we evalute an infinite list? The trick is laziness once
again. We only evaluate what we need to evaluate. We certainly don't need to
filter out the whole list right now.

On the next call of `sieve`, we just need to find the head of the list and pass
the rest of the list into the list comprehension and the next call of `sieve`.

Even then, how does this work? It's hard to see how, so let's take a look at
what happens after the first 5 primes:

> -- sieve 2 : [3, 4, ...] = 2 : sieve [3, 5, 7, ...]
> -- sieve 3 : [5, 7, 9, ...] = 3 : sieve [5, 7, 11, ...]
> -- sieve 5 : [7, 11, 13, 15, 17, ...] = 5 : sieve [7, 11, 13, 17, ...]

(this isn't precisely what happens; i've illustrated the first few elements of
the list for clarity)

As you can see here, we're crossing out elements as we go by, effectively
obtaining a list of primes.

*** Conclusion ***

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

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