Euler #1 : Listing Multiples
by Nicolas Wu
Posted on 1 July 2010
The first problem in Project Euler is as follows:
Add all the natural numbers below one thousand that are multiples of 3 or 5.
This kind of problem is rather easy to solve with lists, so in this article, we’ll talk about how to construct lists and use them to compute values, and then show how a list comprehension can be used to produce our answer.
Lists are really important in Haskell, and we use them for all sorts of things, so it’s well worth understanding these. A list of values can be written down like this:
Lists are made up of values of all the same type: each of the values in the list we just wrote was an
Int. That’s because just like all the other values in Haskell, lists like these have types too:
The type looks a bit funny, because it’s an
Int wrapped up in some brackets. Those brackets are there to tell you that it’s a list of
Int values, and not just one by itself.
All lists are composed from two constructor functions:
The first of these,
, constructs an empty list of elements. It’s type is polymorphic, since even empty lists need a type. The operator
(:) takes a single element, of type
a, and a list of type
[a], and adds the element to the front of the list. Since this operator is polymorphic, it can be used to create lists of any type.
So, putting these together, if we want to add the element
4 to the front of the empty list, we’d write the following:
Using these two constructors, we can decompose long lists into their basic elements. The following calculation shows how we might otherwise write the list
Haskell gives us convenient notation to describe lists of numbers, where the following code lists the numbers from
We can even create infinite lists, by typing the following, which produces the list of natural numbers starting from
The first function that uses lists which we’ll discuss is the function
sum, that sums all the values in a list of
Int values. We’ll start by describing the type of
The type of this function tells us that it takes a list of
Int, and returns an
Int. In order to define the function, we’ll describe what it does to each of the list constructors. The simplest constructor is
, which produces the empty list. The sum of all the elements in this list is trivially
0, since there are no values in the list:
The other constructor for lists is
(:), and we’ll consider how to sum a list made up from a value,
x, added to the front of the list
xs, which we write as
This is a recursive definition, where we simply say that the sum of
(x:xs) is the value of
x added to the result of summing the rest of
xs. Since we’ve finished considering all the constructors for a list, our definition of
sum is complete, wasn’t that simple?
sum is such a useful function, it’s actually already defined in
ghci, so you can test it directly in a prompt:
A list comprehension is a convenient notation that helps us to construct interesting lists. For example, take a look at the following code, which produces all the even numbers from
List comprehensions like this one are made up of two sections, separated by a
| symbol in the middle. The left hand side of the comprehension describes the value that is produced, while the right hand side describes the conditions that hold for that to be produced.
In the example above, the value is just
x, and there are two conditions that must hold. Firstly, the value of
x is drawn from the list
[1 .. 100], (which we show by using the funny
<- arrow), and secondly, the value is produced only when
even x is
As another example of a list comprehension, we might change the condition so that only values that are multiples of
7 are produced. In order to do this, we make our condition
x `mod` 7 == 0, since all multiples of
7 have no remainder:
We now have all the necessary ingredients to answer our question. Our task is to make a condition that checks to see wither a value is a multiple of 3 or of 5. We do this by making use of the “or” operator,
(||), that we saw in the last article:
Of course, this only produces all the values between
999 that are multiples of
5. Our final task is to sum this list, which we can do with the
sum function we saw earlier:
Voila! Our first Euler Project puzzle is solved, and in only a single line of code!
Files and Bird Tracks
One last detail before we wrap up. Every time you start a new
ghci session, you’ll lose the work you did there before. It’s much better to work from a file and load the file into
ghci when you want to test out a function.
To do that, open up a blank file in some text editor, like
notepad, and save it as
euler-1.lhs. Files that end in
.lhs can be loaded into
ghci by typing something like:
In those files, lines that start with
> will be read by
ghci, and lines that don’t will be ignored. We call these Bird tracks. The only catch is that you have to make sure that lines surrounding blocks of Bird tracks are empty, otherwise you’ll get an error message.
Using files makes it really easy to create new functions. For example, we might want to save our first solution by putting this line into our script:
This line names our function
euler1 so that we can reuse it later on. Once our file is saved, we can load it into
ghci and output the answer right away:
A few things have happened here: first we loaded our file into
ghci, which made it automatically compile. Once
ghci finished compiling our function, it waited for our next command, but changed the prompt to
*Main>, which tells us that it’s now working from our file. Then, we just typed the name of our function, and
ghci worked out the answer for us!
For those of you with super sharp eyes, you’ll notice that the the only line in this whole article that starts with a Bird track is the one we needed in our file. I’ve done this so that you can copy the text of this whole post and pop it into a
.lhs file and load it right into
ghci! I’ll do this in the rest of these articles, so keep an eye out for those tracks!
In this article we’ve covered a few important ideas:
- Lists can be made from
- We can define functions like
sumbased on those constructors.
- List comprehensions are a convenient way to build lists.
We’ll be seeing plenty more of lists in the posts that follow, so make sure you understand these!