Haskell is one of the most commonly used purely functional programming languages that has been slowly rising in popularity, but haven’t quite caught on to mainstream programmers. (EDIT IN 2019: In recent years, loads of exciting software have been developed in Haskell, like Pandoc, a marvellous universal markup converter which this blog uses heavily, and semantic by GitHub, a library for parsing, analyzing and comparing source code.)
First off, a few basics you need to know about Haskell.
We can use Haskell as a calculator. Let’s start up
We can now type stuff into the prompt…
Prelude> 3 + 7 10 Prelude> 20 - 10 10 Prelude> 9 / 0 Infinity
…or check out the types of expressions:
Prelude> :type 2 + 2 == 5 2 + 2 == 5 :: Bool
What goes after the double colon is our type. As you can see here,
2 + 2 == 5 yields a boolean. We’ll see the double colon notation being used later on.
Comments can start with
--, which lasts till the end of a line, or enclosed within
-}. The latter can span multiple lines.
Functions are the building block of Haskell. Everything we do in Haskell relies on stringing together functions.
Every function comprises 2 parts:
- Type signature
The type signature tells us what type the function has. Let’s look at an example:
addByThree :: Integer -> Integer
The first line is a type signature. In this case, we take in a single Integer and return an Integer.
Now, for a function to add two integers:
add :: Integer -> Integer -> Integer
This time round, we take in 2 integers and return a single integer. In Haskell, we usually rely on function naming and type signatures to describe what our function does, rather than pointing out and explaining a whole bunch of statements in our code.
Let’s take a look at what the whole of
addByThree looks like.
addByThree :: Integer -> Integer = x + 3addByThree x
In Haskell, we write functions similar to equations. The left hand side is
addByThree x, which is our function name and the integer
x. The right hand side is
x + 3 which adds 3 to our integer
x. Hence, by calling
addByThree 10 we’ll get back
add function is the following:
add :: Integer -> Integer -> Integer = x + yadd x y
You can give these functions a try by pasting this into
addByThree :: Integer -> Integer = x + 3 addByThree x add :: Integer -> Integer -> Integer = x + yadd x y
and then running GHCi:
Then, typing into the prompt:
Prelude> :load main.hs 1 of 1] Compiling Main ( main.hs, interpreted ) [Ok, modules loaded: Main. *Main> addByThree 10 13 *Main> add 10 20 30
* are infix functions, placed between two arguments. We can use them as “normal” functions by enclosing the operator of our choice in brackets. For example, we can rewrite
3 + 7 as
(+) 3 7.
Lists in Haskell are linked lists. We define lists this way:
Prelude> [1, 2, 3] 1, 2, 3] [Prelude> :type "abc" "abc" :: [Char]
Lists in Haskell are implemented as a series of “cons” operations, which join up elements of the list. We use the
: operator to do this (otherwise known as the cons operator). It prepends an element to a list of the same type.
Prelude> 3 : [1, 2] 3, 1, 2][
: operator is right-associative, which means that everything on the right is given precedence and evaluated first.
Prelude> 3 : (2 : (1 : )) 3, 2, 1] [Prelude> 3 : 2 : 1 :  3, 2, 1][
Polymorphic types allow for generic types to be used in a function. Take the function
id :: a -> a id x = x
id can take in any type, but the use of
a as both input and output suggests that the two types have to be the same (note that polymorphic types are lowercase while “normal” types are uppercase).
In our equations, we specified that
id x = x. This function just returns the value it was passed into, and so is called the identity function.
Higher Order functions
Higher order functions are functions that can take in or return other functions.
A function which takes in one parameter and returns something of the same type is denoted by
a -> a. Similarly, a function that takes in a function and returns something of the same type is
(a -> a) -> a.
A very commonly used function is
map which applies a function to every value in a list. Let’s look at the type:
map :: (a -> b) -> [a] -> [b]
map takes in a function that changes the type of an element from
b. It then takes in a list of type
a and returns a list of type
That’s it for the basics. Let’s get down to some interesting code.
Powers of a number
Haskell lets us do quite a lot of elegant stuff. Here’s one example that I find to be quite neat:
pows :: Integer -> [Integer] = iterate (* base) 1pows base
In here, we define a function that takes in an integer and returns a list of integers. Our equation then defines
pows base as
iterate (* base) 1.
* base looks weird, but it is written with the intention of using partially applied functions.
Let’s first look at the difference between multiplying 2 integers and multiplying an integer by 3:
multiply :: Integer -> Integer -> Integer = x * y multiply x y multiplyByThree :: Integer -> Integer = x * 3multiplyByThree x
We notice that the two functions appear similar. Both take in
x and multiply it by a value.
Now, what if we had a way to specify not all arguments to
(*) such that we’d get another function? Well, the above functions can be rewritten as:
multiply :: Integer -> Integer -> Integer = (x *) y multiply x y multiplyByThree :: Integer -> Integer = (x *) 3multiplyByThree x
We provide the left value,
(x *) gives us a function that takes in a single number and multiples that by
x. Finally, we get a value. Haskell allows us to supply only a few parameters required, so as to get back a function that takes in the rest of the parameters. This is known as partial application.
How does that help us? This is where higher order functions come in.
Here’s the definition of
iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x)
iterate does is that it prepends a value to a list, applies a function to the value and pass the new value into
iterate again. This is what we call a recursive function — a function that calls itself.
Trace of the
It’s hard to see what this function does if you’re not familiar with recursion, so let’s look at a trace.
3 pows = iterate (3 *) 1 = 1 : iterate (3 *) 3 -- 3 * 1 = 1 : 3 : iterate (3 *) 9 -- 3 * 3 = 1 : 3 : 9 : iterate (3 *) 27 -- 3 * 9 = ...
We can see that we’ll get a list of powers of 3. How this comes about is that we go through the following steps:
- Prepend the current value to the list
(3 *)to the current value to get a new value.
iterate (3 *)to the new value.
Partially applied functions allow us to write this very elegantly, without having to define a new function
multiplyByThree. This is one of the lovely things about functional programming — we get to reuse all sorts of functions.
Running that will give us a list of the powers of 3.
But wait! Wouldn’t that go on for infinity? In Haskell, executing
pows 3 would have given us an infinite list of the powers of 3 (try it and see what happens!). Notice that the list will keep on growing, which looks horrible.
But we can still do stuff with an infinite list, thanks to laziness. We need not evaluate the whole list, but just the items that we need.
From our infinite list,
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, ...],
we can do stuff like get the first 5 powers of 3,
take 5 (pows 3)
[1, 3, 9, 27, 81]
or maybe get all powers of 2 below 100
takeWhile (< 100) (pows 2)
[1, 2, 4, 8, 16, 32, 64]
The elegance of this solution lies in the fact that we easily did this with recursion, in a rather terse, clear and “mathematical” way. The ability to reuse functions like this grants us a lot of flexibility in Haskell and allows us to reason about code in a very powerful way.
Fibonacci numbers start with 0 and 1. Each number is the sum of the previous two numbers. In this example, we’ll handle only natural numbers.
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 1 and 1. This sequence goes on forever.
On to the code:
fibs :: [Integer] = 0 : 1 : zipWith (+) fibs (tail fibs)fibs
This time round, we define
fibs as a list of integers. We then prepend
zipWith (+) fibs (tail fibs).
zipWith do? Before we cover it, we need to take a look at some list terminology and pattern matching.
Take a look at this graphical representation:
+--+--+--+--+--+--+--+--+ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ^
The top line denotes the elements that make up the
tail while the bottom carat denotes the
head. To put it in words, the
head is the first element of the list, while the
tail is everything after the
Here’s another graphical representation:
+--+--+--+--+--+--+--+--+ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ^
This time round, the top line denotes the
init and the carat denotes the
last are all functions. You can try them out in GHCi:
> head [1, 2, 3] 1 > tail [1, 2, 3] 2, 3] [> init [1, 2, 3] 1, 2] [> last [1, 2, 3] 3
Now that we’ve conquered list terminology, let’s look at
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] zipWith f (a : as) (b : bs) = f a b : zipWith f as bs zipWith _ _ _ = 
We have 2 equations, with some weird underscores. How does this work?
Haskell allows for pattern matching. In our case,
(a : as) seperates a list of values into
a (the head) and
as (the tail). We do the same with
(b : bs). Afterwards, we apply
b, then prepend our value to
zipWith f as bs.
However, there’s still a second equation. Underscores are a way for us to dispose unneeded values. The last clause catches everything that doesn’t fit the first equation and returns an empty list.
But why do we need a catchall? As it turns out, the head of an empty list is undefined. Hence,
(a : as) will only match lists with at least one element. Our catchall ensures that the function doesn’t error out when we exhaust both lists. Instead, it returns an empty list.
This is what we call the
base case of a recursive function, as all other calls to the recursive function gets reduced to this. It’s also the reason why
zipWith terminates while
While we now know what the function is doing, we still have no idea how it works. Looking at the trace should gain some inspiration as to how this works:
zipWith (+) [1, 2, 3] [4, 5, 6] -- 1 + 4 = 5 : zipWith (+) [2, 3] [5, 6] -- 2 + 5 = 5 : 7 : zipWith (+)   -- 3 + 6 = 5 : 7 : 9 : zipwith (+)   -- returns  = 5 : 7 : 9 :  = [5, 7, 9]
The comment shows how the
(+) function is being applied to the values of the list and how the values turn into a list.
Back to the
zipWith (+) fibs (tail fibs) is still a mystery to us. What could it possibly mean? Let’s look at
tail fibs first (with the values that we already know):
0 1 ... + 1 ... --------- 1
The first line is
fibs and the second line is
tail fibs. 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:
0 1 1 ... + 1 1 ... --------- 1 2
We get the fourth number, 2, and it’s appended to the list. Now, for the fifth number:
0 1 1 2 ... + 1 1 2 ... --------- 1 2 3
We get 3. This continues, eventually building up a list of Fibonacci numbers.
I hope this has showed you how elegant Haskell could be and why many programmers enjoy working in it. There’s a lot more to Haskell than this (such as functors, monads, etc.) which can make working on code rather nice for the mathematically-inclined.
You can take a look at the following readings:
You may also wish to follow Chris Allen’s guide to learn more about Haskell. (EDIT IN 2019: Chris Allen has finished all the content in his book on Haskell and is offering early access on Gumroad before the book is published.)