Euler #0 : Hello Haskell!

by Nicolas Wu


Posted on 24 June 2010

Tags: Haskell, Euler


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.

Hello World!

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.

Values

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.

Booleans

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.

Functions

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.

Polymorphism

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.

Summary

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!

Comments