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

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:

Prelude> [1,2,3,4]
[1,2,3,4]

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:

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

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:

[]  :: [a]
(:) :: a -> [a] -> [a]

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:

4 : []

Using these two constructors, we can decompose long lists into their basic elements. The following calculation shows how we might otherwise write the list [1,2,3,4]:

[1,2,3,4]
  == {- definition of (:) -}
1:[2,3,4]
  == {- definition of (:) -}
1:2:[3,4]
  == {- definition of (:) -}
1:2:3:[4]
  == {- definition of (:) -}
1:2:3:4:[]

Haskell gives us convenient notation to describe lists of numbers, where the following code lists the numbers from 1 to 10:

Prelude> [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]

We can even create infinite lists, by typing the following, which produces the list of natural numbers starting from 1:

[1 .. ]

Sums

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 sum:

sum :: [Int] -> Int

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:

sum [] = 0

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 (x:xs):

sum (x:xs) = x + sum xs

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?

Since sum is such a useful function, it’s actually already defined in ghci, so you can test it directly in a prompt:

Prelude> sum [1..10]
55

Comprehensions

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 1 to 100:

[x | x <- [1 .. 100], even x]

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

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:

Prelude> [x | x <- [1 .. 100], x `mod` 7 == 0]
[7,14,21,28,35,42,49,56,63,70,77,84,91,98]

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:

[x | x <- [0 .. 999], x `mod` 3 == 0  || x `mod` 5 == 0]

Of course, this only produces all the values between 0 and 999 that are multiples of 3 or 5. Our final task is to sum this list, which we can do with the sum function we saw earlier:

Prelude> sum [x | x <- [0 .. 999], x `mod` 3 == 0  || x `mod` 5 == 0]
233168

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:

Prelude> :l euler-1.lhs

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:

euler1 = sum [x | x <- [0 .. 999], x `mod` 3 == 0  || x `mod` 5 == 0]

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:

Prelude> :l euler-1.lhs
[1 of 1] Compiling Main             ( euler-1.lhs, interpreted )
Ok, modules loaded: Main.
*Main> euler1
233168

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!

Summary

In this article we’ve covered a few important ideas:

Lists can be made from [] and (:) constructors.
We can define functions like sum based 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!