by Nicolas Wu

Posted on 24 June 2010

Unfortunately, writing about Project Euler answers is considered controversial, since some people might use these solutions to cheat their way through the website (which doesn’t make sense, since most of the benefit comes from thinking about the problems for yourself). Some people view Project Euler as some kind of competition, and are not keen on answers being published at all. Nevertheless, I’ve decided to post these articles since they will hopefully make an interesting read, and might encourage people to start working on Project Euler for themselves, or investigate using Haskell. Since the first level of achievement is only cleared after answering twenty-five questions, I hope I’m not offending too many people by posting these articles.

This is the first post in a series that covers the basics of programming in Haskell by looking at the answers to the first twenty Project Euler problems. Project Euler is a collection of interesting mathematical problems that can be solved with a computer. The site itself states that:

Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics.

If you’re a programmer, then hopefully you’ll be working your way through the problems using your own favourite language, and I’ve written this series of posts to show how Haskell elegantly solves these problems. —

I’m not going to assume that you know very much programming in this series, and the rest of this article is a quick introduction to the very basics of Haskell. If you’re already a programmer, you can probably skip through the rest of this article once you’ve installed a Haskell compiler.

If you want to learn a bit of Haskell, you ought to get stuck right in an install a program that can run your Haskell code. I suggest you use `ghci`

, which comes as part of the Haskell Platform. Go ahead and follow that link and install whatever you need.

Once you’re done, you should run `ghci`

, and get a blank screen with the words `Prelude>`

waiting near the top. If you type `"Hello World!"`

(including the `"`

symbols), the prompt will say it right back to you:

```
Prelude> "Hello World!"
"Hello World!"
```

In this article, I’ll start a line with `Prelude>`

like I did just above, to show what would happen if you typed something into the `ghci`

prompt, and write what `ghci`

returns below that line. Feel free to follow along in your prompt too.

Oh, I should probably mention that when you’ve had enough of `ghci`

, type `:q`

to get out:

```
*Main> :q
Leaving GHCi.
```

You can think of `ghci`

as a clever calculator, and use symbols like `+`

, `-`

and `*`

to add, subtract and multiply values (I’ll talk about division later):

```
Prelude> (1 + 2) * (-3) + 20
11
```

You might notice that I had to put brackets around `-3`

: that’s because `ghci`

gets a bit upset if you don’t.

All the values you’ll use in Haskell have a *type*, which separates the values into different groups. For example, integers like `1`

and `2`

have type `Int`

, and we can write the following *type signature* to indicate this:

```
1 :: Int
2 :: Int
```

The code after the `::`

symbol shows us what the type is of the value to the left. In this case it just says that those values have type `Int`

.

The operators like `(+)`

and `(*)`

have types too:

```
(+) :: Int -> Int -> Int
(*) :: Int -> Int -> Int
```

These operators are written between brackets because symbols like these are usually *infix* operations, which means that the values they use go either side of them. By enclosing an infix operator in brackets, it is considered to be a *prefix* function, where arguments follow the operation. The type of `(+)`

takes two values of type `Int`

, one after the other, returns a value of type `Int`

, which is the result of adding the first two.

Here’s the type of `"Hello World!"`

:

`"Hello World!" :: String`

A `String`

is basically a list of characters. If you try something strange like:

`Prelude> "Hello World!" + 3`

Then `ghci`

will moan at you, since it doesn’t understand what you’re asking for! Here you’ll get an error because the types didn’t match what is expected: the `(+)`

operator requires two values of type `Int`

, but here we’re giving it a `String`

, which doesn’t make sense.

Another basic type is `Bool`

, which has two values:

```
True :: Bool
False :: Bool
```

These values are used to describe whether something is true or not, and they are usually called *Boolean* values after the mathematician George Boole.

Earlier on we saw some operators like `(+)`

and `(*)`

that worked with values of type `Int`

. Boolean values also come with a couple operators:

```
(&&) :: Bool -> Bool -> Bool
(||) :: Bool -> Bool -> Bool
```

The first operator, `(&&)`

, takes two values of type `Bool`

, and returns returns `True`

if *both* the values given to it are `True`

, and otherwise returns `False`

. We tend to call this operator “and”. The second operator, `(||)`

, returns `True`

if *either* of the values given to it are `True`

, and otherwise returns `False`

, this operator is usually called “or”. Go ahead and try some combinations:

```
Prelude> True && False
False
Prelude> True || True
True
```

Functions can involve more than one type, like the function called `even`

that tells us whether or not a value is even, and the function `odd`

that tells us when a value is odd. The type signatures of these functions show us that they take values of type `Int`

, and return a values of type `Bool`

:

```
even :: Int -> Bool
odd :: Int -> Bool
```

We can try this out in `ghci`

:

```
Prelude> even 234
True
```

Since the end result of an `even`

function is something of type `Bool`

, we can put some of the functions we’ve already seen together:

```
Prelude> even (3 + 4) || odd (7 - 3)
True
```

We can work out what this silly little program does for ourselves:

```
even (3 + 4) || odd (7 - 2)
== {- basic arithmetic -}
even 7 || odd 5
== {- 7 is not even, 5 is odd -}
False || True
== {- definition of (||) -}
True
```

One of the neat things about functional programming is that we can do calculations like this to work out what is going on in a program. Later on in this series, we’ll see how this helps us to find solutions to the problems we face.

An `Int`

represents a whole number, so when we perform divisions using `Int`

values the results will always be whole numbers too. The functions `div`

and `mod`

help us to do integer division, where `div`

returns the result of whole number division, and `mod`

gives us the remainder. Here are the types of these functions:

```
div :: Int -> Int -> Int
mod :: Int -> Int -> Int
```

As an example, here’s what these functions return for some simple values:

```
Prelude> div 10 3
3
Prelude> mod 10 3
1
```

Most of the time we want to feed values to functions one after the other, like we did in the example above, but with some functions like `div`

and `mod`

, it makes more sense to write the function *between* its arguments, as if it were an operator. In Haskell we can do this by surrounding the function with tick ```

symbols:

```
Prelude> 23 `div` 7
3
Prelude> 23 `mod` 7
3
```

We call these *infix* functions.

The operators like `(+)`

and `div`

can only take values of specific types that can’t change, so we tend to call those *monomorphic* functions. Some functions are a bit more general, like the `(==)`

operator that returns a `Bool`

:

`(==) :: a -> a -> Bool`

This function takes two values of some variable type, `a`

, and checks to see if those values are equal. If the values are equal then the function returns `True`

, otherwise, it returns `False`

.

Since the type we have here is an `a`

, rather than some fixed type, we can use different types in place of `a`

, like `Int`

, or `Bool`

. We call functions like `(==)`

that can take different types of values *polymorphic* functions.

For example, we can feed the function two values of `Int`

if we want:

```
Prelude> 5 + 3 == 8
True
```

We can also try to use values of type `Bool`

too:

```
Prelude> True && False == False
True
```

Each use of `(==)`

in an expression is independent of the others, and the following statement shows us how `(==)`

is a polymorphic function even within a single expression:

```
Prelude> False == False || 1 == 2
True
```

Here the first version of `(==)`

has type `Bool -> Bool -> Bool`

, and the second one has type `Int -> Int -> Bool`

.

This little lesson has shown us a really small snapshot of some of the basics to using Haskell. In particular, we’ve learnt about:

- Basic types like
`Int`

and`Bool`

. - The importance of type signatures.
- Polymorphic functions.

In the articles that follow we’ll see that we can use `ghci`

for far more than the silly little examples we’ve seen so far, and that we can program some really neat stuff in just a few lines of code!