The New Haskell Homepage

For a declarative language like haskell, mathematics is arguably a much saner inspiration for notation than C/C++. I recommend avoiding any temptations to relate the two. When you see "return" or "class" in the code, treat it as a completely new idea.

A note! Haskell has weird syntax. But it actually uses this syntax in cool ways, as opposed to some languages that have weird syntax in an effort to be different.

Let's consider the basic unit of Haskell programming -- the function!

Here is a function which returns its input:

    f x = x

Now notice that I didn't include a type signature. In haskell, you can omit them if you want. The compiler will figure out the most general type. Think of this as C++11 `auto` keyword on steroids.

If I were to include the type signature, it would look like this:

    f :: a -> a
    f x = x

`::` just means "is of the type". So `f :: ...` is "function f is of the type..."

`a` is a type variable. Think of this like C++ templates! In C++, an equivalent function is

   template 
   T f(T x) { return x; }

The `->` syntax is a bit funny, but it makes sense when you learn about function currying, which I will not explain now because it can be intimidating to some. For now, just think of the type signature as

    arg1Type -> arg2Type -> ... -> argNType -> ResultType

    f :: a -> a

Now let's consider a more complex function.

    f x = 2 * x

In Java style, we might say that the type must implement the interface `Multipliable` or something. It turns out, Haskell has a system that is very roughly similar to Java interfaces or in C++, a class with a bunch of virtual methods.

Haskell calls these Typeclasses. So there is a typeclass that specifies that types in the typeclass must implement some basic numeric methods, such as +, -, etc. This typeclass is called `Num`.

So we can imagine, our doubling function only takes types that implement `Num`. Our type signature reads:

    f :: Num a => a -> a
    f x = x * 2

    f :: (Show a, Num a) => a -> a

Now we are ready to approach the `primes` bit.

The first foreign looking thing is [2..]. This is an infinite list from 2 to infinity. How can one have an infinite list? The answer is laziness.

Whenever I go and ask for the 10000th value, the list must extend itself to that value if it hasn't yet. So the list only grows for as much as you ask for, but in theory it will grow until you run out of memory.

The [m..n] syntax is just nice syntactic sugar because it's used so much. [1..10] == [1,2,3,4,5,6,7,8,9,10]

[1..] == [1,2,3,4,5,....infinity]

So this is what we know so far:

    primes = sieve [2..]

Now you ask, well what the hell is the function `sieve`?

Haskell has a nice sugar for defining scoped functions within other functions with the `where` keyword.

Consider the doubling function. I could instead do:

    f x = x * (three - one)
      where
        three = 3
        one = 1

So `sieve` is a scoped function (cannot be accessed from outside of `primes` that takes a list as an argument and apparently produces the primes that are in that list. How does it do it?

We see some weird syntax in the definition of `sieve`:

    sieve (p:xs) = ...

    int fact(int n) {
        if(n == 0) return 1;
        return n * fact(n-1);
    }

    int fact(0) { return 1; }
    int fact(int n) { return n * fact(n-1); }

So in Haskell, we could implement factorial like

    fact :: Num a => a -> a
    fact 0 = 1
    fact n = n * fact (n-1)

Now we go into the funny syntax and power of that funny syntax! Not only can pattern matching match on values, but it can decompose those values. What do I mean? Again, let me use some fake C++ as an example.

Consider the C++ function

    int f(pair my_pair) {
        int x = my_pair.first;
        int y = my_pair.second;
        return x*y;
    }

Now imagine if C++ let us do this:

    int f(pair) {
        return x*y;
    }

Consider a direct translation of the C++:

    f :: (Int, Int) -> Int
    f my_pair = fst my_pair * snd my_pair

    f :: (Int, Int) -> Int
    f (x,y) = x*y

So what is `sieve (p:xs)` decomposing?

In Haskell, the default [] list is a linked list (there are random access arrays in various libraries). That means we can stick a value onto the front of the list in O(1) time. The way we stick a value onto the front of the list is with the `:` operator.

So

    x = [1,2,3]
    y = 0:x

Just like we can compose lists with the `:` operator, we can decompose them via pattern matching with it.

So consider the function (I'll omit the type signature for brevity)

    f (p:xs) = print (p, xs)

    [1,2,3,4] == 1:[2,3,4]

This is a very common idiom in Haskell. Let's say I wanted to make a function that added 1 to every value in a list. Ignoring that there are much cooler/efficient ways to do this in Haskell, let's make a specialized function for it.

    addOne (x:xs) = x+1 : addOne xs

Now in our function body, we recompose a list with different values. Those values are `x+1` for the first value, and `addOne xs` for the second value. So we add one to the first value, and stick it into the front of the rest of the list after the rest has had 1 added to its values. You might notice now, that there is no bottom-out case for this recursion. So let's add one.

    addOne [] = []
    addOne (x:xs) = x+1 : addOne xs

So `sieve` is pulling off the first value, storing it in `p`, and taking the rest of the list and storing it in `xs`.

It is returning...

    p : sieve [x | x 

    sieve [x | x 

    p stuck onto the front of all the primes in [x | x