From Wikibooks, the open-content textbooks collection

This is the print version of Haskell You won't see this message or any elements not part of the book's content when you print or preview this page.

Table Of Contents

Haskell Basics

Getting set up

Variables and functions

Lists and tuples

Next steps

Type basics

Simple input and output

Type declarations

Elementary Haskell

Recursion

List processing

More about lists

Pattern matching

Control structures

More on functions

Higher order functions

Intermediate Haskell

Modules

Indentation

More on datatypes

Class declarations

Classes and types

Keeping track of State

Monads

Understanding monads

Advanced monads

Additive monads (MonadPlus)

Monadic parser combinators

Monad transformers

Value recursion (MonadFix)

Practical monads

Advanced Haskell

Arrows

Understanding arrows

Continuation passing style (CPS)

Mutable objects

Zippers

Applicative Functors

Monoids

Concurrency

Fun with Types

Polymorphism basics

Existentially quantified types

Advanced type classes

Phantom types

Generalised algebraic data-types (GADT)

Datatype algebra

Wider Theory

Denotational semantics

Equational reasoning

Program derivation

Category theory

The Curry-Howard isomorphism

fix and recursion

Haskell Performance

Introduction

Step by Step Examples

Graph reduction

Laziness

Strictness

Algorithm complexity

Data structures

Parallelism

Libraries Reference

The Hierarchical Libraries

Lists:Arrays:Maybe:Maps

IO:Random Numbers

General Practices

Building a standalone application

Debugging

Testing

Packaging your software (Cabal)

Using the Foreign Function Interface (FFI)

Specialised Tasks

Graphical user interfaces (GUI)

Databases

Web programming

Working with XML

Using Regular Expressions

Haskell Basics

Getting set up

This chapter will explore how to install the programs you'll need to start coding in Haskell.

Installing Haskell

First of all, you need a Haskell compiler. A compiler is a program that takes your code and spits out an executable which you can run on your machine.

There are several Haskell compilers available freely, the most popular and fully featured of them all being the Glasgow Haskell Compiler or GHC for short. The GHC was originally written at the University of Glasgow. GHC is available for most platforms:

• For MS Windows, see the GHC download page for details
• For MacOS X, Linux or other platforms, you are most likely better off using one of the pre-packaged versions for your distribution or operating system.

Getting interactive

If you've just installed GHC, then you'll have also installed a sideline program called GHCi. The 'i' stands for 'interactive', and you can see this if you start it up. Open a shell (or click Start, then Run, then type 'cmd' and hit Enter if you're on Windows) and type ghci, then press Enter.

You should get output that looks something like the following:

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude>

The first bit is GHCi's logo. It then informs you it's loading the base package, so you'll have access to most of the built-in functions and modules that come with GHC. Finally, the Prelude> bit is known as the prompt. This is where you enter commands, and GHCi will respond with what they evaluate to.

Let's try some basic arithmetic:

Prelude> 2 + 2
4
Prelude> 5 * 4 + 3
23
Prelude> 2 ^ 5
32

The operators are similar to what they are in other languages: + is addition, * is multiplication, and ^ is exponentiation (raising to the power of).

GHCi is a very powerful development environment. As we progress through the course, we'll learn how we can load source files into GHCi, and evaluate different bits of them.

The next chapter will introduce some of the basic concepts of Haskell. Let's dive into that and have a look at our first Haskell functions.

Variables and functions

(All the examples in this chapter can be typed into a Haskell source file and evaluated by loading that file into GHC or Hugs.)

Variables

Previously, we saw how to do simple arithmetic operations like addition and subtraction. Pop quiz: what is the area of a circle whose radius is 5 cm? No, don't worry, you haven't stumbled through the Geometry wikibook by mistake. The area of our circle is πr² where r is our radius (5cm) and π, for the sake of simplicity, is 3.14. So let's try this out in GHCi:

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Prelude>

So let's see, we want to multiply pi (3.14) times our radius squared, so that would be

Prelude> 3.14 * 5^2
78.5

Great! Well, now since we have these wonderful, powerful computers to help us calculate things, there really isn't any need to round pi down to 2 decimal places. Let's do the same thing again, but with a slightly longer value for pi

Prelude> 3.14159265358979323846264338327950 * (5 ^ 2)
78.53981633974483

Much better, so now how about giving me the circumference of that circle (hint: 2πr)?

Prelude> 2 * 3.14159265358979323846264338327950 * 5
31.41592653589793

Or how about the area of a different circle with radius 25 (hint: πr²)?

Prelude> 3.14159265358979323846264338327950 * (25 ^ 2)
1963.4954084936207

What we're hoping here is that sooner or later, you are starting to get sick of typing (or copy-and-pasting) all this text into your interpreter (some of you might even have noticed the up-arrow and Emacs-style key bindings to zip around the command line). Well, the whole point of programming, we would argue, is to avoid doing stupid, boring, repetitious work like typing the first 20 digits of pi a million times. What we really need is a means of remembering the value of pi:

Prelude> let pi = 3.14159265358979323846264338327950

Here you are literally telling Haskell to: "let pi be equal to 3.14159...". This introduces the new variable pi, which is now defined as being the number 3.14159265358979323846264338327950. This will be very handy because it means that we can call that value back up by just typing pi again:

Prelude> pi
3.141592653589793

Don't worry about all those missing digits; they're just skipped when displaying the value. All the digits will be used in any future calculations.

Having variables takes some of the tedium out of things. What is the area of a circle having a radius of 5 cm? How about a radius of 25cm?

Prelude> pi * 5^2
78.53981633974483
Prelude> pi * 25^2
1963.4954084936207

Types

Following the previous example, you might be tempted to try storing a value for that radius. Let's see what happens:

Prelude> let r = 25
Prelude> 2 * pi * r

<interactive>:1:9:
    Couldn't match `Double' against `Integer'
      Expected type: Double
      Inferred type: Integer
    In the second argument of `(*)', namely `r'
    In the definition of `it': it = 2 * pi * r

Whoops! You've just run into a programming concept known as types. Types are a feature of many programming languages which are designed to catch some of your programming errors early on so that you find out about them before it's too late. We'll discuss types in more detail later on in the Type basics chapter, but for now it's useful to think in terms of plugs and connectors. For example, many of the plugs on the back of your computer are designed to have different shapes and sizes for a purpose. This is partly so that you don't inadvertently plug the wrong bits of your computer together and blow something up. Types serve a similar purpose, but in this particular example, well, types aren't so helpful.

The tricky bit here is that numbers like 25 can either be interpreted as being Double or Integer (among other types)... but for lack of other information, Haskell has "guessed" that its type must be Integer (which cannot be multiplied with a Double). To work around this, we simply insist that it is to be treated as a Double

Prelude> let r = 25 :: Double
Prelude> 2 * pi * r
157.07963267948966

Note that Haskell only has this "guessing" behaviour in contexts where it does not have enough information to infer the type of something. As we will see below, most of the time, the surrounding context gives us all of the information that is needed to determine, say, if a number is to be treated as an Integer or not.

Prelude> let r :: Num a => a ; r = 25
Prelude> 2 * pi * r
157.07963267948966

Variables within variables

Variables can contain much more than just simple values such as 3.14. Indeed, they can contain any Haskell expression whatsoever. So, if we wanted to keep around, say the area of a circle with radius of 5, we could write something like this:

Prelude> let area = pi * 5^2

What's interesting about this is that we've stored a complicated chunk of Haskell (an arithmetic expression containing a variable) into yet another variable.

We can use variables to store any arbitrary Haskell code, so let's use this to get our acts together.

Prelude> let r = 25.0
Prelude> let area2 = pi * r ^ 2
Prelude> area2
1963.4954084936207

So far so good.

Prelude> let r = 2.0
Prelude> area2
1963.4954084936207

Wait a second, why didn't this work? That is, why is it that we get the same value for area as we did back when r was 25? The reason this is the case is that variables in Haskell do not change^[1]. What actually happens when you defined r the second time is that you are talking about a different r. This is something that happens in real life as well. How many people do you know that have the name John? What's interesting about people named John is that most of the time, you can talk about "John" to your friends, and depending on the context, your friends will know which John you are referring to. Programming has something similar to context, called scope. We won't explain scope (at least not now), but Haskell's lexical scope is the magic that lets us define two different r and always get the right one back. Scope, however, does not solve the current problem. What we want to do is define a generic area function that always gives you the area of a circle. What we could do is just define it a second time:

Prelude> let area3 = pi * r ^ 2
Prelude> area3
12.566370614359172

But we are programmers, and programmers loathe repetition. Is there a better way?

Functions

What we are really trying to accomplish with our generic area is to define a function. Defining functions in Haskell is dead-simple. It is exactly like defining a variable, except with a little extra stuff on the left hand side. For instance, below is our definition of pi, followed by our definition of area:

Prelude> let pi = 3.14159265358979323846264338327950
Prelude> let area r = pi * r ^ 2

To calculate the area of our two circles, we simply pass it different values:

Prelude> area 5
78.53981633974483
Prelude> area 25
1963.4954084936207

Functions allow us to make a great leap forward in the reusability of our code. But let's slow down for a moment, or rather, back up to dissect things. See the r in our definition area r = ...? This is what we call a parameter. A parameter is what we use to provide input to the function. It's something that the function depends on, like here the area depends on the radius. When Haskell is interpreting the function, the value of its parameter must come from the outside. In the case of area, the value of r is 5 when you say area 5, but it is 25 if you say area 25.

Prelude> let r = 0
Prelude> let area r = pi * r ^ 2
Prelude> area 5

Scope and parameters

Warning: this section contains spoilers to the previous exercise

We hope you have completed the very short exercise (I would say thought experiment) above. Fortunately, the following fragment of code does not contain any unpleasant surprises:

Prelude> let r = 0
Prelude> let area r = pi * r ^ 2
Prelude> area 5
78.53981633974483

An unpleasant surprise here would have been getting the value 0. This is just a consequence of what we wrote above, namely the value of a parameter is strictly what you pass in when you call the function. And that is directly a consequence of our old friend scope. Informally, the r in let r = 0 is not the same r as the one inside our defined function area - the r inside area overrides the other r; you can think of it as Haskell picking the most specific version of r there is. If you have many friends all named John, you go with the one which just makes more sense and is specific to the context; similarly, what value of r we get depends on the scope.

Multiple parameters

Another thing you might want to know about functions is that they can accept more than one parameter. Say for instance, you want to calculate the area of a rectangle. This is quite simple to express:

Prelude> let areaRect l w = l * w
Prelude> areaRect 5 10
50

Or say you want to calculate the area of a right triangle :

Prelude> let areaRtTriangle b h = (b * h) / 2
Prelude> areaRtTriangle 3 9
13.5

Passing parameters in is pretty straightforward: you just give them in the same order that they are defined. So, whereas areaRtTriangle 3 9 gives us the area of a triangle with base 3 and height 9, areaRtTriangle 9 3 gives us the area with the base 9 and height 3.

Functions within functions

To further cut down the amount of repetition, it is possible to call functions from within other functions. A simple example showing how this can be used is to create a function to compute the area of a square. We can think of a square as a special case of a rectangle (the area is still the width multiplied by the length); however, we also know that the width and length are the same, so why should we need to type it in twice?

Prelude> let areaRect l w = l * w
Prelude> let areaSquare s = areaRect s s
Prelude> areaSquare 5
25

Summary

1. Variables store values. In fact, they store any arbitrary Haskell expression.
2. Variables do not change.
3. Functions help you write reusable code.
4. Functions can accept more than one parameter.

Notes

1. ↑ For readers with prior programming experience: Variables don't change? I only get constants? Shock! Horror! No... trust us, as we hope to show you in the rest of this book, you can go a very long way without changing a single variable! In fact, this non-changing of variables makes life easier because it makes programs so much more predictable.

Lists and tuples

Lists and tuples are two ways of binding several values down into a single value.

Lists

The functional programmer's next best friend

In the last section we introduced the concept of variables and functions in Haskell. Functions are one of the two major building blocks of any Haskell program. The other is the versatile list. So, without further ado, let's switch over to the interpreter and build some lists:

Example - Building Lists in the Interpreter

Prelude> let numbers = [1,2,3,4]
Prelude> let truths  = [True, False, False]
Prelude> let strings = ["here", "are", "some", "strings"]

The square brackets denote the beginning and the end of the list. List elements are separated by the comma "," operator. Further, list elements must be all of the same type. Therefore, [42, "life, universe and everything else"] is not a valid list because it contains two elements of different types, namely, integer and string respectively. However, [12, 80] or, ["beer", "sandwiches"] are valid lists because they are both type-homogeneous.

Here is what happens if you try to define a list with mixed-type elements:

Prelude> let mixed = [True, "bonjour"]

<interactive>:1:19:
    Couldn't match `Bool' against `[Char]'
      Expected type: Bool
      Inferred type: [Char]
    In the list element: "bonjour"
    In the definition of `mixed': mixed = [True, "bonjour"]

If you're confused about this business of lists and types, don't worry about it. We haven't talked very much about types yet and we are confident that this will clear up as the book progresses.

Building lists

Square brackets and commas aren't the only way to build up a list. Another thing you can do with them is to build them up piece by piece, by consing^[1] things on to them, via the (:) operator.

Example: Consing something on to a list

Prelude> let numbers = [1,2,3,4]
Prelude> numbers
[1,2,3,4]
Prelude> 0:numbers
[0,1,2,3,4]

When you cons something on to a list (something:someList), what you get back is another list. So, unsurprisingly, you could keep on consing your way up.

Example: Consing lots of things to a list

Prelude> 1:0:numbers
[1,0,1,2,3,4]
Prelude> 2:1:0:numbers
[2,1,0,1,2,3,4]
Prelude> 5:4:3:2:1:0:numbers
[5,4,3,2,1,0,1,2,3,4]

In fact, this is just about how all lists are built, by consing them up from the empty list ([]). The commas and brackets notation is actually a pleasant form or syntactic sugar. In other words, a list like [1,2,3,4,5] is exactly equivalent to 1:2:3:4:5:[]

You will, however, want to watch out for a potential pitfall in list construction. Whereas 1:2:[] is perfectly good Haskell, 1:2 is not. In fact, if you try it out in the interpreter, you get a nasty error message.

Example: Whoops!

Prelude> 1:2

<interactive>:1:2:
    No instance for (Num [a])
      arising from the literal `2' at <interactive>:1:2
    Probable fix: add an instance declaration for (Num [a])
    In the second argument of `(:)', namely `2'
    In the definition of `it': it = 1 : 2

Well, to be fair, the error message is nastier than usual because numbers are slightly funny beasts in Haskell. Let's try this again with something simpler, but still wrong, True:False

Example: Simpler but still wrong

Prelude> True:False

<interactive>:1:5:
    Couldn't match `[Bool]' against `Bool'
      Expected type: [Bool]
      Inferred type: Bool
    In the second argument of `(:)', namely `False'
    In the definition of `it': it = True : False

The basic intuition for this is that the cons operator, (:) works with this pattern something:someList ; however, what we gave it is more something:somethingElse. Cons only knows how to stick things onto lists. We're starting to run into a bit of reasoning about types. Let's summarize so far:

• The elements of the list must have the same type.
• You can only cons (:) something onto a list.

Well, sheesh, aren't types annoying? They are indeed, but as we will see in Type basics, they can also be a life saver. In either case, when you are programming in Haskell and something blows up, you'll probably want to get used to thinking "probably a type error".

Lists within lists

Lists can contain anything, just as long as they are all of the same type. Well, then, chew on this: lists are things too, therefore, lists can contain... yes indeed, other lists! Try the following in the interpreter:

Example: Lists can contain lists

Prelude> let listOfLists = [[1,2],[3,4],[5,6]] 
Prelude> listOfLists
[[1,2],[3,4],[5,6]]

Lists of lists can be pretty tricky sometimes, because a list of things does not have the same type as a thing all by itself. Let's sort through these implications with a few exercises:

Lists of lists are extremely useful, because they allow you to express some very complicated, structured data (two-dimensional matrices, for example). They are also one of the places where the Haskell type system truly shines. Human programmers, or at least this wikibook author, get confused all the time when working with lists of lists, and having restrictions of types often helps in wading through the potential mess.

Tuples

A different notion of many

Tuples are another way of storing multiple values in a single value, but they are subtly different in a number of ways. They are useful when you know, in advance, how many values you want to store, and they lift the restriction that all the values have to be of the same type. For example, we might want a type for storing pairs of coordinates. We know how many elements there are going to be (two: an x and y coordinate), so tuples are applicable. Or, if we were writing a phonebook application, we might want to crunch three values into one: the name, phone number and address of someone. Again, we know how many elements there are going to be. Also, those three values aren't likely to have the same type, but that doesn't matter here, because we're using tuples.

Let's look at some sample tuples.

Example: Some tuples

(True, 1)
("Hello world", False)
(4, 5, "Six", True, 'b')

The first example is a tuple containing two elements. The first one is True and the second is 1. The next example again has two elements, the first is "Hello world" and the second, False. The third example is a bit more complex. It's a tuple consisting of five elements, the first is 4 (a number), the second 5 (another number), the third "Six" (a string), the fourth True (a boolean value), and the last one 'b' (a character). So the syntax for tuples is: separate the different elements with a comma, and surround the whole thing in parentheses.

A quick note on nomenclature: in general you write n-tuple for a tuple of size n. 2-tuples (that is, tuples with 2 elements) are normally called 'pairs' and 3-tuples triples. Tuples of greater sizes aren't actually all that common, although, if you were to logically extend the naming system, you'd have 'quadruples', 'quintuples' and so on, hence the general term 'tuple'.

So tuples are a bit like lists, in that they can store multiple values. However, there is a very key difference: pairs don't have the same type as triples, and triples don't have the same type as quadruples, and in general, two tuples of different sizes have different types. You might be getting a little disconcerted because we keep mentioning this word 'type', but for now, it's just important to grasp how lists and tuples differ in their approach to sizes. You can have, say, a list of numbers, and add a new number on the front, and it remains a list of numbers. If you have a pair and wish to add a new element, it becomes a triple, and this is a fundamentally different object ^[2].

What are tuples for?

Tuples are handy when you want to return more than one value from a function. In most languages trying to return two or more things at once means wrapping them up in a special data structure, maybe one that only gets used in that function. In Haskell, just return them as a tuple.

Haskell records often serve the same purpose but you would have to specify the names of the components then. We'll meet up with records on the way.

You can also use tuples as a primitive kind of data structure. But that needs an understanding of types, which we haven't covered yet.

Getting data out of tuples

In this section, we concentrate solely on pairs. This is mostly for simplicity's sake, but pairs are far and away the most commonly used size of tuple.

Okay, so we've seen how we can put values into tuples, simply by using the (x, y, z) syntax. How can we get them out again? For example, a typical use of tuples is to store the (x, y) coordinate pair of a point: imagine you have a chess board, and want to specify a specific square. You could do this by labeling all the rows from 1 to 8, and similarly with the columns, then letting, say, (2, 5) represent the square in row 2 and column 5. Say we want to define a function for finding all the pieces in a given row. One way of doing this would be to find the coordinates of all the pieces, then look at the row part and see if it's equal to whatever row we're being asked to examine. This function would need, once it had the coordinate pair (x, y) of a piece, to extract the x (the row part). To do this there are two functions, fst and snd, which project the first and second elements out of a pair, respectively (in math-speak, a function that gets some data out of a structure is called a "Projection"). Let's see some examples:

Example: Using fst and snd

Prelude> fst (2, 5)
2
Prelude> fst (True, "boo")
True
Prelude> snd (5, "Hello")
"Hello"

It should be fairly obvious what these functions do. Note that you can only use these functions on pairs. Why? It all harks back to the fact that tuples of different sizes are different beasts entirely. fst and snd are specialized to pairs, and so you can't use them on anything else ^[3].

The general technique for extracting a component out of a tuple is pattern matching (yep, we'll talk about it in great detail later on, as this is one of the distinctive features of functional languages). Without making things more complicated than they ought to be at this point, let me just show you how I can write a function named first that does the same thing as fst:

Example: The definition of first

 Prelude> let first (x, y) = x
 Prelude> first (3, True) 
 3

This just says that given a pair (x, y), first (x, y) gives you x.

Tuples within tuples (and other combinations)

We can apply the same reasoning to tuples about storing lists within lists. Tuples are things too, so you can store tuples with tuples (within tuples up to any arbitrary level of complexity). Likewise, you could also have lists of tuples, tuples of lists, all sorts of combinations along the same lines.

Example: Nesting tuples and lists

((2,3), True)
((2,3), [2,3])
[(1,2), (3,4), (5,6)]

Some discussion about this - what you get out of this, maybe, what's the big idea behind grouping things together

There is one bit of trickiness to watch out for, however. The type of a tuple is defined not only by its size, but by the types of objects it contains. For example, the tuples ("Hello",32) and (47,"World") are fundamentally different. One is of type (String,Int), whereas the other is (Int,String). This has implications for building up lists of tuples. We could very well have lists like [("a",1),("b",9),("c",9)], but having a list like [("a",1),(2,"b"),(9,"c")] is right out. Can you spot the difference?

Summary

We have introduced two new notions in this chapter, lists and tuples. To sum up:

1. Lists are defined by square brackets and commas : [1,2,3].
   • They can contain anything as long as all the candidate elements of the list are of the same type
   • They can also be built by the cons operator, (:), but you can only cons things onto lists
2. Tuples are defined by parentheses and commas : ("Bob",32)
   • They can contain anything, even things of different types
   • They have a fixed length, or at least their length is encoded in their type. That is, two tuples with different lengths will have different types.
3. Lists and tuples can be combined in any number of ways: lists within lists, tuples with lists, etc

We hope that at this point, you're somewhat comfortable enough manipulating them as part of the fundamental Haskell building blocks (variables, functions and lists), because we're now going to move to some potentially heady topics, types and recursion. We have alluded to types thrice in this chapter without really saying what they are, so these shall be the next major topic that we cover. But before we get to that, we're going to make a short detour to help you make better use of the GHC interpreter.

Notes

1. ↑ You might object that that isn't even a proper word. Well, it isn't. Among programmers, the tradition started from LISP, to call this specific task of appending an element in front of a list "consing". The verb here is "cons", which happens to be a mnemonic for "constructor", as it is the way lists are constructed.
2. ↑ At least as far as types are concerned, but we're trying to avoid that word :)
3. ↑ More technically, fst and snd have types which limit them to pairs. It would be impossible to define projection functions on tuples in general, because they'd have to be able to accept tuples of different sizes, so the type of the function would vary.

Notes

Next steps

Haskell files

Up to now, we've made heavy use of the GHC interpreter. The interpreter is indeed a useful tool for trying things out quickly and for debugging your code. But we're getting to the point where typing everything directly into the interpreter isn't very practical. So now, we'll be writing our first Haskell source files.

Open up a file Varfun.hs in your favourite text editor (the hs stands for Haskell) and paste the following definition in. Haskell uses indentations and spaces to decide where functions (and other things) begin and end, so make sure there are no leading spaces and that indentations are correct, otherwise GHC will report parse errors.

area r = pi * r^2

(In case you're wondering, pi is actually predefined in Haskell, no need to include it here). Now change into the directory where you saved your file, open up ghci, and use :load (or :l for short):

Prelude> :load Varfun.hs
Compiling Main             ( Varfun.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

If ghci gives an error, "Could not find module 'Varfun.hs'", then use :cd to change the current directory to the directory containing Varfun.hs:

Prelude> :cd c:\myDirectory
Prelude> :load Varfun.hs
Compiling Main             ( Varfun.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

Now you can execute the bindings found in that file:

*Main> area 5
78.53981633974483

If you make changes to the file, just use :reload (:r for short) to reload the file.

You'll note that there are a couple of differences between how we do things when we type them directly into ghci, and how we do them when we load them from files. The differences may seem awfully arbitrary for now, but they're actually quite sensible consequences of the scope, which, rest assured, we will explain later.

No let

For starters, you no longer say something like

let x = 3
let y = 2
let area r = pi * r ^ 2

Instead, you say things like

x = 3
y = 2
area r = pi * r ^ 2

The keyword let is actually something you use a lot in Haskell, but not exactly in this context. We'll see further on in this chapter when we discuss the use of let bindings.

You can't define the same thing twice

Previously, the interpreter cheerfully allowed us to write something like this

Prelude> let r = 5
Prelude> r
5
Prelude> let r = 2
Prelude> r
2

On the other hand, writing something like this in a source file does not work

-- this does not work
r = 5
r = 2

As we mentioned above, variables do not change, and this is even more the case when you're working in a source file. This has one very nice implication. It means that:

Order does not matter

The order in which you declare things does not matter. For example, the following fragments of code do exactly the same thing:

 y = x * 2
 x = 3

 x = 3
 y = x * 2

This is a unique feature of Haskell and other functional programming languages. The fact that variables never change means that we can opt to write things in any order that we want (but this is also why you can't declare something more than once... it would be ambiguous otherwise).

More about functions

Working with actual source code files instead of typing things into the interpreter makes it convenient to define much more substantial functions than those we've seen up to now. Let's flex some Haskell muscle here and examine the kinds of things we can do with our functions.

Conditional expressions

if / then / else

Haskell supports standard conditional expressions. For instance, we could define a function that returns − 1 if its argument is less than 0; 0 if its argument is 0; and 1 if its argument is greater than 0. Actually, such a function already exists (called the signum function), but let's define one of our own, what we'll call mySignum.

mySignum x =
    if x < 0 then 
        -1
    else if x > 0 then 
        1
    else 
        0

You can experiment with this as:

Example:

*Main> mySignum 5
1
*Main> mySignum 0
0
*Main> mySignum (5-10)
-1
*Main> mySignum (-1)
-1

Note that the parenthesis around "-1" in the last example are required; if missing, the system will think you are trying to subtract the value "1" from the value "mySignum," which is ill-typed.

The if/then/else construct in Haskell is very similar to that of most other programming languages; however, you must have both a then and an else clause. It evaluates the condition (in this case x < 0) and, if this evaluates to True, it evaluates the then condition; if the condition evaluated to False, it evaluates the else condition.

You can test this program by editing the file and loading it back into your interpreter. Instead of typing :l Varfun.hs again, you can simply type :reload or just :r to reload the current file. This is usually much faster.

case

Haskell, like many other languages, also supports case constructions. These are used when there are multiple values that you want to check against (case expressions are actually quite a bit more powerful than this -- see the Pattern matching chapter for all of the details).

Suppose we wanted to define a function that had a value of 1 if its argument were 0; a value of 5 if its argument were 1; a value of 2 if its argument were 2; and a value of − 1 in all other instances. Writing this function using if statements would be long and very unreadable; so we write it using a case statement as follows (we call this function f):

f x =
    case x of
      0 -> 1
      1 -> 5
      2 -> 2
      _ -> -1

In this program, we're defining f to take an argument x and then inspecting the value of x. If it matches 0, the value of f is 1. If it matches 1, the value of f is 5. If it matches 2, then the value of f is 2; and if it hasn't matched anything by that point, the value of f is − 1 (the underscore can be thought of as a "wildcard" -- it will match anything).

The indentation here is important. Haskell uses a system called "layout" to structure its code (the programming language Python uses a similar system). The layout system allows you to write code without the explicit semicolons and braces that other languages like C and Java require.

Because whitespace matters in Haskell, you need to be careful about whether you are using tabs or spaces. If you can configure your editor to never use tabs, that's probably better. If not, make sure your tabs are always 8 spaces long, or you're likely to run into problems.

Indentation

The general rule for layout is that an open-brace is inserted after the keywords where, let, do and of, and the column position at which the next command appears is remembered. From then on, a semicolon is inserted before every new line that is indented the same amount. If a following line is indented less, a close-brace is inserted. This may sound complicated, but if you follow the general rule of indenting after each of those keywords, you'll never have to remember it (see the Indentation chapter for a more complete discussion of layout).

Some people prefer not to use layout and write the braces and semicolons explicitly. This is perfectly acceptable. In this style, the above function might look like:

f x = case x of
        { 0 -> 1 ; 1 -> 5 ; 2 -> 2 ; _ -> -1 }

Of course, if you write the braces and semicolons explicitly, you're free to structure the code as you wish. The following is also equally valid:

f x =
    case x of { 0 -> 1 ;
      1 -> 5 ; 2 -> 2
   ; _ -> -1 }

However, structuring your code like this only serves to make it unreadable (in this case).

Defining one function for different parameters

Functions can also be defined piece-wise, meaning that you can write one version of your function for certain parameters and then another version for other parameters. For instance, the above function f could also be written as:

f 0 = 1
f 1 = 5
f 2 = 2
f _ = -1

Just like in the case case above, order is important. If we had put the last line first, it would have matched every argument, and f would return -1, regardless of its argument (most compilers will warn you about this, though, saying something about overlapping patterns). If we had not included this last line, f would produce an error if anything other than 0, 1 or 2 were applied to it (most compilers will warn you about this, too, saying something about incomplete patterns). This style of piece-wise definition is very popular and will be used quite frequently throughout this tutorial. These two definitions of f are actually equivalent -- this piece-wise version is translated into the case expression.

Function composition

More complicated functions can be built from simpler functions using function composition. Function composition is simply taking the result of the application of one function and using that as an argument for another. We've already seen this back in the Getting set up chapter, when we wrote 5*4+3. In this, we were evaluating 5 * 4 and then applying + 3 to the result. We can do the same thing with our square and f functions:

square x = x^2

Example:

*Main> square (f 1)
25
*Main> square (f 2)
4
*Main> f (square 1)
5
*Main> f (square 2)
-1

The result of each of these function applications is fairly straightforward. The parentheses around the inner function are necessary; otherwise, in the first line, the interpreter would think that you were trying to get the value of square f, which has no meaning. Function application like this is fairly standard in most programming languages. There is another, more mathematical way to express function composition: the (.) enclosed period function. This (.) function is modeled after the () operator in mathematics.

The (.) function (called the function composition function), takes two functions and makes them into one. For instance, if we write (square . f), this means that it creates a new function that takes an argument, applies f to that argument and then applies square to the result. Conversely, (f . square) means that a new function is created that takes an argument, applies square to that argument and then applies f to the result. We can see this by testing it as before:

Example:

*Main> (square . f) 1
25
*Main> (square . f) 2
4
*Main> (f . square) 1
5
*Main> (f . square) 2
-1

Here, we must enclose the function composition in parentheses; otherwise, the Haskell compiler will think we're trying to compose square with the value f 1 in the first line, which makes no sense since f 1 isn't even a function.

It would probably be wise to take a little time-out to look at some of the functions that are defined in the Prelude. Undoubtedly, at some point, you will accidentally rewrite some already-existing function (I've done it more times than I can count), but if we can keep this to a minimum, that would save a lot of time.

Let Bindings

Often we wish to provide local declarations for use in our functions. For instance, if you remember back to your grade school mathematics courses, the following formula is used to find the roots (zeros) of a polynomial of the form ax² + bx + c:

.

We could write the following function to compute the two values of x:

roots a b c =
    ((-b + sqrt(b*b - 4*a*c)) / (2*a),
     (-b - sqrt(b*b - 4*a*c)) / (2*a))

Notice that our definition here has a bit of redundancy. It is not quite as nice as the mathematical definition because we have needlessly repeated the code for sqrt(b*b - 4*a*c). To remedy this problem, Haskell allows for local bindings. That is, we can create values inside of a function that only that function can see. For instance, we could create a local binding for sqrt(b*b-4*a*c) and call it, say, disc and then use that in both places where sqrt(b*b - 4*a*c) occurred. We can do this using a let/in declaration:

roots a b c =
    let disc = sqrt (b*b - 4*a*c)
    in  ((-b + disc) / (2*a),
         (-b - disc) / (2*a))

In fact, you can provide multiple declarations inside a let. Just make sure they're indented the same amount, or you will have layout problems:

roots a b c =
    let disc = sqrt (b*b - 4*a*c)
        twice_a = 2*a
    in  ((-b + disc) / twice_a,
         (-b - disc) / twice_a)

Type basics

Types in programming are a way of grouping similar values. In Haskell, the type system is a powerful way of ensuring there are fewer mistakes in your code.

Introduction

Programming deals with different sorts of entities. For example, consider adding two numbers together:

2 + 3

What are 2 and 3? They are numbers, clearly. But how about the plus sign in the middle? That's certainly not a number. So what is it?

Similarly, consider a program that asks you for your name, then says "Hello". Neither your name nor the word Hello is a number. What are they then? We might refer to all words and sentences and so forth as Text. In fact, it's more normal in programming to use a slightly more esoteric word, that is, String.

If you've ever set up a database before, you'll likely have come across types. For example, say we had a table in a database to store details about a person's contacts; a kind of personal telephone book. The contents might look like this:

The fields contain values. Sherlock is a value as is 99 Long Road Street Villestown as well as 655523. As we've said, types are a way of grouping different sorts of data. What do we have in the above table? Two of the columns, First name and Last name contain text, so we say that the values are of type String. The type of the third column is a dead giveaway by its name, Telephone number. Values in that column have the type of Number!

At first glance one may be tempted to class address as a string. However, the semantics behind an innocent address are quite complex. There are a whole lot of human conventions that dictate. For example, if the first line contains a number, then that's the number of the house, if not, then it's probably the name of the house, except if the line begins with PO Box then it's just a postal box address and doesn't indicate where the person lives at all... Clearly, there's more going on here than just Text. We could say that addresses are Text; there'd be nothing wrong with that. However, claiming they're of some different type, say, Address, is more powerful. If we know some piece of data has the type of Text, that's not very helpful. However, if we know it has the type of Address, we instantly know much more about the piece of data.

We might also want to apply this line of reasoning to our telephone number column. Indeed, it would be a good idea to come up with a TelephoneNumber type. Then if we were to come across some arbitrary sequence of digits, knowing that sequence of digits was of type TelephoneNumber, we would have access to a lot more information than if it were just a Number.

Another reason to not consider the TelephoneNumber as a Number is that numbers are arithmetic entities allowing them to be used for computing other numbers. What then would be the meaning and expected effect of adding 1 to a TelephoneNumber? It would not allow calling anyone by phone. That's a good enough reason why you would like a stronger type than just a mere Number. Also, each digit comprising a telephone number is important, it's not acceptable to lose some of them, by rounding it, or even by omitting some leading zeroes. Other reasons would be that telephone numbers can't be used the same way from different locations, so you may also need to specify within a TelephoneNumber value some other information like an area number or a country prefix. One good way to specify that is to provide some abstraction for telephone numbers and to design your database with a separate type instead of just Number.

Why types are useful

So far, what we've done just seems like categorizing things -- hardly a feature that would cause every modern programming language designer to incorporate types into their language! In the next section we explore how Haskell uses types to the programmer's benefit.

Using the interactive :type command

Characters and strings

The best way to explore how types work in Haskell is from GHCi. Let's get it up and running and get to know the :type command.

Example: Using the :type command in GHCi on a literal character

Prelude> :type 'H'
'H' :: Char

(The :type can be also shortened to :t, which we shall use from now on.)

And there we have it. You give GHCi an expression and it returns its type. In this case we gave it the literal value 'H' - the letter H enclosed in single quotation marks (a.k.a. apostrophe, ANSI 39) and GHCi printed it followed by the "::" symbol which reads "is of type" followed by Char. The whole thing reads: 'H' is of type Char.

If we try to give it a string of characters, we need to enclose them in quotation marks:

Example: Using the :t command in GHCi on a literal string

Prelude> :t "Hello World"
"Hello World" :: [Char]

In this case we gave it some text enclosed in double quotation marks and GHCi printed "Hello World" :: [Char]. [Char] means a list of characters. Notice the difference between Char and [Char] - the square brackets are used to construct literal lists, and they are also used to describe the list type.

This is essentially what strings are in Haskell - lists of characters. A string in Haskell can be initialized in several ways: It may be entered as a sequence of characters enclosed in double quotation marks (ANSI 34); it may also be constructed similar to any other list, that is, as individual elements of type Char joined together with the ":" function and terminated by an empty list, or built with individual Char values enclosed in brackets and separated by commas.

So, for the final time, what precisely is this concept of text that we're throwing around? One way of interpreting it is to say it's basically a sequence of characters. Think about it: the word "Hey" is just the character 'H' followed by the character 'e' followed by the character 'y'. Haskell uses a list to hold this sequence of characters. Square brackets indicate a list of things, for example here [Char] means 'a list of Chars'.

Haskell has a concept of type synonyms. Just as in the English language, two words that mean the same thing, for example 'fast' and 'quick', are called synonyms, in Haskell two types which are exactly the same are called 'type synonyms'. Everywhere you can use [Char], you can use String. So to say:

"Hello World" :: String

Is also perfectly valid. From here on we'll mostly refer to text as String, rather than [Char].

Boolean values

One of the other types found in most languages is called a Boolean, or Bool for short. This has two values: true and false. This turns out to be very useful. For example, consider a program that would ask the user for a name then look that name up in a spreadsheet. It might be useful to have a function, nameExists, which indicates whether or not the name of the user exists in the spreadsheet. If it does exist, you could say that it is true that the name exists, and if not, you could say that it is false that the name exists. So we've come across Bools. The two values of bools are, as we've mentioned, true and false. In Haskell, boolean values are capitalized (for reasons that will later become clear):

Example: Exploring the types of True and False in GHCi

Prelude> :t True
True :: Bool
Prelude> :t False
False :: Bool

This shouldn't need too much explaining at this point. The values True and False are categorized as Booleans, that is to say, they have type Bool.

Numeric types

If you've been playing around with typing :t on all the familiar values you've come across, perhaps you've run into the following complication:

Prelude> :t 5
5 :: (Num t) => t

We'll defer the full explanation of this until later. The short version of the story is that there are many different types of numbers (fractions, whole numbers, etc) and 5 can be any one of them. This weird-looking type relates to a Haskell feature called type classes, which we will be playing with later in this book.

Functional types

So far, the types we have talked about apply to values (strings, booleans, characters, etc), and we have explained how types not only help to categorize them, but also describe them. The next thing we'll look at is what makes the type system truly powerful: We can assign types not only to values, but to functions as well^[1]. Let's look at some examples.

Example: not

Example: Negating booleans

not True  = False
not False = True

not is a standard Prelude function that simply negates Bools, in the sense that truth turns into falsity and vice versa. For example, taking the above example we gave using Bools, nameExists, we could define a similar function that would test whether a name doesn't exist in the spreadsheet. It would likely look something like this:

Example: nameDoesntExist: using not

nameDoesntExist name = not (nameExists name)

To assign a type to not we look at two things: the type of values it takes as its input, and the type of values it returns. In our example, things are easy. not takes a Bool (the Bool to be negated), and returns a Bool (the negated Bool). Therefore, we write that:

Example: Type signature for not

not :: Bool -> Bool

You can read this as 'not is a function from things of type Bool to things of type Bool'.

Example: unlines and unwords

A common programming task is to take a list of Strings, then join them all up into a single string, but insert a newline character between each one, so they all end up on different lines. For example, say you had the list ["Bacon", "Sausages", "Egg"], and wanted to convert it to something resembling a shopping list, the natural thing to do would be to join the list together into a single string, placing each item from the list onto a new line. This is precisely what unlines does. unwords is similar, but it uses a space instead of a newline as a separator. (mnemonic: un = unite)

Example: unlines and unwords

Prelude> unlines ["Bacon", "Sausages", "Egg"]
"Bacon\nSausages\nEgg\n"
Prelude> unwords ["Bacon", "Sausages", "Egg"]
"Bacon Sausages Egg"

Notice the weird output from unlines. This isn't particularly related to types, but it's worth noting anyway, so we're going to digress a little and explore why this is. Basically, any output from GHCi is first run through the show function, which converts it into a String. This makes sense, because GHCi shows you the result of your commands as text, so it has to be a String. However, what does show do if you give it something which is already a String? Although the obvious answer would be 'do nothing', the behaviour is actually slightly different: any 'special characters', like tabs, newlines and so on in the String are converted to their 'escaped forms', which means that rather than a newline actually making the stuff following it appear on the next line, it is shown as "\n". To avoid this, we can use the putStrLn function, which GHCi sees and doesn't run your output through show.

Example: Using putStrLn in GHCi

Prelude> putStrLn (unlines ["Bacon", "Sausages", "Egg"])
Bacon
Sausages
Egg

Prelude> putStrLn (unwords ["Bacon", "Sausages", "Egg"])
Bacon Sausages Egg

The second result may look identical, but notice the lack of quotes. putStrLn outputs exactly what you give it (actually putStrLn appends a newline character to its input before printing it; the function putStr outputs exactly what you give it). Also, note that you can only pass it a String. Calls like putStrLn 5 will fail. You'd need to convert the number to a String first, that is, use show: putStrLn (show 5) (or use the equivalent function print: print 5).

Getting back to the types. What would the types of unlines and unwords be? Well, again, let's look at both what they take as an argument, and what they return. As we've just seen, we've been feeding these functions a list, and each of the items in the list has been a String. Therefore, the type of the argument is [String]. They join all these Strings together into one long String, so the return type has to be String. Therefore, both of the functions have type [String] -> String. Note that we didn't mention the fact that the two functions use different separators. This is totally inconsequential when it comes to types — all that matters is that they return a String. The type of a String with some newlines is precisely the same as the type of a String with some spaces.

Example: chr and ord

Text presents a problem to computers. Once everything is reduced to its lowest level, all a computer knows how to deal with is 1s and 0s: computers work in binary. As working with binary isn't very convenient, humans have come up with ways of making computers store text. Every character is first converted to a number, then that number is converted to binary and stored. Hence, a piece of text, which is just a sequence of characters, can be encoded into binary. Normally, we're only interested in how to encode characters into their numerical representations, because the number to binary bit is very easy.

The easiest way of converting characters to numbers is simply to write all the possible characters down, then number them. For example, we might decide that 'a' corresponds to 1, then 'b' to 2, and so on. This is exactly what a thing called the ASCII standard is: 128 of the most commonly-used characters, numbered. Of course, it would be a bore to sit down and look up a character in a big lookup table every time we wanted to encode it, so we've got two functions that can do it for us, chr (pronounced 'char') and ord ^[2]:

Example: Type signatures for chr and ord

chr :: Int  -> Char
ord :: Char -> Int

Remember earlier when we stated Haskell has many numeric types? The simplest is Int, which represents integers. ^[3] So what do the above type signatures say? Recall how the process worked for not above. We look at the type of the function's argument, then at the type of the function's result. In the case of chr (find the character corresponding to a specific numeric encoding), the type signature tells us that it takes arguments of type Int and has a result of type Char. The converse is the case with ord (find the specific numeric encoding for a given character): it takes things of type Char and returns things of type Int.

To make things more concrete, here are a few examples of function calls to chr and ord, so you can see how the types work out. Notice that the two functions aren't in the standard prelude, but instead in the Data.Char module, so you have to load that module with the :m (or :module) command.

Example: Function calls to chr and ord

Prelude> :m Data.Char
Prelude Data.Char> chr 97
'a'
Prelude Data.Char> chr 98
'b'
Prelude Data.Char> ord 'c'
99

Functions in more than one argument

So far, we've only worked with functions that take a single argument. This isn't very interesting! For example, the following is a perfectly valid Haskell function, but what would its type be?

Example: A function in more than one argument

f x y = x + 5 + 2 * y

As we've said a few times, there's more than one type for numbers, but we're going to cheat here and pretend that x and y have to be Ints.

The general technique for forming the type of a function in more than one argument, then, is to just write down all the types of the arguments in a row, in order (so in this case x first then y), then write -> in between all of them. Finally, add the type of the result to the end of the row and stick a final -> in just before it. So in this case, we have:

FIXME: use images here.

1. Write down the types of the arguments. We've already said that x and y have to be Ints, so it becomes:

   Int             Int
   ^^ x is an Int  ^^ y is an Int as well
   

2. Fill in the gaps with ->:

   Int -> Int
   

3. Add in the result type and a final ->. In our case, we're just doing some basic arithmetic so the result remains an Int.

   Int -> Int -> Int
                 ^^ We're returning an Int
       ^^ There's the extra -> that got added in 
   

Real-World Example: openWindow

As you'll learn in the Practical Haskell section of the course, one popular group of Haskell libraries are the GUI ones. These provide functions for dealing with all the parts of Windows or Linux you're familiar with: opening and closing application windows, moving the mouse around etc. One of the functions from one of these libraries is called openWindow, and you can use it to open a new window in your application. For example, say you're writing a word processor like Microsoft Word, and the user has clicked on the 'Options' button. You need to open a new window which contains all the options that they can change. Let's look at the type signature for this function ^[4]:

Example: openWindow

openWindow :: WindowTitle -> WindowSize -> Window

Don't panic! Here are a few more types you haven't come across yet. But don't worry, they're quite simple. All three of the types there, WindowTitle, WindowSize and Window are defined by the GUI library that provides openWindow. As we saw when constructing the types above, because there are two arrows, the first two types are the types of the parameters, and the last is the type of the result. WindowTitle holds the title of the window (what appears in the blue bar (XP and before) or black translucent bar (Vista) - you didn't change the color, did you? - at the top), and WindowSize specifies how big the window should be. The function then returns a value of type Window which you can use to get information on and manipulate the window.

Polymorphic types

So far all we've looked at are functions and values with a single type. However, if you start playing around with :t in GHCi you'll quickly run into things that don't have types beginning with the familiar capital letter. For example, there's a function that finds the length of a list, called (rather predictably) length. Remember that [Foo] is a list of things of type Foo. However, we'd like length to work on lists of any type. I.e. we'd rather not have a lengthInts :: [Int] -> Int, as well as a lengthBools :: [Bool] -> Int, as well as a lengthStrings :: [String] -> Int, as well as a...

That's too complicated. We want one single function that will find the length of any type of list. The way Haskell does this is using type variables. For example, the actual type of length is as follows:

Example: Our first polymorphic type

length :: [a] -> Int

The "a" you see there in the square brackets is called a type variable. Type variables begin with a lowercase letter. Indeed, this is why types have to begin with an uppercase letter — so they can be distinguished from type variables. When Haskell sees a type variable, it allows any type to take its place. This is exactly what we want. In type theory (a branch of mathematics), this is called polymorphism: functions or values with only a single type (like all the ones we've looked at so far except length) are called monomorphic, and things that use type variables to admit more than one type are therefore polymorphic.

Example: fst and snd

As we saw, you can use the fst and snd functions to extract parts of pairs. By this time you should be in the habit of thinking "What type is that function?" about every function you come across. Let's examine fst and snd. First, a few sample calls to the functions:

Example: Example calls to fst and snd

Prelude> fst (1, 2) 
1
Prelude> fst ("Hello", False)
"Hello"
Prelude> snd (("Hello", False), 4)
4

To begin with, let's point out the obvious: these two functions take a pair as their parameter and return one part of this pair. The important thing about pairs, and indeed tuples in general, is that they don't have to be homogeneous with respect to types; their different parts can be different types. Indeed, that is the case in the second and third examples above. If we were to say:

fst :: (a, a) -> a

That would force the first and second part of input pair to be the same type. That illustrates an important aspect to type variables: although they can be replaced with any type, they have to be replaced with the same type everywhere. So what's the correct type? Simply:

Example: The types of fst and snd

fst :: (a, b) -> a
snd :: (a, b) -> b

Note that if you were just given the type signatures, you might guess that they return the first and second parts of a pair, respectively. In fact this is not necessarily true, they just have to return something with the same type of the first and second parts of the pair.

Type signatures in code

Now we've explored the basic theory behind types as well as how they apply to Haskell, let's look at how they appear in code. Most Haskell programmers will annotate every function they write with its associated type. That is, you might be writing a non-annotated module that looks something like this:

Example: Module without type signatures

module StringManip where

import Data.Char

uppercase = map toUpper
lowercase = map toLower
capitalise x = 
  let capWord []     = []
      capWord (x:xs) = toUpper x : xs
  in unwords (map capWord (words x))

This is a small library that provides some frequently used string manipulation functions. uppercase converts a string to uppercase, lowercase to lowercase, and capitalize capitalizes the first letter of every word. Providing a type for these functions makes it more obvious what they do. For example, most Haskellers would write the above module something like the following:

Example: Module with type signatures

module StringManip where

import Data.Char

uppercase, lowercase :: String -> String
uppercase = map toUpper
lowercase = map toLower

capitalise :: String -> String
capitalise x = 
  let capWord []     = []
      capWord (x:xs) = toUpper x : xs
  in unwords (map capWord (words x))

Note that you can group type signatures together into a single type signature (like ours for uppercase and lowercase above) if the two functions share the same type.

Type inference

So far, we've explored types by using the :t command in GHCi. However, before you came across this chapter, you were still managing to write perfectly good Haskell code, and it has been accepted by the compiler. In other words, it's not necessary to add type signatures. However, if you don't add type signatures, that doesn't mean Haskell simply forgets about typing altogether! Indeed, when you didn't tell Haskell the types of your functions and variables, it worked them out. This is a process called type inference, whereby the compiler starts with the types of things it knows, then works out the types of the rest of the things. Type inference for Haskell is decidable, which means that the compiler can always work out the types, even if you never write them in ^[5]. Let's look at some examples to see how the compiler works out types.

Example: Simple type inference

-- We're deliberately not providing a type signature for this function
isL c = c == 'l'

This function takes a character and sees if it is an 'l' character. The compiler derives the type for isL something like the following:

Example: A typing derivation

(==)  :: a -> a -> Bool
'l'   :: Char
Replacing the second ''a'' in the signature for (==) with the type of 'l':
(==)  :: Char -> Char -> Bool
isL   :: Char -> Bool

The first line indicates that the type of the function (==), which tests for equality, is a -> a -> Bool ^[6]. (We include the function name in parentheses because it's an operator: its name consists only of non-alphanumeric characters. More on this later.) The compiler also knows that something in 'single quotes' has type Char, so clearly the literal 'l' has type Char. Next, the compiler starts replacing the type variables in the signature for (==) with the types it knows. Note that in one step, we went from a -> a -> Bool to Char -> Char -> Bool, because the type variable a was used in both the first and second argument, so they need to be the same. And so we arrive at a function that takes a single argument (whose type we don't know yet, but hold on!) and applies it as the first argument to (==). We have a particular instance of the polymorphic type of (==), that is, here, we're talking about (==) :: Char -> Char -> Bool because we know that we're comparing Chars. Therefore, as (==) :: Char -> Char -> Bool and we're feeding the parameter into the first argument to (==), we know that the parameter has the type of Char. Phew!

But wait, we're not finished yet! What's the return type of the function? Thankfully, this bit is a bit easier. We've fed two Chars into a function which (in this case) has type Char -> Char -> Bool, so we must have a Bool. Note that the return value from the call to (==) becomes the return value of our isL function.

So, let's put it all together. isL is a function that takes a single argument. We discovered that this argument must be of type Char. Finally, we derived that we return a Bool. So, we can confidently say that isL has the type:

Example: isL with a type

isL :: Char -> Bool
isL c = c == 'l'

And, indeed, if you miss out the type signature, the Haskell compiler will discover this on its own, using exactly the same method we've just run through.

Reasons to use type signatures

So if type signatures are optional, why bother with them at all? Here are a few reasons:

• Documentation: the most prominent reason is that it makes your code easier to read. With most functions, the name of the function along with the type of the function is sufficient to guess at what the function does. (Of course, you should always comment your code anyway.)
• Debugging: if you annotate a function with a type, then make a typo in the body of the function, the compiler will tell you at compile-time that your function is wrong. Leaving off the type signature could have the effect of allowing your function to compile, and the compiler would assign it an erroneous type. You wouldn't know until you ran your program that it was wrong. In fact, this is so important, let's explore it some more.

Types prevent errors

Imagine you have a few functions set up like the following:

Example: Type inference at work

fiveOrSix :: Bool -> Int
fiveOrSix True  = 5
fiveOrSix False = 6

pairToInt :: (Bool, String) -> Int
pairToInt x = fiveOrSix (fst x)

Our function fiveOrSix takes a Bool. When pairToInt receives its arguments, it knows, because of the type signature we've annotated it with, that the first element of the pair is a Bool. So, we could extract this using fst and pass that into fiveOrSix, and this would work, because the type of the first element of the pair and the type of the argument to fiveOrSix are the same.

This is really central to typed languages. When passing expressions around you have to make sure the types match up like they did here. If they don't, you'll get type errors when you try to compile; your program won't typecheck. This is really how types help you to keep your programs bug-free. To take a very trivial example:

Example: A non-typechecking program

"hello" + " world"

Having that line as part of your program will make it fail to compile, because you can't add two strings together! More likely, you wanted to use the string concatenation operator, which joins two strings together into a single one:

Example: Our erroneous program, fixed

"hello" ++ " world"

An easy typo to make, but because you use Haskell, it was caught when you tried to compile. You didn't have to wait until you ran the program for the bug to become apparent.

This was only a simple example. However, the idea of types being a system to catch mistakes works on a much larger scale too. In general, when you make a change to your program, you'll change the type of one of the elements. If this change isn't something that you intended, then it will show up immediately. A lot of Haskell programmers remark that once they have fixed all the type errors in their programs, and their programs compile, that they tend to 'just work': function flawlessly first time, with only minor problems. Run-time errors, where your program goes wrong when you run it rather than when you compile it, are much rarer in Haskell than in other languages. This is a huge advantage of a strong type system like Haskell's.

Notes

1. ↑ In fact, these are one and the same concept in Haskell.
2. ↑ This isn't quite what chr and ord do, but that description fits our purposes well, and it's close enough.
3. ↑ To make things even more confusing, there's actually even more than one type for integers! Don't worry, we'll come on to this in due course.
4. ↑ This has been somewhat simplified to fit our purposes. Don't worry, the essence of the function is there.
5. ↑ Some of the newer type system extensions to GHC do break this, however, so you're better off just always putting down types anyway.
6. ↑ This is a slight lie. That type signature would mean that you can compare two values of any type whatsoever, but this clearly isn't true: how can you see if two functions are equal? Haskell includes a kind of 'restricted polymorphism' that allows type variables to range over some, but not all types. Haskell implements this using type classes, which we'll learn about later. In this case, the correct type of (==) is Eq a => a -> a -> Bool.

Simple input and output

So far this tutorial has discussed functions that return values, which is well and good. But how do we write "Hello world"? To give you a first taste of it, here is a small variant of the "Hello world" program:

Example: Hello! What is your name?

main = do
  putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")

At the very least, what should be clear is that dealing with input and output (IO) in Haskell is not a lost cause! Functional languages have always had a problem with input and output because they require side effects. Functions always have to return the same results for the same arguments. But how can a function "getLine" return the same value every time it is called? Before we give the solution, let's take a step back and think about the difficulties inherent in such a task.

Any IO library should provide a host of functions, containing (at a minimum) operations like:

• print a string to the screen
• read a string from a keyboard
• write data to a file
• read data from a file

There are two issues here. Let's first consider the initial two examples and think about what their types should be. Certainly the first operation (I hesitate to call it a "function") should take a String argument and produce something, but what should it produce? It could produce a unit (), since there is essentially no return value from printing a string. The second operation, similarly, should return a String, but it doesn't seem to require an argument.

We want both of these operations to be functions, but they are by definition not functions. The item that reads a string from the keyboard cannot be a function, as it will not return the same String every time. And if the first function simply returns () every time, then referential transparency tells us we should have no problem with replacing it with a function f _ = (). But clearly this does not have the desired effect.

Actions

The breakthrough for solving this problem came when Philip Wadler realized that monads would be a good way to think about IO computations. In fact, monads are able to express much more than just the simple operations described above; we can use them to express a variety of constructions like concurrence, exceptions, IO, non-determinism and much more. Moreover, there is nothing special about them; they can be defined within Haskell with no special handling from the compiler (though compilers often choose to optimize monadic operations). Monads also have a somewhat undeserved reputation of being difficult to understand. So we're going to leave things at that -- knowing simply that IO somehow makes use of monads without necessarily understanding the gory details behind them (they really aren't so gory). So for now, we can forget that monads even exist.

As pointed out before, we cannot think of things like "print a string to the screen" or "read data from a file" as functions, since they are not (in the pure mathematical sense). Therefore, we give them another name: actions. Not only do we give them a special name, we give them a special type. One particularly useful action is putStrLn, which prints a string to the screen. This action has type:

putStrLn :: String -> IO ()

As expected, putStrLn takes a string argument. What it returns is of type IO (). This means that this function is actually an action (that is what the IO means). Furthermore, when this action is evaluated (or "run") , the result will have type ().

You can probably already guess the type of getLine:

getLine :: IO String

This means that getLine is an IO action that, when run, will have type String.

The question immediately arises: "how do you 'run' an action?". This is something that is left up to the compiler. You cannot actually run an action yourself; instead, a program is, itself, a single action that is run when the compiled program is executed. Thus, the compiler requires that the main function have type IO (), which means that it is an IO action that returns nothing. The compiled code then executes this action.

However, while you are not allowed to run actions yourself, you are allowed to combine actions. There are two ways to go about this. The one we will focus on in this chapter is the do notation, which provides a convenient means of putting actions together, and allows us to get useful things done in Haskell without having to understand what really happens. Lurking behind the do notation is the more explicit approach using the (>>=) operator, but we will not be ready to cover this until the chapter Understanding monads.

Let's consider the following name program:

Example: What is your name?

main = do
  putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")

We can consider the do notation as a way to combine a sequence of actions. Moreover, the <- notation is a way to get the value out of an action. So, in this program, we're sequencing three actions: a putStrLn, a getLine and another putStrLn. The putStrLn action has type String -> IO (), so we provide it a String, so the fully applied action has type IO (). This is something that we are allowed to run as a program.

The base?
3.3
The height?
5.4
The area of that triangle is 8.91

Left arrow clarifications

The <- is optional

While we are allowed to get a value out of certain actions like getLine, we certainly are not obliged to do so. For example, we could very well have written something like this:

Example: executing getLine directly

main = do
  putStrLn "Please enter your name: "
  getLine
  putStrLn ("Hello, how are you?")

Clearly, that isn't very useful: the whole point of prompting the user for his or her name was so that we could do something with the result. That being said, it is conceivable that one might wish to read a line and completely ignore the result. Omitting the <- will allow for that; the action will happen, but the data won't be stored anywhere.

In order to get the value out of the action, we write name <- getLine, which basically means "run getLine, and put the results in the variable called name."

The <- can be used with any action (except the last)

On the flip side, there are also very few restrictions which actions can have values obtained from them. Consider the following example, where we put the results of each action into a variable (except the last... more on that later):

Example: putting all results into a variable

main = do
  x <- putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")

The variable x gets the value out of its action, but that isn't very interesting because the action returns the unit value (). So while we could technically get the value out of any action, it isn't always worth it. But wait, what about that last action? Why can't we get a value out of that? Let's see what happens when we try:

Example: getting the value out of the last action

main = do
  x <- putStrLn "Please enter your name: "
  name <- getLine
  y <- putStrLn ("Hello, " ++ name ++ ", how are you?")

Whoops!

YourName.hs:5:2:
    The last statement in a 'do' construct must be an expression

This is a much more interesting example, but it requires a somewhat deeper understanding of Haskell than we currently have. Suffice it to say, whenever you use <- to get the value of an action, Haskell is always expecting another action to follow it. So the very last action better not have any <-s.

Controlling actions

Normal Haskell constructions like if/then/else and case/of can be used within the do notation, but you need to be somewhat careful. For instance, in a simple "guess the number" program, we have:

    doGuessing num = do
       putStrLn "Enter your guess:"
       guess <- getLine
       if (read guess) < num
         then do putStrLn "Too low!"
                 doGuessing num
         else if (read guess) > num
                then do putStrLn "Too high!"
                        doGuessing num
                else do putStrLn "You Win!"

If we think about how the if/then/else construction works, it essentially takes three arguments: the condition, the "then" branch, and the "else" branch. The condition needs to have type Bool, and the two branches can have any type, provided that they have the same type. The type of the entire if/then/else construction is then the type of the two branches.

In the outermost comparison, we have (read guess) < num as the condition. This clearly has the correct type. Let's just consider the "then" branch. The code here is:

              do putStrLn "Too low!"
                 doGuessing num

Here, we are sequencing two actions: putStrLn and doGuessing. The first has type IO (), which is fine. The second also has type IO (), which is fine. The type result of the entire computation is precisely the type of the final computation. Thus, the type of the "then" branch is also IO (). A similar argument shows that the type of the "else" branch is also IO (). This means the type of the entire if/then/else construction is IO (), which is just what we want.

It is incorrect to think to yourself "Well, I already started a do block; I don't need another one," and hence write something like:

    do if (read guess) < num
         then putStrLn "Too low!"
              doGuessing num
         else ...

Here, since we didn't repeat the do, the compiler doesn't know that the putStrLn and doGuessing calls are supposed to be sequenced, and the compiler will think you're trying to call putStrLn with three arguments: the string, the function doGuessing and the integer num. It will certainly complain (though the error may be somewhat difficult to comprehend at this point).

We can write the same doGuessing function using a case statement. To do this, we first introduce the Prelude function compare, which takes two values of the same type (in the Ord class) and returns one of GT, LT, EQ, depending on whether the first is greater than, less than or equal to the second.

doGuessing num = do
  putStrLn "Enter your guess:"
  guess <- getLine
  case compare (read guess) num of
    LT -> do putStrLn "Too low!"
             doGuessing num
    GT -> do putStrLn "Too high!"
             doGuessing num
    EQ -> putStrLn "You Win!"

Here, again, the dos after the ->s are necessary on the first two options, because we are sequencing actions.

If you're used to programming in an imperative language like C or Java, you might think that return will exit you from the current function. This is not so in Haskell. In Haskell, return simply takes a normal value (for instance, one of type Int) and makes it into an action that returns the given value (for the same example, the action would be of type IO Int). In particular, in an imperative language, you might write this function as:

void doGuessing(int num) {
  print "Enter your guess:";
  int guess = atoi(readLine());
  if (guess == num) {
    print "You win!";
    return ();
  }

  // we won't get here if guess == num
  if (guess < num) {
    print "Too low!";
    doGuessing(num);
  } else {
    print "Too high!";
    doGuessing(num);
  }
}

Here, because we have the return () in the first if match, we expect the code to exit there (and in most imperative languages, it does). However, the equivalent code in Haskell, which might look something like:

doGuessing num = do
  putStrLn "Enter your guess:"
  guess <- getLine
  case compare (read guess) num of
    EQ -> do putStrLn "You win!"
             return ()

  -- we don't expect to get here if guess == num
  if (read guess < num)
    then do print "Too low!";
            doGuessing num
    else do print "Too high!";
            doGuessing num

First of all, if you guess correctly, it will first print "You win!," but it won't exit, and it will check whether guess is less than num. Of course it is not, so the else branch is taken, and it will print "Too high!" and then ask you to guess again.

On the other hand, if you guess incorrectly, it will try to evaluate the case statement and get either LT or GT as the result of the compare. In either case, it won't have a pattern that matches, and the program will fail immediately with an exception.

main =
 do x <- getX
    putStrLn x

getX =
 do return "hello"
    return "aren't"
    return "these"
    return "returns"
    return "rather"
    return "pointless?"

Actions under the microscope

Actions may look easy up to now, but they are actually a common stumbling block for new Haskellers. If you have run into trouble working with actions, you might consider looking to see if one of your problems or questions matches the cases below. It might be worth skimming this section now, and coming back to it when you actually experience trouble.

Mind your action types

One temptation might be to simplify our program for getting a name and printing it back out. Here is one unsuccessful attempt:

Example: Why doesn't this work?

main =
 do putStrLn "What is your name? "
    putStrLn ("Hello " ++ getLine)

Ouch!

YourName.hs:3:26:
    Couldn't match expected type `[Char]'
           against inferred type `IO String'

Let us boil the example above down to its simplest form. Would you expect this program to compile?

Example: This still does not work

main =
 do putStrLn getLine

For the most part, this is the same (attempted) program, except that we've stripped off the superflous "What is your name" prompt as well as the polite "Hello". One trick to understanding this is to reason about it in terms of types. Let us compare:

putStrLn :: String -> IO ()
getLine  :: IO String

We can use the same mental machinery we learned in Type basics to figure how everything went wrong. Simply put, putStrLn is expecting a String as input. We do not have a String, but something tantalisingly close, an IO String. This represents an action that will give us a String when it's run. To obtain the String that putStrLn wants, we need to run the action, and we do that with the ever-handy left arrow, <-.

Example: This time it works

main =
 do name <- getLine
    putStrLn name

Working our way back up to the fancy example:

main =
 do putStrLn "What is your name? "
    name <- getLine
    putStrLn ("Hello " ++ name)

Now the name is the String we are looking for and everything is rolling again.

Mind your expression types too

Fine, so we've made a big deal out of the idea that you can't use actions in situations that don't call for them. The converse of this is that you can't use non-actions in situations that DO expect actions. Say we want to greet the user, but this time we're so excited to meet them, we just have to SHOUT their name out:

Example: Exciting but incorrect. Why?

import Data.Char (toUpper)

main =
 do name <- getLine
    loudName <- makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)

-- Don't worry too much about this function; it just capitalises a String
makeLoud :: String -> String
makeLoud s = map toUpper s

This goes wrong...

    Couldn't match expected type `IO' against inferred type `[]'
      Expected type: IO t
      Inferred type: String
    In a 'do' expression: loudName <- makeLoud name

This is quite similar to the problem we ran into above: we've got a mismatch between something that is expecting an IO type, and something which is not. This time, the cause is our use of the left arrow <-; we're trying to left arrow a value of makeLoud name, which really isn't left arrow material. It's basically the same mismatch we saw in the previous section, except now we're trying to use regular old String (the loud name) as an IO String, which clearly are not the same thing. The latter is an action, something to be run, whereas the former is just an expression minding its own business. Note that we cannot simply use loudName = makeLoud name because a do sequences actions, and loudName = makeLoud name is not an action.

So how do we extricate ourselves from this mess? We have a number of options:

• We could find a way to turn makeLoud into an action, to make it return IO String. But this is not desirable, because the whole point of functional programming is to cleanly separate our side-effecting stuff (actions) from the pure and simple stuff. For example, what if we wanted to use makeLoud from some other, non-IO, function? An IO makeLoud is certainly possible (how?), but missing the point entirely.
• We could use return to promote the loud name into an action, writing something like loudName <- return (makeLoud name). This is slightly better, in that we are at least leaving the makeLoud function itself nice and IO-free, whilst using it in an IO-compatible fashion. But it's still moderately clunky, because by virtue of left arrow, we're implying that there's action to be had -- how exciting! -- only to let our reader down with a somewhat anticlimatic return
• Or we could use a let binding...

It turns out that Haskell has a special extra-convenient syntax for let bindings in actions. It looks a little like this:

Example: let bindings in do blocks.

main =
 do name <- getLine
    let loudName = makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)

If you're paying attention, you might notice that the let binding above is missing an in. This is because let bindings in do blocks do not require the in keyword. You could very well use it, but then you'd have to make a mess of your do blocks. For what it's worth, the following two blocks of code are equivalent.

 do name <- getLine
    let loudName = makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)

 do name <- getLine
    let loudName = makeLoud name
    in  do putStrLn ("Hello " ++ loudName ++ "!")
           putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)

Learn more

At this point, you should have the skills you need to do some fancier input/output. Here are some IO-related options to consider.

• You could continue the sequential track, by learning more about types and eventually monads.
• Alternately: you could start learning about building graphical user interfaces in the GUI chapter
• For more IO-related functionality, you could also consider learning more about the System.IO library

Type declarations



Haskell has three basic ways to declare a new type:

• The data declaration for structures and enumerations.
• The type declaration for type synonyms.
• The newtype declaration, which is a cross between the other two.

In this chapter, we will focus on the most essential way, data, and to make life easier, type. You'll find out about newtype later on, but don't worry too much about it; it's there mainly for optimisation.

data for making your own types

Here is a data structure for a simple list of anniversaries:

data Anniversary = Birthday String Int Int Int       -- name, year, month, day
                 | Wedding String String Int Int Int -- first name, second name, year, month, day

This declares a new data type Anniversary with two constructor functions called Birthday and Wedding. As usual with Haskell the case of the first letter is important: type names and constructor functions must always start with capital letters. Note also the vertical bar: this marks the point where one alternative ends and the next begins; you can think of it almost as an or - which you'll remember was || - except used in types.

The declaration says that an Anniversary can be one of two things; a Birthday or a Wedding. A Birthday contains one string and three integers, and a Wedding contains two strings and three integers. The comments (after the "--") explain what the fields actually mean.

Now we can create new anniversaries by calling the constructor functions. For example, suppose we have John Smith born on 3rd July 1968:

johnSmith :: Anniversary
johnSmith = Birthday "John Smith" 1968 7 3

He married Jane Smith on 4th March 1987:

smithWedding :: Anniversary
smithWedding = Wedding "John Smith" "Jane Smith" 1987 3 4

These two objects can now be put in a list:

anniversaries :: [Anniversary]
anniversaries = [johnSmith, smithWedding]

(Obviously a real application would not hard-code its entries: this is just to show how constructor functions work).

Constructor functions can do all of the things ordinary functions can do. Anywhere you could use an ordinary function you can use a constructor function.

Anniversaries will need to be converted into strings for printing. This needs another function:

showAnniversary :: Anniversary -> String

showAnniversary (Birthday name year month day) =
   name ++ " born " ++ showDate year month day

showAnniversary (Wedding name1 name2 year month day) =
   name1 ++ " married " ++ name2 ++ " " ++ showDate year month day

This shows the one way that constructor functions are special: they can also be used to deconstruct objects. showAnniversary takes an argument of type Anniversary. If the argument is a Birthday then the first version gets used, and the variables name, month, date and year are bound to its contents. If the argument is a Wedding then the second version is used and the arguments are bound in the same way. The parentheses indicate that the whole thing is one argument split into five or six parts, rather than five or six separate arguments.

Notice the relationship between the type and the constructors. All versions of showAnniversary convert an Anniversary to a String. One of them handles the Birthday case and the other handles the Wedding case.

It also needs an additional showDate routine:

showDate y m d = show y ++ "-" ++ show m ++ "-" ++ show d

Of course, it's a bit clumsy having the date passed around as three separate integers. What we really need is a new datatype:

data Date = Date Int Int Int   -- Year, Month, Day

Constructor functions are allowed to be the same name as the type, and if there is only one then it is good practice to make it so.

type for making type synonyms

It would also be nice to make it clear that the strings in the Anniversary type are names, but still be able to manipulate them like ordinary strings. The type declaration does this:

type Name = String

This says that a Name is a synonym for a String. Any function that takes a String will now take a Name as well, and vice versa. The right hand side of a type declaration can be a more complex type as well. For example String itself is defined in the standard libraries as

type String = [Char]

So now we can rewrite the Anniversary type like this:

data Anniversary = 
   Birthday Name Date
   | Wedding Name Name Date

which is a lot easier to read. We can also have a type for the list:

type AnniversaryBook = [Anniversary]

The rest of the code needs to be changed to match:

johnSmith :: Anniversary
johnSmith = Birthday "John Smith" (Date 1968 7 3)

smithWedding :: Anniversary
smithWedding = Wedding "John Smith" "Jane Smith" (Date 1987 3 4)

anniversaries :: AnniversaryBook
anniversaries = [johnSmith, smithWedding]


showAnniversary :: Anniversary -> String

showAnniversary (Birthday name date) =
   name ++ " born " ++ showDate date

showAnniversary (Wedding name1 name2 date) =
   name1 ++ " married " ++ name2 ++ showDate date


showDate :: Date -> String
showDate (Date y m d) = show y ++ "-" ++ show m ++ "-" ++ show d

Elementary Haskell

Recursion

Recursion is a clever idea which plays a central role in Haskell (and computer science in general): namely, recursion is the idea of using a given function as part of its own definition. A function defined in this way is said to be recursive. It might sound like this always leads to infinite regress, but if done properly it doesn't have to.

Generally speaking, a recursive definition comes in two parts. First, there are one or more base cases which say what to do in simple cases where no recursion is necessary (that is, when the answer can be given straightaway without recursively calling the function being defined). This ensures that the recursion can eventually stop. The recursive case is more general, and defines the function in terms of a 'simpler' call to itself. Let's look at a few examples.

Numeric recursion

The factorial function

In mathematics, especially combinatorics, there is a function used fairly frequently called the factorial function ^[1]. It takes a single number as an argument, finds all the numbers between one and this number, and multiplies them all together. For example, the factorial of 6 is 1 × 2 × 3 × 4 × 5 × 6 = 720. This is an interesting function for us, because it is a candidate to be written in a recursive style.

The idea is to look at the factorials of adjacent numbers:

Example: Factorials of adjacent numbers

Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 =     5 × 4 × 3 × 2 × 1

Notice how we've lined things up. You can see here that the factorial of 6 involves the factorial of 5. In fact, the factorial of 6 is just 6 × (factorial of 5). Let's look at some more examples:

Example: Factorials of adjacent numbers

Factorial of 3 = 3 × 2 × 1
Factorial of 2 =     2 × 1

Factorial of 8 = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
Factorial of 7 =     7 × 6 × 5 × 4 × 3 × 2 × 1

Indeed, we can see that the factorial of any number is just that number multiplied by the factorial of the number one less than it. There's one exception to this: if we ask for the factorial of 0, we don't want to multiply 0 by the factorial of -1! In fact, we just say the factorial of 0 is 1 (we define it to be so. It just is, okay?^[2]). So, 0 is the base case for the recursion: when we get to 0 we can immediately say that the answer is 1, without using recursion. We can summarize the definition of the factorial function as follows:

• The factorial of 0 is 1.
• The factorial of any other number is that number multiplied by the factorial of the number one less than it.

We can translate this directly into Haskell:

Example: Factorial function

factorial 0 = 1
factorial n = n * factorial (n-1)

This defines a new function called factorial. The first line says that the factorial of 0 is 1, and the second one says that the factorial of any other number n is equal to n times the factorial of n-1. Note the parentheses around the n-1: without them this would have been parsed as (factorial n) - 1; function application (applying a function to a value) will happen before anything else does (we say that function application binds more tightly than anything else).

This function must be defined in a file, rather than using let statements in the interpreter. The latter will cause the function to be redefined with the last definition, losing the important first definition and leading to infinite recursion.

This all seems a little voodoo so far. How does it work? Well, let's look at what happens when you execute factorial 3:

• 3 isn't 0, so we recur: work out the factorial of 2
  • 2 isn't 0, so we recur.
    • 1 isn't 0, so we recur.
      • 0 is 0, so we return 1.
    • We multiply the current number, 1, by the result of the recursion, 1, obtaining 1 (1 × 1).
  • We multiply the current number, 2, by the result of the recursion, 1, obtaining 2 (2 × 1 × 1).
• We multiply the current number, 3, by the result of the recursion, obtaining 6 (3 × 2 × 1 × 1).

We can see how the multiplication 'builds up' through the recursion.

(Note that we end up with the one appearing twice, since the base case is 0 rather than 1; but that's okay since multiplying by one has no effect. We could have designed factorial to stop at 1 if we had wanted to, but it's conventional, and often useful, to have the factorial of 0 defined.)

One more thing to note about the recursive definition of factorial: the order of the two declarations (one for factorial 0 and one for factorial n) is important. Haskell decides which function definition to use by starting at the top and picking the first one that matches. In this case, if we had the general case (factorial n) before the 'base case' (factorial 0), then the general n would match anything passed into it -- including 0. So factorial 0 would match the general n case, the compiler would conclude that factorial 0 equals 0 * factorial (-1), and so on to negative infinity. Definitely not what we want. The lesson here is that one should always list multiple function definitions starting with the most specific and proceeding to the most general.

A quick aside

This section is aimed at people who are used to more imperative-style languages like C and Java.

Loops are the bread and butter of imperative languages. For example, the idiomatic way of writing a factorial function in an imperative language would be to use a for loop, like the following (in C):

Example: The factorial function in an imperative language

int factorial(int n) {
  int res = 1;
  for (i = 1; i <= n; i++)
    res *= i;
  return res;
}

This isn't directly possible in Haskell, since changing the value of the variables res and i (a destructive update) would not be allowed. However, you can always translate a loop into an equivalent recursive form. The idea is to make each loop variable in need of updating into a parameter of a recursive function. For example, here is a direct 'translation' of the above loop into Haskell:

Example: Using recursion to simulate a loop

factorial n = factorialWorker 1 n 1 where
factorialWorker i n res | i <= n    = factorialWorker (i+1) n (res * i)
                        | otherwise = res

The expressions after the vertical bars are called guards, and we'll learn more about them in the section on control structures. For now, you can probably figure out how they work by comparing them to the corresponding C code above.

Obviously this is not the shortest or most elegant way to implement factorial in Haskell (translating directly from an imperative paradigm into Haskell like this rarely is), but it can be nice to know that this sort of translation is always possible.

Another thing to note is that you shouldn't be worried about poor performance through recursion with Haskell. In general, functional programming compilers include a lot of optimization for recursion, including an important one called tail-call optimisation; remember too that Haskell is lazy -- if a calculation isn't needed, it won't be done. We'll learn about these in later chapters.

Other recursive functions

As it turns out, there is nothing particularly special about the factorial function; a great many numeric functions can be defined recursively in a natural way. For example, let's think about multiplication. When you were first introduced to multiplication (remember that moment? :)), it may have been through a process of 'repeated addition'. That is, 5 × 4 is the same as summing four copies of the number 5. Of course, summing four copies of 5 is the same as summing three copies, and then adding one more -- that is, 5 × 4 = 5 × 3 + 5. This leads us to a natural recursive definition of multiplication:

Example: Multiplication defined recursively

mult n 0 = 0                      -- anything times 0 is zero
mult n 1 = n                      -- anything times 1 is itself
mult n m = (mult n (m - 1)) + n   -- recur: multiply by one less, and add an extra copy

Stepping back a bit, we can see how numeric recursion fits into the general recursive pattern. The base case for numeric recursion usually consists of one or more specific numbers (often 0 or 1) for which the answer can be immediately given. The recursive case computes the result by recursively calling the function with a smaller argument and using the result in some manner to produce the final answer. The 'smaller argument' used is often one less than the current argument, leading to recursion which 'walks down the number line' (like the examples of factorial and mult above), but it doesn't have to be; the smaller argument could be produced in some other way as well.

List-based recursion

A lot of functions in Haskell turn out to be recursive, especially those concerning lists.^[3] Consider the length function that finds the length of a list:

Example: The recursive definition of length

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

Don't worry too much about the syntax; we'll learn more about it in the section on Pattern matching. For now, let's rephrase this code into English to get an idea of how it works. The first line gives the type of length: it takes any sort of list and produces an Int. The next line says that the length of an empty list is 0. This, of course, is the base case. The final line is the recursive case: if a list consists of a first element x and another list xs representing the rest of the list, the length of the list is one more than the length of xs.

How about the concatenation function (++), which joins two lists together? (Some examples of usage are also given, as we haven't come across this function so far in this chapter.)

Example: The recursive (++)

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"

(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

This is a little more complicated than length but not too difficult once you break it down. The type says that (++) takes two lists and produces another. The base case says that concatenating the empty list with a list ys is the same as ys itself. Finally, the recursive case breaks the first list into its head (x) and tail (xs) and says that to concatenate the two lists, concatenate the tail of the first list with the second list, and then tack the head x on the front.

There's a pattern here: with list-based functions, the base case usually involves an empty list, and the recursive case involves passing the tail of the list to our function again, so that the list becomes progressively smaller.

Recursion is used to define nearly all functions to do with lists and numbers. The next time you need a list-based algorithm, start with a case for the empty list and a case for the non-empty list and see if your algorithm is recursive.

Don't get TOO excited about recursion...

Although it's very important to have a solid understanding of recursion when programming in Haskell, one rarely has to write functions that are explicitly recursive. Instead, there are all sorts of standard library functions which perform recursion for you in various ways, and one usually ends up using those instead. For example, a much simpler way to implement the factorial function is as follows:

Example: Implementing factorial with a standard library function

factorial n = product [1..n]

Almost seems like cheating, doesn't it? :) This is the version of factorial that most experienced Haskell programmers would write, rather than the explicitly recursive version we started out with. Of course, the product function is using some list recursion behind the scenes^[4], but writing factorial in this way means you, the programmer, don't have to worry about it.

Summary

Recursion is the practise of using a function you're defining in the body of the function itself. It nearly always comes in two parts: a base case and a recursive case. Recursion is especially useful for dealing with list- and number-based functions.

Notes

1. ↑ In mathematics, n! normally means the factorial of n, but that syntax is impossible in Haskell, so we don't use it here.
2. ↑ Actually, defining the factorial of 0 to be 1 is not just arbitrary; it's because the factorial of 0 represents an empty product.
3. ↑ This is no coincidence; without mutable variables, recursion is the only way to implement control structures. This might sound like a limitation until you get used to it (it isn't, really).
4. ↑ Actually, it's using a function called foldl, which actually does the recursion.

Pattern matching

Pattern matching is a convenient way to bind variables to different parts of a given value.

What is pattern matching?

You've actually met pattern matching before, in the chapter about lists. Recall functions like map:

map _ []     = []
map f (x:xs) = f x : map f xs

Here there are four different patterns going on: two per equation. Let's explore each one in turn (although not in the order they appeared in that example):

• [] is a pattern that matches the empty list. It doesn't bind any variables.
• (x:xs) is a pattern that matches something (which gets bound to x), which is cons'd, using the function (:), onto something else (which gets bound to the variable xs).
• f is a pattern which matches anything at all, and binds f to that something.
• _ is the pattern which matches anything at all, but doesn't do any binding.

So pattern matching is a way of assigning names to things (or binding those names to those things), and possibly breaking down expressions into subexpressions at the same time (as we did with the list in the definition of map).

However, you can't pattern match with everything. For example, you might want to define a function like the following to chop off the first three elements of a list:

dropThree ([x,y,z] ++ xs) = xs

However, that won't work, and will give you an error. The problem is that the function (++) isn't allowed in patterns. So what is allowed?

The one-word answer is constructors. Recall algebraic datatypes, which look something like:

data Foo = Bar | Baz Int

Here Bar and Baz are constructors for the type Foo. And so you can pattern match with them:

f :: Foo -> Int
f Bar     = 1
f (Baz x) = x - 1

Remember that lists are defined thusly (note that the following isn't actually valid syntax: lists are in reality deeply grained into Haskell):

data [a] = [] | a : [a]

So the empty list, [], and the (:) function, are in reality constructors of the list datatype, so you can pattern match with them.

Note, however, that as [x, y, z] is just syntactic sugar for x:y:z:[], you can still pattern match using the latter form:

dropThree (_:_:_:xs) = xs

If the only relevant information is the type of the constructor (regardless of the number of its elements) the {} pattern can be used:

g :: Foo -> Bool
g Bar {} = True
g Baz {} = False

The function g does not have to be changed when the number of elements of the constructors Bar or Baz changes. Note: Foo does not have to be a record for this to work.

For constructors with many elements, it can help to use records:

data Foo2 = Bar2 | Baz2 {barNumber::Int, barName::String}

which then allows:

h :: Foo2 -> Int
h Baz2 {barName=name} = length name
h Bar2 {} = 0

The one exception

There is one exception to the rule that you can only pattern match with constructors. It's known as n+k patterns. It is indeed valid Haskell 98 to write something like:

pred :: Int -> Int
pred (n+1) = n

However, this is generally accepted as bad form and not many Haskell programmers like this exception, and so try to avoid it.

As-patterns

Sometimes, when matching a pattern with a value, it may be useful to bind a name also to the whole value being matched. As-patterns allow exactly this: they are of the form var@pattern and have the additional effect to bind the name var to the whole value being matched by pattern.

For instance, the following code snippet:

other_map f [] = []
other_map f list@(x:xs) = f x list : other_map f xs

creates a variant of map, called other_map, which passes to the parameter function f also the original list. Writing it without as-patterns would have been more cumbersome, because you must recreate the original value, i.e. x:xs:

other_map f [] = []
other_map f (x:xs) = f x (x:xs) : other_map f xs

The difference would be more notable with a more complex pattern.

Where you can use it

The short answer is that wherever you can bind variables, you can pattern match. Let's have a look at that more precisely.

Equations

The first place is in the left-hand side of function equations. For example, our above code for map:

map _ []     = []
map f (x:xs) = f x : map f xs

Here we're binding, and doing pattern-matching, on the left hand side of both of these equations.

Let expressions / Where clauses

You can obviously bind variables with a let expression or where clause. As such, you can also do pattern matching here. A trivial example:

let Just x = lookup "bar" [("foo", 1), ("bar", 2), ("baz", 3)] 

Case expressions

One of the most obvious places you can use pattern binding is on the left hand side of case branches:

case someRandomList of
  []     -> "The list was empty"
  (x:xs) -> "The list wasn't empty: the first element was " ++ show x ++ ", and " ++
            "there were " ++ show (length xs) ++ " more elements in the list."

Lambdas

As lambdas can be easily converted into functions, you can pattern match on the left-hand side of lambda expressions too:

head = (\(x:xs) -> x)

Note that here, along with on the left-hand side of equations as described above, you have to use parentheses around your patterns (unless they're just _ or are just a binding, not a pattern, like x).

List comprehensions

After the | in list comprehensions, you can pattern match. This is actually extremely useful. For example, the function catMaybes from Data.Maybe takes a list of Maybes, filters all the Just xs, and gets rid of all the Just wrappers. It's easy to write it using list comprehensions:

catMaybes :: [Maybe a] -> [a]
catMaybes ms = [ x | Just x <- ms ]

If the pattern match fails, it just moves on to the next element in ms. (More formally, as list comprehensions are just the list monad, a failed pattern match invokes fail, which is the empty list in this case, and so gets ignored.)

A few other places

That's mostly it, but there are one or two other places you'll find as you progress through the book. Here's a list in case you're very eager already:

• In p <- x in do-blocks, p can be a pattern.
• Similarly, with let bindings in do-blocks, you can pattern match analogously to 'real' let bindings.

More about lists



By now we have seen the basic tools for working with lists. We can build lists up from the cons operator (:) and the empty list [] (see Lists and tuples if you are unsure about this); and we can take them apart by using a combination of Recursion and Pattern matching. In this chapter, we will delve a little deeper into the inner-workings and the use of Haskell lists. We'll discover a little bit of new notation and some characteristically Haskell-ish features like infinite lists and list comprehensions. But before going into this, let us step back for a moment and combine the things we have already learned about lists.

Constructing Lists

We'll start by making a function to double every element of a list of integers. First, we must specify the type declaration for our function. For our purposes here, the function maps a list of integers to another list of integers:

doubleList :: [Integer] -> [Integer]

Then, we must specify the function definition itself. We'll be using a recursive definition, which consists of

1. the general case which iteratively generates a successive and simpler general case and
2. the base case, where iteration stops.

doubleList (n:ns) = (n * 2) : doubleList ns
doubleList [] = []

Since by definition, there are no more elements beyond the end of a list, intuition tells us iteration must stop at the end of the list. The easiest way to accomplish this is to return the null list: As a constant, it halts our iteration. As the empty list, it doesn't change the value of any list we append it to.

The general case requires some explanation. Remember that ":" is one of a special class of functions known as "constructors". The important thing about constructors is that they can be used to break things down as part of "pattern matching" on the left hand side of function definitions. In this case the argument passed to doubleList is broken down into the first element of the list (known as the "head") and the rest of the list (known as the "tail").

On the right hand side doubleList builds up a new list by using ":". It says that the first element of the result is twice the head of the argument, and the rest of the result is obtained by applying "doubleList" to the tail. Note the naming convention implicit in (n:ns). By appending an "s" to the element "n" we are forming its plural. The idea is that the head contains one item while the tail contains many, and so should be pluralised.

So what actually happens when we evaluate the following?

doubleList [1,2,3,4]

We can work this out longhand by substituting the argument into the function definition, just like schoolbook algebra:

doubleList 1:[2,3,4] = (1*2) : doubleList (2 : [3,4])
                     = (1*2) : (2*2) : doubleList (3 : [4])
                     = (1*2) : (2*2) : (3*2) : doubleList (4 : [])
                     = (1*2) : (2*2) : (3*2) : (4*2) : doubleList []
                     = (1*2) : (2*2) : (3*2) : (4*2) : []
                     = 2 : 4 : 6 : 8 : []
                     = [2, 4, 6, 8]

Notice how the definition for empty lists terminates the recursion. Without it, the Haskell compiler would have had no way to know what to do when it reached the end of the list.

Also notice that it would make no difference when we did the multiplications (unless one of them is an error or nontermination: we'll get to that later). If I had done them immediately it would have made absolutely no difference. This is an important property of Haskell: it is a "pure" functional programming language. Because evaluation order can never change the result, it is mostly left to the compiler to decide when to actually evaluate things. Haskell is a "lazy" evaluation language, so evaluation is usually deferred until the value is really needed, but the compiler is free to evaluate things sooner if this will improve efficiency. From the programmer's point of view evaluation order rarely matters (except in the case of infinite lists, of which more will be said shortly).

Of course a function to double a list has limited generality. An obvious generalization would be to allow multiplication by any number. That is, we could write a function "multiplyList" that takes a multiplicand as well as a list of integers. It would be declared like this:

multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList _ [] = []
multiplyList m (n:ns) = (m*n) : multiplyList m ns

This example introduces the "_", which is used for a "don't care" argument; it will match anything, like * does in shells or .* in regular expressions. The multiplicand is not used for the null case, so instead of being bound to an unused argument name it is explicitly thrown away, by "setting" _ to it. ("_" can be thought of as a write-only "variable".)

The type declaration needs some explanation. Hiding behind the rather odd syntax is a deep and clever idea. The "->" arrow is actually an operator for types, and is right associative. So if you add in the implied brackets the type definition is actually

multiplyList :: Integer -> ( [Integer] -> [Integer] )

Think about what this is saying. It means that "multiplyList" doesn't take two arguments. Instead it takes one (an Integer), and then returns a new function. This new function itself takes one argument (a list of Integers) and returns a new list of Integers. This process of functions taking one argument is called "currying", and is very important.

The new function can be used in a straightforward way:

evens = multiplyList 2 [1,2,3,4]

or it can do something which, in most other languages, would be an error; this is partial function application and because we're using Haskell, we can write the following neat & elegant bits of code:

doubleList = multiplyList 2
evens = doubleList [1,2,3,4]

It may help you to understand if you put the implied brackets in the first definition of "evens":

evens = (multiplyList 2) [1,2,3,4]

In other words "multiplyList 2" returns a new function that is then applied to [1,2,3,4].

Dot Dot Notation

Haskell has a convenient shorthand for specifying a list containing a sequence of integers. Some examples are enough to give the flavor:

Code             Result
----             ------
[1..10]          [1,2,3,4,5,6,7,8,9,10]
[2,4..10]        [2,4,6,8,10]
[5,4..1]         [5,4,3,2,1]
[1,3..10]        [1,3,5,7,9]

The same notation can be used for floating point numbers and characters as well. However, be careful with floating point numbers: rounding errors can cause unexpected things to happen. Try this:

[0,0.1 .. 1]

Similarly, there are limits to what kind of sequence can be written through dot-dot notation. You can't put in

[0,1,1,2,3,5,8..100]

and expect to get back the rest of the Fibonacci series, or put in the beginning of a geometric sequence like

[1,3,9,27..100]

Infinite Lists

One of the most mind-bending things about Haskell lists is that they are allowed to be infinite. For example, the following generates the infinite list of integers starting with 1:

[1..]

(If you try this in GHCi, remember you can stop an evaluation with Ctrl-c).

Or you could define the same list in a more primitive way by using a recursive function:

intsFrom n = n : intsFrom (n+1)
positiveInts = intsFrom 1

This works because Haskell uses lazy evaluation: it never actually evaluates more than it needs at any given moment. In most cases an infinite list can be treated just like an ordinary one. The program will only go into an infinite loop when evaluation would actually require all the values in the list. Examples of this include sorting or printing the entire list. However:

evens = doubleList [1..]
  

will define "evens" to be the infinite list [2,4,6,8....]. And you can pass "evens" into other functions, and it will all just work. See the exercise 4 below for an example of how to process an infinite list and then take the first few elements of the result.

Infinite lists are quite useful in Haskell. Often it's more convenient to define an infinite list and then take the first few items than to create a finite list. Functions that process two lists in parallel generally stop with the shortest, so making the second one infinite avoids having to find the length of the first. An infinite list is often a handy alternative to the traditional endless loop at the top level of an interactive program.

Deconstructing lists

So now we know how to generate lists by appending to the empty list, or using infinite lists and their notation. Very useful.

But what happens if our function is not generating a list and handing it off to some other function, but is rather receiving a list? It needs to be analyzed and broken down in some way.

For this purpose, Haskell includes the same basic functionality as other programming languages, except with better names than "car" or "cdr": the "head" and "tail" functions.

     head :: [a] -> a
     tail :: [a] -> [a]

From these two functions we can build pretty much all the functionality we want. If we want the first item in the list, a simple head will do:

Code            Result
----            ------
head [1,2,3]    1
head [5..100]   5

If we want the second item in a list, we have to be a bit clever: head gives the first item in a list, and tail effectively removes the first item in a list. They can be combined, though:

Code                	   Result
----			      ------
head(tail [1,2,3,4,5])        2
head(tail (tail [1,2,3,4,5])) 3

Enough tails can reach to arbitrary elements; usually this is generalized into a function which is passed a list and a number, which gives the position in a list to return.

List comprehensions

This is one further way to deconstruct lists; it is called a List comprehension. List comprehensions are useful and concise expressions, although they are fairly rare.

List comprehensions are basically syntactic sugar for a common pattern dealing with lists: when one wants to take a list and generate a new list composed only of elements of the first list that meet a certain condition.

One could write this out manually. For example, suppose one wants to take a list [1..10], and only retain the even numbers? One could handcraft a recursive function called retainEven, based on a test for evenness which we've already written called isEven:

            isEven :: Integer -> Bool 
            isEven n
                    | n < 0 = error "isEven needs a positive integer"
                    | ((mod n 2) == 0) = True  -- Even numbers have no remainder when divided by 2
                    | otherwise = False  -- If it has a remainder of anything but 0, it is not even

    retainEven :: [Integer] -> [Integer]
    retainEven []               = []
    retainEven (e:es) 
                     | isEven e  = e:retainEven es --If something is even, let's hang onto it
                     | otherwise = retainEven es --If something isn't even, discard it and move on

This is fairly verbose, though, and we had to go through a fair bit of effort and define an entirely new function just to accomplish the relatively simple task of filtering a list. Couldn't it be generalized? What we want to do is construct a new list with only the elements of an old list for which some boolean condition is true. Well, we could generalize our function writing above like this, involving the higher-order functions map and filter. For example, the above can also be written as

   retainEven es = filter isEven es

We can do this through the list comprehension form, which looks like this:

   retainEven es = [ n | n <- es , isEven n ]   

We can read the first half as an arbitrary expression modifying n, which will then be prepended to a new list. In this case, n isn't being modified, so we can think of this as repeatedly prepending the variable, like n:n:n:n:[] - but where n is different each time. n is drawn (the "<-") from the list es (a subtle point is that es can be the name of a list, or it can itself be a list).

Thus if es is equal to [1,2,3,4], then we would get back the list [2,4].

Suppose we wanted to subtract one from every even?

   evensMinusOne es = [n - 1 | n<-es , isEven n ]

We can do more than that, and list comprehensions can be easily modifiable. Perhaps we wish to generalize factoring a list, instead of just factoring it by evenness (that is, by 2). Well, given that ((mod n x) == 0) returns true for numbers n which are factorizable by x, it's obvious how to use it, no? Write a function using a list comprehension which will take an integer, and a list of integers, and return a list of integers which are divisible by the first argument. In other words, the type signature is thus:

returnFact :: Int -> [Int] -> [Int]

We can load the function, and test it with:

returnFact 10 [10..1000]

which should give us this:

*Main> returnFact 10 [10..1000]
[10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,....etc.]

Which is as it should be. But what if we want to write the opposite? What if we want to write a function which returns those integers which are not divisible? The modification is very simple, and the type signature the same. What decides whether a integer will be added to the list or not is the mod function, which currently returns true for those to be added. A simple 'not' suffices to reverse when it returns true, and so reverses the operation of the list:

rmFact :: Int -> [Int] -> [Int]
rmFact x ys = [n | n<-ys , (not ((mod n x) == 0))]

We can load it and give the equivalent test:

*Main> rmFact 10 [10..1000]
[11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,......etc.]

Of course this function is not perfect. We can still do silly things like

*Main> rmFact 0 [1..1000]
*** Exception: divide by zero

We can stack on more tests besides the one: maybe all our even numbers should be larger than 2:

   evensLargerThanTwo = [ n | n <- [1..10] , isEven n, n > 2 ]   

Fortunately, our Boolean tests are commutative, so it doesn't matter whether (n > 2) or (isEven 2) is evaluated first.

Pattern matching in list comprehensions

It's useful to note that the left arrow in list comprehensions can be used with pattern matching. For example, suppose we had a list of tuples [(Integer, Integer)]. What we would like to do is return the first element of every tuple whose second element is even. We could write it with a filter and a map, or we could write it as follows:

firstOfEvens xys = [ x | (x,y) <- xys, isEven y ]

And if we wanted to double those first elements:

doubleFirstOfEvens xys = [ 2 * x | (x,y) <- xys, isEven y ]

Control structures



Haskell offers several ways of expressing a choice between different values. This section will describe them all and explain what they are for:

if Expressions

You have already seen these. The full syntax is:

if <condition> then <true-value> else <false-value>

If the <condition> is True then the <true-value> is returned, otherwise the <false-value> is returned. Note that in Haskell if is an expression (returning a value) rather than a statement (to be executed). Because of this the usual indentation is different from imperative languages. If you need to break an if expression across multiple lines then you should indent it like one of these:

if <condition>
   then <true-value>
   else <false-value>

if <condition>
   then
      <true-value>
   else
      <false-value>

Here is a simple example:

message42 :: Integer -> String
message42 n =
   if n == 42
      then "The Answer is forty two."
      else "The Answer is not forty two."

Unlike many other languages, in Haskell the else is required. Since if is an expression, it must return a result, and the else ensures this.

case Expressions

case expressions are a generalization of if expressions. As an example, let's clone if as a case:

case <condition> of
     True  -> <true-value>
     False -> <false-value>
     _     -> error "Neither True nor False? File Not Found!"

First, this checks <condition> for a pattern match against True. If they match, the whole expression will evaluate to <true-value>, otherwise it will continue down the list. You can use _ as the pattern wildcard. In fact, the left hand side of any case branch is just a pattern, so it can also be used for binding:

case str of
   (x:xs) -> "The first character is " ++ [x] ++ "; the rest of the string is " ++ xs
   ""     -> "This is the empty string."

This expression tells you whether str is the empty string or something else. Of course, you could just do this with an if-statement (with a condition of null str), but using a case binds variables to the head and tail of our list, which is convenient in this instance.

Equations and Case Expressions

You can use multiple equations as an alternative to case expressions. The case expression above could be named describeString and written like this:

describeString :: String -> String
describeString (x:xs) = "The first character is " ++ [x] ++ "; the rest of the string is " ++ xs
describeString ""     = "This is the empty string."

Named functions and case expressions at the top level are completely interchangeable. In fact the function definition form shown here is just syntactic sugar for a case expression.

The handy thing about case expressions is that they can go inside other expressions, or be used in an anonymous function. TODO: this isn't really limited to case. For example, this case expression returns a string which is then concatenated with two other strings to create the result:

data Colour = Black | White | RGB Int Int Int

describeColour c = 
   "This colour is "
   ++ (case c of
          Black -> "black"
          White -> "white"
          RGB _ _ _ -> "freaky, man, sort of in between")
   ++ ", yeah?"

You can also put where clauses in a case expression, just as you can in functions:

describeColour c = 
   "This colour is "
   ++ (case c of
          Black -> "black"
          White -> "white"
          RGB red green blue -> "freaky, man, sort of " ++ show av
             where av = (red + green + blue) `div` 3
      )
   ++ ", yeah?"

Guards

As shown, if we have a top-level case expression, we can just give multiple equations for the function instead, which is normally neater. Is there an analogue for if expressions? It turns out there is.

We use some additonal syntax known as "guards". A guard is a boolean condition, like this:

describeLetter :: Char -> String
describeLetter c
   | c >= 'a' && c <= 'z' = "Lower case"
   | c >= 'A' && c <= 'Z' = "Upper case"
   | otherwise            = "Not a letter"

Note the lack of an = before the first |. Guards are evaluated in the order they appear. That is, if you have a set up similar to the following:

f (pattern1) | predicate1 = w
             | predicate2 = x
f (pattern2) | predicate3 = y
             | predicate4 = z

Then the input to f will be pattern-matched against pattern1. If it succeeds, then predicate1 will be evaluated. If this is true, then w is returned. If not, then predicate2 is evaluated. If this is true, then x is returned. Again, if not, then we jump out of this 'branch' of f and try to pattern match against pattern2, repeating the guards procedure with predicate3 and predicate4. If no guards match, an error will be produced at runtime, so it's always a good idea to leave an 'otherwise' guard in there to handle the "But this can't happen!" case.

The otherwise you saw above is actually just a normal value defined in the Standard Prelude as:

otherwise :: Bool
otherwise = True

This works because of the sequential evaluation described a couple of paragraphs back: if none of the guards previous to your 'otherwise' one are true, then your otherwise will definitely be true and so whatever is on the right-hand side gets returned. It's just nice for readability's sake.

'where' and guards

One nicety about guards is that where clauses are common to all guards.

 doStuff x
   | x < 3 = report "less than three"
   | otherwise = report "normal"
  where
   report y = "the input is " ++ y

This section is a stub. You can help Haskell by expanding it.

The difference between if and case

It's worth noting that there is a fundamental difference between if-expressions and case-expressions. if-expressions, and guards, only check to see if a boolean expression evaluated to True. case-expressions, and multiple equations for the same function, pattern match against the input. Make sure you understand this important distinction.

List processing



Because lists are such a fundamental data type in Haskell, there is a large collection of standard functions for processing them. These are mostly to be found in a library module called the 'Standard Prelude' which is automatically imported in all Haskell programs. There are also additional list-processing functions to be found in the Data.List module.

Map

This module will explain one particularly important function, called map, and then describe some of the other list processing functions that work in similar ways.

Recall the multiplyList function from a couple of chapters ago.

multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList _ [] = []
multiplyList m (n:ns) = (m*n) : multiplyList m ns

This works on a list of integers, multiplying each item by a constant. But Haskell allows us to pass functions around just as easily as we can pass integers. So instead of passing a multiplier m we could pass a function f, like this:

mapList1 :: (Integer -> Integer) -> [Integer] -> [Integer]
mapList1 _ [] = []
mapList1 f (n:ns) = (f n) : mapList1 f ns

Take a minute to compare the two functions. The difference is in the first parameter. Instead of being just an Integer it is now a function. This function parameter has the type (Integer -> Integer), meaning that it is a function from one integer to another. The second line says that if this is applied to an empty list then the result is itself an empty list, and the third line says that for a non-empty list the result is f applied to the first item in the list, followed by a recursive call to mapList1 for the rest of the list.

Remember that (*) has type Integer -> Integer -> Integer. So if we write (2*) then this returns a new function that doubles its argument and has type Integer -> Integer. But that is exactly the type of functions that can be passed to mapList1. So now we can write doubleList like this:

  doubleList = mapList1 (2*)

We could also write it like this, making all the arguments explicit:

  doubleList ns = mapList1 (2*) ns

(The two are equivalent because if we pass just one argument to mapList1 we get back a new function. The second version is more natural for newcomers to Haskell, but experts often favour the first, known as 'point free' style.)

Obviously this idea is not limited to just integers. We could just as easily write

mapListString :: (String -> String) -> [String] -> [String]
mapListString _ [] = []
mapListString f (n:ns) = (f n) : mapListString f ns

and have a function that does this for strings. But this is horribly wasteful: the code is exactly the same for both strings and integers. What is needed is a way to say that mapList works for both Integers, Strings, and any other type we might want to put in a list. In fact there is no reason why the input list should be the same type as the output list: we might very well want to convert a list of integers into a list of their string representations, or vice versa. And indeed Haskell provides a way to do this. The Standard Prelude contains the following definition of map:

 map :: (a -> b) -> [a] -> [b]
 map _ [] = []
 map f (x:xs) = (f x) : map f xs

Instead of constant types like String or Integer this definition uses type variables. These start with lower case letters (as opposed to type constants that start with upper case) and otherwise follow the same lexical rules as normal variables. However the convention is to start with "a" and go up the alphabet. Even the most complicated functions rarely get beyond "d".

So what this says is that map takes two parameters:

• A function from a thing of type a to a thing of type b.
• A list of things of type a.

Then it returns a new list containing things of type b, constructed by applying the function to each element of the input list.

Folds

A fold applies a function to a list in a way similar to map, but accumulates a single result instead of a list.

Take for example, a function like sum, which might be implemented as follows:

Example: sum

 sum :: [Integer] -> Integer
 sum []     = 0
 sum (x:xs) = x + sum xs

or product:

Example: product

 product :: [Integer] -> Integer
 product []     = 1
 product (x:xs) = x * product xs

or concat, which takes a list of lists and joins (concatenates) them into one:

Example: concat

 concat :: [[a]] -> [a]
 concat []     = []
 concat (x:xs) = x ++ concat xs

There is a certain pattern of recursion common to all of these examples. This pattern is known as a fold, possibly from the idea that a list is being "folded up" into a single value, or that a function is being "folded between" the elements of the list.

The Standard Prelude defines four fold functions: foldr, foldl, foldr1 and foldl1.

foldr

The most natural and commonly used of these in a lazy language like Haskell is the right-associative foldr:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

The first argument is a function with two arguments, the second is a "zero" value for the accumulator, and the third is the list to be folded.

For example, in sum, f is (+), and z is 0, and in concat, f is (++) and z is []. In many cases, like all of our examples so far, the function passed to a fold will have both its arguments be of the same type, but this is not necessarily the case in general.

What foldr f z xs does is to replace each cons (:) in the list xs with the function f, and the empty list at the end with z. That is,

a : b : c : []

becomes

f a (f b (f c z))

This is perhaps most elegantly seen by picturing the list data structure as a tree:

  :                         f
 / \                       / \
a   :       foldr f z     a   f
   / \    ------------->     / \
  b   :                     b   f
     / \                       / \
    c  []                     c   z

It is fairly easy to see with this picture that foldr (:) [] is just the identity function on lists.

foldl

The left-associative foldl processes the list in the opposite direction:

foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs

So brackets in the resulting expression accumulate on the left. Our list above, after being transformed by foldl f z becomes:

f (f (f z a) b) c

The corresponding trees look like:

  :                            f
 / \                          / \
a   :       foldl f z        f   c
   / \    ------------->    / \
  b   :                    f   b 
     / \                  / \
    c  []                z   a

Technical Note: The left associative fold is tail-recursive, that is, it recurs immediately, calling itself. For this reason the compiler will optimise it to a simple loop, and it will then be much more efficient than foldr. However, Haskell is a lazy language, and so the calls to f will by default be left unevaluated, building up an expression in memory whose size is linear in the length of the list, exactly what we hoped to avoid in the first place. To get back this efficiency, there is a version of foldl which is strict, that is, it forces the evaluation of f immediately, called foldl'. Note the single quote character: this is pronounced "fold-ell-tick". A tick is a valid character in Haskell identifiers. foldl' can be found in the library Data.List. As a rule you should use foldr on lists that might be infinite or where the fold is building up a data structure, and foldl' if the list is known to be finite and comes down to a single value. foldl (without the tick) should rarely be used at all.

foldr1 and foldl1

As previously noted, the type declaration for foldr makes it quite possible for the list elements and result to be of different types. For example, "read" is a function that takes a string and converts it into some type (the type system is smart enough to figure out which one). In this case we convert it into a float.

Example: The list elements and results can have different types

 addStr :: String -> Float -> Float
 addStr str x = read str + x

 sumStr :: [String] -> Float
 sumStr = foldr addStr 0.0

If you substitute the types Float and String for the type variables a and b in the type of foldr you will see that this is type correct.

There is also a variant called foldr1 ("fold - arr - one") which dispenses with an explicit zero by taking the last element of the list instead:

foldr1           :: (a -> a -> a) -> [a] -> a
foldr1 f [x]     =  x
foldr1 f (x:xs)  =  f x (foldr1 f xs)
foldr1 _ []      =  error "Prelude.foldr1: empty list"

And foldl1 as well:

foldl1           :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs)  =  foldl f x xs
foldl1 _ []      =  error "Prelude.foldl1: empty list"

Note: There is additionally a strict version of foldl1 called foldl1' in the Data.List library.

Notice that in this case all the types have to be the same, and that an empty list is an error. These variants are occasionally useful, especially when there is no obvious candidate for z, but you need to be sure that the list is not going to be empty. If in doubt, use foldr or foldl'.

folds and laziness

One good reason that right-associative folds are more natural to use in Haskell than left-associative ones is that right folds can operate on infinite lists, which are not so uncommon in Haskell programming. If the input function f only needs its first parameter to produce the first part of the output, then everything works just fine. However, a left fold must call itself recursively until it reaches the end of the input list; this is inevitable, because the recursive call is not made in an argument to f. Needless to say, this never happens if the input list is infinite, and the program will spin endlessly in an infinite loop.

As a toy example of how this can work, consider a function echoes taking a list of integers, and producing a list where if the number n occurs in the input list, then n replicated n times will occur in the output list. We will make use of the prelude function replicate: replicate n x is a list of length n with x the value of every element.

We can write echoes as a foldr quite handily:

echoes = foldr (\x xs -> (replicate x x) ++ xs) []

or, equally handily, as a foldl:

echoes = foldl (\xs x -> xs ++ (replicate x x)) []

but only the first definition works on an infinite list like [1..]. Try it! (If you try this in GHCi, remember you can stop an evaluation with Ctrl-c).

Note the syntax in the above example: the \xs x -> means that xs is set to the first argument outside the parentheses (in this case, []), and x is set to the second (will end up being the argument of echoes when it is called).

As a final example, another thing that you might notice is that map itself is patterned as a fold:

map f = foldr (\x xs -> f x : xs) []

Folding takes a little time to get used to, but it is a fundamental pattern in functional programming, and eventually becomes very natural. Any time you want to traverse a list and build up a result from its members, you likely want a fold.

Scans

A "scan" is much like a cross between a map and a fold. Folding a list accumulates a single return value, whereas mapping puts each item through a function with no accumulation. A scan does both: it accumulates a value like a fold, but instead of returning a final value it returns a list of all the intermediate values.

The Standard Prelude contains four scan functions:

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

This accumulates the list from the left, and the second argument becomes the first item in the resulting list. So scanl (+) 0 [1,2,3] = [0,1,3,6]

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

This is the same as scanl, but uses the first item of the list as a zero parameter. It is what you would typically use if the input and output items are the same type. Notice the difference in the type signatures. scanl1 (+) [1,2,3] = [1,3,6].

scanr   :: (a -> b -> b) -> b -> [a] -> [b] 	
scanr1  :: (a -> a -> a) -> [a] -> [a] 	

These two functions are the exact counterparts of scanl and scanl1. They accumulate the totals from the right. So:

scanr (+) 0 [1,2,3] = [6,5,3,0]
scanr1 (+) [1,2,3] = [6,5,3]

More on functions



As functions are absolutely essential to functional programming, there are some nice features you can use to make using functions easier.

Private Functions

Remember the sumStr function from the chapter on list processing. It used another function called addStr:

addStr :: Float -> String -> Float
addStr x str = x + read str

sumStr :: [String] -> Float
sumStr = foldl addStr 0.0

So you could find that

  addStr 4.3 "23.7"

gives 28.0, and

  sumStr ["1.2", "4.3", "6.0"]

gives 11.5.

But maybe you don't want addStr cluttering up the top level of your program. Haskell lets you nest declarations in two subtly different ways:

 sumStr = foldl addStr 0.0
    where addStr x str = x + read str

 sumStr =
    let addStr x str = x + read str
    in foldl addStr 0.0

The difference between let and where lies in the fact that let foo = 5 in foo + foo is an expression, but foo + foo where foo = 5 is not. (Try it: an interpreter will reject the latter expression.) Where clauses are part of the function declaration as a whole, which makes a difference when using guards.

Anonymous Functions

An alternative to creating a named function like addStr is to create an anonymous function, also known as a lambda function. For example, sumStr could have been defined like this:

 sumStr = foldl (\x str -> x + read str) 0.0

The bit in the parentheses is a lambda function. The backslash is used as the nearest ASCII equivalent to the Greek letter lambda (λ). This example is a lambda function with two arguments, x and str, and the result is "x + read str". So, the sumStr presented just above is precisely the same as the one that used addStr in a let binding.

Lambda functions are handy for one-off function parameters, especially where the function in question is simple. The example above is about as complicated as you want to get.

Infix versus Prefix

As we noted in the previous chapter, you can take an operator and turn it into a function by surrounding it in brackets:

2 + 4
(+) 2 4

This is called making the operator prefix: you're using it before its arguments, so it's known as a prefix function. We can now formalise the term 'operator': it's a function which entirely consists of non-alphanumeric characters, and is used infix (normally). You can define your own operators just the same as functions, just don't use any alphanumeric characters. For example, here's the set-difference definition from Data.List:

(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ ys = foldl (\zs y -> delete y zs) xs ys

Note that aside from just using operators infix, you can define them infix as well. This is a point that most newcomers to Haskell miss. I.e., although one could have written:

(\\) xs ys = foldl (\zs y -> delete y zs) xs ys

It's more common to define operators infix. However, do note that in type declarations, you have to surround the operators by parentheses.

You can use a variant on this parentheses style for 'sections':

(2+) 4
(+4) 2

These sections are functions in their own right. (2+) has the type Int -> Int, for example, and you can pass sections to other functions, e.g. map (+2) [1..4].

If you have a (prefix) function, and want to use it as an operator, simply surround it by backticks:

1 `elem` [1..4]

This is called making the function infix: you're using it in between its arguments. It's normally done for readability purposes: 1 `elem` [1..4] reads better than elem 1 [1..4]. You can also define functions infix:

elem :: Eq a => a -> [a] -> Bool
x `elem` xs = any (==x) xs

But once again notice that in the type signature you have to use the prefix style.

Sections even work with infix functions:

(1 `elem`) [1..4]
(`elem` [1..4]) 1

You can only make binary functions (those that take two arguments) infix. Think about the functions you use, and see which ones would read better if you used them infix.

Higher-order functions and Currying



Higher-order functions are functions that take other functions as arguments. We have already met some of them, such as map, so there isn't anything really frightening or unfamiliar about them. They offer a form of abstraction that is unique to the functional programming style. In functional programming languages like Haskell, functions are just like any other value, so it doesn't get any harder to deal with higher-order functions.

Higher order functions have a separate chapter in this book, not because they are particularly difficult -- we've already worked with them, after all -- but because they are powerful enough to draw special attention to them. We will see in this chapter how much we can do if we can pass around functions as values. Generally speaking, it is a good idea to abstract over a functionality whenever we can. Besides, Haskell without higher order functions wouldn't be quite as much fun.

The Quickest Sorting Algorithm In Town

Don't get too excited, but quickSort is certainly one of the quickest. Have you heard of it? If so, you can skip the following subsection and go straight to the next one:

The Idea Behind quickSort

The idea is very simple. For a big list, we pick an element, and divide the whole list into three parts.

The first part has all elements that should go before that element, the second part consists of all of the elements that are equal to the picked element, the third has the elements that ought to go after that element. And then, of course, we are supposed to concatenate these. What we get is somewhat better, right?

The trick is to note that only the first and the third are yet to be sorted, and for the second, sorting doesn't really make sense (they are all equal!). How to go about sorting the yet-to-be-sorted sub-lists? Why... apply the same algorithm on them again! By the time the whole process is finished, you get a completely sorted list.

So Let's Get Down To It!

-- if the list is empty, we do nothing
-- note that this is the base case for the recursion
quickSort [] = []

-- if there's only one element, no need to sort it
-- actually, the third case takes care of this one pretty well
-- I just wanted you to take it step by step
quickSort [x] = [x]

-- this is the gist of the process
-- we pick the first element as our "pivot", the rest is to be sorted
-- don't forget to include the pivot in the middle part!
quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                     where less = filter (< x) xs
                           equal = filter (== x) xs
                           more = filter (> x) xs

And we are done! I suppose if you have met quickSort before, you probably thought recursion was a neat trick but difficult to implement.

Now, How Do We Use It?

With quickSort at our disposal, sorting any list is a piece of cake. Suppose we have a list of String, maybe from a dictionary, and we want to sort them, we just apply quickSort to the list. For the rest of this chapter, we will use a pseudo-dictionary of words (but a 25,000 word dictionary should do the trick as well):

dictionary = ["I", "have", "a", "thing", "for", "Linux"]

We get, for quickSort dictionary,

["I", "Linux", "a", "for", "have", "thing"]

But, what if we wanted to sort them in the descending order? Easy, just reverse the list, reverse (quickSort dictionary) gives us what we want.

But wait! We didn't really sort in the descending order, we sorted (in the ascending order) and reversed it. They may have the same effect, but they are not the same thing!

Besides, you might object that the list you got isn't what you wanted. "a" should certainly be placed before "I". "Linux" should be placed between "have" and "thing". What's the problem here?

The problem is, the way Strings are represented in a typical programming settings is by a list of ASCII characters. ASCII (and almost all other encodings of characters) specifies that the character code for capital letters are less than the small letters. Bummer. So "Z" is less than "a". We should do something about it. Looks like we need a case insensitive quickSort as well. It might come handy some day.

But, there's no way you can blend that into quickSort as it stands. We have work to do.

Tweaking What We Already Have

What we need to do is to factor out the comparisons quickSort makes. We need to provide quickSort with a function that compares two elements, and gives an Ordering, and as you can imagine, an Ordering is any of LT, EQ, GT.

To sort in the descending order, we supply quickSort with a function that returns the opposite of the usual Ordering. For the case-insensitive sort, we may need to define the function ourselves. By all means, we want to make quickSort applicable to all such functions so that we don't end up writing it over and over again, each time with only minor changes.

quickSort, Take Two

So, forget the version of quickSort we have now, and let's think again.

Our quickSort will take two things this time: first, the comparison function, and second, the list to sort.

A comparison function will be a function that takes two things, say, x and y, and compares them. If x is less than y (according to the criteria we want to implement by this function), then the value will be LT. If they are equal (well, equal with respect to the comparison, we want "Linux" and "linux" to be equal when we are dealing with the insensitive case), we will have EQ. The remaining case gives us GT (pronounced: greater than, for obvious reasons).

-- no matter how we compare two things
-- the first two equations should not change
-- they need to accept the comparison function though
-- but the result doesn't need it
quickSort _ [] = []
quickSort _ [x] = [x]

-- we are in a more general setting now
-- but the changes are worth it!
-- c is the comparison function
quickSort c (x : xs) = (quickSort c less) ++ (x : equal) ++ (quickSort c more)
                             where less  = filter (\y -> y `c` x == LT) xs
                                   equal = filter (\y -> y `c` x == EQ) xs
                                   more  = filter (\y -> y `c` x == GT) xs

Cool!

But What Did We Gain?

Reuse. We can reuse quickSort to serve different purposes.

-- the usual ordering
-- uses the compare function from the Ord class
usual = compare

-- the descending ordering, note we flip the order of the arguments to compare
descending x y = compare y x

-- the case-insensitive version is left as an exercise!
insensitive = ... 
-- can you think of anything without making a very big list of all possible cases?

And we are done!

quickSort usual dictionary

should, then, give

["I", "Linux", "a", "for", "have", "thing"]

The comparison is just compare from the Ord class. This was our quickSort, before the tweaking.

quickSort descending dictionary

now gives

["thing", "have", "for", "a", "Linux", "I"]

And finally,

quickSort insensitive dictionary

gives

["a", "for", "have", "I", "Linux", "thing"]

Exactly what we wanted!

Higher-Order Functions and Types

Our quickSort has type (a -> a -> Ordering) -> [a] -> [a].

Most of the time, the type of a higher-order function provides a good guideline about how to use it. A straightforward way of reading the type signature would be, "quickSort takes a function that gives an ordering of as, and a list of as, to give a list of as". It is then natural to guess that the function sorts the list respecting the given ordering function.

Note that the parentheses surrounding a -> a -> Ordering is mandatory. It says that a -> a -> Ordering altogether form a single argument, an argument that happens to be a function. What happens if we omit the parentheses? We would get a function of type a -> a -> Ordering -> [a] -> [a], which accepts four arguments instead of the desired two (a -> a -> Ordering and [a]). Furthermore none of the four arguments, neither a nor Ordering nor [a] are functions, so omitting the parentheses would give us something that isn't a higher order function.

Furthermore, it's worth noting that the -> operator is right-associative, which means that a -> a -> Ordering -> [a] -> [a] means the same thing as a -> (a -> (Ordering -> ([a] -> [a]))). We really must insist that the a -> a -> Ordering be clumped together by writing those parentheses... but wait... if -> is right-associative, wouldn't that mean that the correct signature (a -> a -> Ordering) -> [a] -> [a] actually means... (a -> a -> Ordering) -> ([a] -> [a])?

Is that really what we want?

If you think about it, we're trying to build a function that takes two arguments, a function and a list, returning a list. Instead, what this type signature is telling us is that our function takes one argument (a function) and returns another function. That is profoundly odd... but if you're lucky, it might also strike you as being profoundly beautiful. Functions in multiple arguments are fundamentally the same thing as functions that take one argument and give another function back. It's OK if you're not entirely convinced. We'll go into a little bit more detail below and then show how something like this can be turned to our advantage.

for :: a -> (a->Bool) -> (a->a) -> (a-> IO ()) -> IO ()
for i p f job = -- ???

for 1 (<10) (+1) (print)

Currying

I hope you followed the reasoning of the preceding chapter closely enough. If you haven't, you should, so give it another try.

Currying is a technique^[1] that lets you partially apply a multi-parameter function. When you do that, it remembers those given values, and waits for the remaining parameters.

Our quickSort takes two parameters, the comparison function, and the list. We can, by currying, construct variations of quickSort with a given comparison function. The variation just "remembers" the specific comparison, so you can apply it to the list, and it will sort the list using the that comparison function.

descendingSort = quickSort descending

What is the type of descendingSort? quickSort was (a -> a -> Ordering) -> [a] -> [a], and the comparison function descending was a -> a -> Ordering. Applying quickSort to descending (that is, applying it partially, we haven't specified the list in the definition) we get a function (our descendingSort) for which the first parameter is already given, so you can scratch that type out from the type of quickSort, and we are left with a simple [a] -> [a]. So we can apply this one to a list right away!

descendingSort dictionary

gives us

["thing", "have", "for", "a", "Linux", "I"]

It's rather neat. But is it useful? You bet it is. It is particularly useful as sections, you might notice. Currying often makes Haskell programs very concise. More than that, it often makes your intentions a lot clearer. Remember

less = filter (< x) xs

from the first version of quickSort? You can read it aloud like "keep those in xs that are less than x". Although (< x) is just a shorthand for (\y -> y < x), try reading that aloud!

Notes

1. ↑ named after the outstanding logician Haskell Brooks Curry, the same guy after whom the language is named.

Intermediate Haskell

Modules



Modules

Haskell modules are a useful way to group a set of related functionalities into a single package and manage a set of different functions that have the same name. The module definition is the first thing that goes in your Haskell file.

Here is what a basic module definition looks like:

module YourModule where

Note that

1. The name of the module begins with a capital letter
2. Each file contains only one module.

The name of the file must be that of the module but with a .hs file extension. Any dots '.' in the module name are changed for directories. So the module YourModule would be in the file YourModule.hs while a module Foo.Bar would be in the file Foo/Bar.hs or Foo\Bar.hs. Since the module name must begin with a capital letter, then the file name must also start with a capital letter.

Importing

One thing your module can do is import functions from other modules. That is, in between the module declaration and the rest of your code, you may include some import declarations such as

-- import only the functions toLower and toUpper from Data.Char
import Data.Char (toLower, toUpper) 

-- import everything exported from Data.List 
import Data.List 

-- import everything exported from MyModule
import MyModule

Imported datatypes are specified by their name, followed by a list of imported constructors in parenthesis. For example:

-- import only the Tree data type, and its Node constructor from Data.Tree
import Data.Tree (Tree(Node))

Now what to do if you import some modules, but some of them have overlapping definitions? Or if you import a module, but want to overwrite a function yourself? There are three ways to handle these cases: Qualified imports, hiding definitions and renaming imports.

Qualified imports

Say MyModule and MyOtherModule both have a definition for remove_e, which removes all instances of e from a string. However, MyModule only removes lower-case e's, and MyOtherModule removes both upper and lower case. In this case the following code is ambiguous:

-- import everything exported from MyModule
import MyModule

-- import everything exported from MyOtherModule
import MyOtherModule

-- someFunction puts a c in front of the text, and removes all e's from the rest
someFunction :: String -> String
someFunction text = 'c' : remove_e text

It isn't clear which remove_e is meant! To avoid this, use the qualified keyword:

import qualified MyModule
import qualified MyOtherModule

someFunction text = 'c' : MyModule.remove_e text -- Will work, removes lower case e's
someOtherFunction text = 'c' : MyOtherModule.remove_e text -- Will work, removes all e's
someIllegalFunction text = 'c' : remove_e text -- Won't work, remove_e isn't defined.

See the difference? In the latter code snippet, the function remove_e isn't even defined. Instead, we call the functions from the imported modules by prefixing them with the module's name. Note that MyModule.remove_e also works if the qualified keyword isn't included. The difference lies in the fact that remove_e is ambiguously defined in the first case, and undefined in the second case. If we have a remove_e defined in the current module, then using remove_e without any prefix will call this function.

Hiding definitions

Now suppose we want to import both MyModule and MyOtherModule, but we know for sure we want to remove all e's, not just the lower cased ones. It will become really tedious to add MyOtherModule before every call to remove_e. Can't we just not import remove_e from MyModule? The answer is: yes we can.

-- Note that I didn't use qualified this time.
import MyModule hiding (remove_e)
import MyOtherModule

someFunction text = 'c' : remove_e text

This works. Why? Because of the word hiding on the import line. Followed by it, is a list of functions that shouldn't be imported. Hiding more than one function works like this:

import MyModule hiding (remove_e, remove_f)

Note that algebraic datatypes and type synonyms cannot be hidden. These are always imported. If you have a datatype defined in more modules, you must use qualified names.

Renaming imports

This is not really a technique to allow for overwriting, but it is often used along with the qualified flag. Imagine:

import qualified MyModuleWithAVeryLongModuleName

someFunction text = 'c' : MyModuleWithAVeryLongModuleName.remove_e $ text

Especially when using qualified, this gets irritating. What we can do about it, is using the as keyword:

import qualified MyModuleWithAVeryLongModuleName as Shorty

someFunction text = 'c' : Shorty.remove_e $ text

This allows us to use Shorty instead of MyModuleWithAVeryLongModuleName as prefix for the imported functions. As long as there are no ambiguous definitions, the following is also possible:

import MyModule as My
import MyCompletelyDifferentModule as My

In this case, both the functions in MyModule and the functions in MyCompletelyDifferentModule can be prefixed with My.

Exporting

In the examples at the start of this article, the words "import everything exported from MyModule" were used. This raises a question. How can we decide which functions are exported and which stay "internal"? Here's how:

module MyModule (remove_e, add_two) where

add_one blah = blah + 1

remove_e text = filter (/= 'e') text

add_two blah = add_one . add_one $ blah

In this case, only remove_e and add_two are exported. While add_two is allowed to make use of add_one, functions in modules that import MyModule cannot use add_one, as it isn't exported.

Datatype export specifications are written quite similarly to import. You name the type, and follow with the list of constructors in parenthesis:

module MyModule2 (Tree(Branch, Leaf)) where

data Tree a = Branch {left, right :: Tree a} 
            | Leaf a

In this case, the module declaration could be rewritten "MyModule2 (Tree(..))", declaring that all constructors are exported.

Note: maintaining an export list is good practice not only because it reduces namespace pollution, but also because it enables certain compile-time optimizations which are unavailable otherwise.

Notes

In Haskell98, the last standardised version of Haskell, the module system is fairly conservative, but recent common practice consists of employing an hierarchical module system, using periods to section off namespaces.

Mutual recursive modules are possible but need some special treatment. For how to do it in GHC see: http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#mutual-recursion

A module may export functions that it imports.

See the Haskell report for more details on the module system:

• http://www.haskell.org/onlinereport/modules.html

Indentation



Haskell relies on indentation to reduce the verbosity of your code, but working with the indentation rules can be a bit confusing. The rules may seem many and arbitrary, but the reality of things is that there are only one or two layout rules, and all the seeming complexity and arbitrariness comes from how these rules interact with your code. So to take the frustration out of indentation and layout, the simplest solution is to get a grip on these rules.

The golden rule of indentation

Whilst the rest of this chapter will discuss in detail Haskell's indentation system, you will do fairly well if you just remember a single rule:

Code which is part of some expression should be indented further in than the line containing the beginning of that expression

What does that mean? The easiest example is a let binding group. The equations binding the variables are part of the let expression, and so should be indented further in than the beginning of the binding group: the let keyword. So,

let
 x = a
 y = b

Although you actually only need to indent by one extra space, it's more normal to place the first line alongside the 'let' and indent the rest to line up:

let x = a
    y = b

Here are some more examples:

do foo
   bar
   baz

where x = a
      y = b

case x of
  p  -> foo
  p' -> baz

Note that with 'case' it's less common to place the next expression on the same line as the beginning of the expression, as with 'do' and 'where'. Also note we lined up the arrows here: this is purely aesthetic and isn't counted as different layout; only indentation, whitespace beginning on the far-left edge, makes a difference to layout.

Things get more complicated when the beginning of the expression doesn't start at the left-hand edge. In this case, it's safe to just indent further than the line containing the expression's beginning. So,

myFunction firstArgument secondArgument = do -- the 'do' doesn't start at the left-hand edge
  foo                                        -- so indent these commands more than the beginning of the line containing the 'do'.
  bar
  baz

Here are some alternative layouts to the above which would have also worked:

myFunction firstArgument secondArgument = 
  do foo
     bar
     baz

myFunction firstArgument secondArgument = do foo
                                             bar
                                             baz

A mechanical translation

Did you know that layout (whitespace) is optional? It is entirely possible to treat Haskell as a one-dimensional language like C, using semicolons to separate things, and curly braces to group them back.

To understand layout, you need to understand two things: where we need semicolons/braces, and how to get there from layout. The entire layout process can be summed up in three translation rules (plus a fourth one that doesn't come up very often):

1. If you see one of the layout keywords, (let, where, of, do), insert an open curly brace (right before the stuff that follows it)
2. If you see something indented to the SAME level, insert a semicolon
3. If you see something indented LESS, insert a closing curly brace
4. If you see something unexpected in a list, like where, insert a closing brace before instead of a semicolon.

to be completed: work through an example

  of a
     b
      c
     d
  where
  a
  b
  c
  do
 you
  like
 the
way
 i let myself
        abuse
       these
 layout rules

Layout in action

 do first thing
 second thing
 third thing

 do first thing
    second thing 
    third thing

do within if

What happens if we put a do expression with an if? Well, as we stated above, the keywords if then else, and everything besides the 4 layout keywords do not affect layout. So things remain exactly the same:

 if foo
    then do first thing
         second thing
         third thing
    else do something else

 if foo
    then do first thing
            second thing
            third thing
    else do something else

Indent to the first

Remember from the First Rule of Layout Translation (above) that although the keyword do tells Haskell to insert a curly brace, where the curly braces goes depends not on the do, but the thing that immediately follows it. For example, this weird block of code is totally acceptable:

         do
first thing
second thing
third thing

As a result, you could also write combined if/do combination like this:

 if foo
    then do first thing
         second thing
         third thing
    else do something else

 if foo
    then do 
     first thing
     second thing
     third thing
    else do something else

This is also the reason why you can write things like this

main = do
 first thing
 second thing

instead of

main = 
 do first thing
    second thing

Both are acceptable

if within do

This is a combination which trips up many Haskell programmers. Why does the following block of code not work?

-- why is this bad?
do first thing
   if condition
   then foo
   else bar
   third thing

Just to reiterate, the if then else block is not at fault for this problem. Instead, the issue is that the do block notices that the then part is indented to the same column as the if part, so it is not very happy, because from its point of view, it just found a new statement of the block. It is as if you had written the unsugared version on the right:

-- why is this bad?
do first thing
   if condition
   then foo
   else bar
   third thing

-- still bad, just explicitly so
do { first thing
   ; if condition
   ; then foo
   ; else bar
   ; third thing }

Naturally, the Haskell compiler is confused because it thinks that you never finished writing your if expression, before writing a new statement. The compiler sees that you have written something like if condition;, which is clearly bad, because it is unfinished. So, in order to fix this, we need to indent the bottom parts of this if block a little bit inwards

-- whew, fixed it!
do first thing
   if condition
    then foo
    else bar
   third thing

-- the fixed version without sugar
do { first thing
   ; if condition
      then foo
      else bar
   ; third thing }

This little bit of indentation prevents the do block from misinterpreting your then as a brand new expression.

References

• The Haskell Report (lexemes) - see 2.7 on layout

More on datatypes

Enumerations

One special case of the data declaration is the enumeration. This is simply a data type where none of the constructor functions have any arguments:

data Month = January | February | March | April | May | June | July
             | August | September | October | November | December

You can mix constructors that do and do not have arguments, but it's only an enumeration if none of the constructors have arguments. The section below on "Deriving" explains why the distinction is important. For instance,

data Colour = Black | Red | Green | Blue | Cyan
            | Yellow | Magenta | White | RGB Int Int Int

The last constructor takes three arguments, so Colour is not an enumeration.

Incidentally, the definition of the Bool datatype is:

data Bool = False | True
    deriving (Eq, Ord, Enum, Read, Show, Bounded)

Named Fields (Record Syntax)

Consider a datatype whose purpose is to hold configuration settings. Usually when you extract members from this type, you really only care about one or possibly two of the many settings. Moreover, if many of the settings have the same type, you might often find yourself wondering "wait, was this the fourth or fifth element?" One thing you could do would be to write accessor functions. Consider the following made-up configuration type for a terminal program:

data Configuration =
    Configuration String          -- user name
                  String          -- local host
                  String          -- remote host
                  Bool            -- is guest?
                  Bool            -- is super user?
                  String          -- current directory
                  String          -- home directory
                  Integer         -- time connected
              deriving (Eq, Show)

You could then write accessor functions, like (I've only listed a few):

getUserName (Configuration un _ _ _ _ _ _ _) = un
getLocalHost (Configuration _ lh _ _ _ _ _ _) = lh
getRemoteHost (Configuration _ _ rh _ _ _ _ _) = rh
getIsGuest (Configuration _ _ _ ig _ _ _ _) = ig
...

You could also write update functions to update a single element. Of course, now if you add an element to the configuration, or remove one, all of these functions now have to take a different number of arguments. This is highly annoying and is an easy place for bugs to slip in. However, there's a solution. We simply give names to the fields in the datatype declaration, as follows:

data Configuration =
    Configuration { username      :: String,
                    localhost     :: String,
                    remotehost    :: String,
                    isguest       :: Bool,
                    issuperuser   :: Bool,
                    currentdir    :: String,
                    homedir       :: String,
                    timeconnected :: Integer
                  }

This will automatically generate the following accessor functions for us:

username :: Configuration -> String
localhost :: Configuration -> String
...

Moreover, it gives us very convenient update methods. Here is a short example for a "post working directory" and "change directory" like functions that work on Configurations:

changeDir :: Configuration -> String -> Configuration
changeDir cfg newDir =
    -- make sure the directory exists
    if directoryExists newDir
      then -- change our current directory
           cfg{currentdir = newDir}
      else error "directory does not exist"

postWorkingDir :: Configuration -> String
  -- retrieve our current directory
postWorkingDir cfg = currentdir cfg

So, in general, to update the field x in a datatype y to z, you write y{x=z}. You can change more than one; each should be separated by commas, for instance, y{x=z, a=b, c=d}.

It's only sugar

You can of course continue to pattern match against Configurations as you did before. The named fields are simply syntactic sugar; you can still write something like:

getUserName (Configuration un _ _ _ _ _ _ _) = un

But there is little reason to. Finally, you can pattern match against named fields as in:

getHostData (Configuration {localhost=lh,remotehost=rh})
  = (lh,rh)

This matches the variable lh against the localhost field on the Configuration and the variable rh against the remotehost field on the Configuration. These matches of course succeed. You could also constrain the matches by putting values instead of variable names in these positions, as you would for standard datatypes.

You can create values of Configuration in the old way as shown in the first definition below, or in the named-field's type, as shown in the second definition below:

initCFG =
    Configuration "nobody" "nowhere" "nowhere"
                  False False "/" "/" 0
initCFG' =
    Configuration
       { username="nobody",
         localhost="nowhere",
         remotehost="nowhere",
         isguest=False,
         issuperuser=False,
         currentdir="/",
         homedir="/",
         timeconnected=0 }

The first way is much shorter, although the second is much more understandable (unless you litter your code with comments).

Parameterised Types

Parameterised types are similar to "generic" or "template" types in other languages. A parameterised type takes one or more type parameters. For example the Standard Prelude type Maybe is defined as follows:

data Maybe a = Nothing | Just a

This says that the type Maybe takes a type parameter a. You can use this to declare, for example:

lookupBirthday :: [Anniversary] -> String -> Maybe Anniversary

The lookupBirthday function takes a list of birthday records and a string and returns a Maybe Anniversary. Typically, our interpretation is that if it finds the name then it will return Just the corresponding record, and otherwise, it will return Nothing.

You can parameterise type and newtype declarations in exactly the same way. Furthermore you can combine parameterised types in arbitrary ways to construct new types.

More than one type parameter

We can also have more than one type parameter. An example of this is the Either type:

data Either a b = Left a | Right b

For example:

eitherExample :: Int -> Either Int String
eitherExample a | even a = Left (a `div` 2)
                | a `mod` 3 == 0 = Right "three"
                | otherwise = Right "neither two nor three"

otherFunction :: Int -> String
otherFunction a = case eitherExample a of
  Left c -> "Even: " ++ show a ++ " = 2*" ++ show c ++ "."
  Right s -> show a ++ " is divisible by " ++ s ++ "."

In this example, when you call otherFunction, it'll return a String. If you give it an even number as argument, it'll say so, and give half of it. If you give it anything else, eitherExample will determine if it's divisible by three and pass it through to otherFunction.

Kind Errors

The flexibility of Haskell parameterised types can lead to errors in type declarations that are somewhat like type errors, except that they occur in the type declarations rather than in the program proper. Errors in these "types of types" are known as "kind" errors. You don't program with kinds: the compiler infers them for itself. But if you get parameterised types wrong then the compiler will report a kind error.

Trees

Now let's look at one of the most important datastructures: Trees. A tree is an example of a recursive datatype. Typically, its definition will look like this:

data Tree a = Leaf a | Branch (Tree a) (Tree a)

As you can see, it's parameterised, so we can have trees of Ints, trees of Strings, trees of Maybe Ints, even trees of (Int, String) pairs, if you really want. What makes it special is that Tree appears in the definition of itself. We will see how this works by using an already known example: the list.

Lists as Trees

Think about it. As we have seen in the List Processing chapter, we break lists down into two cases: An empty list (denoted by []), and an element of the specified type, with another list (denoted by (x:xs)). This gives us valuable insight about the definition of lists:

data [a] = [] | (a:[a]) -- Pseudo-Haskell, will not work properly.

Which is sometimes written as (for Lisp-inclined people):

data List a = Nil | Cons a (List a)

As you can see this is also recursive, like the tree we had. Here, the constructor functions are [] and (:). They represent what we have called Leaf and Branch. We can use these in pattern matching, just as we did with the empty list and the (x:xs):

Maps and Folds

We already know about maps and folds for lists. With our realisation that a list is some sort of tree, we can try to write map and fold functions for our own type Tree. To recap:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
data [a]    = []     | (:)    a [a]              
  -- (:) a [a] would be the same as (a:[a]) with prefix instead of infix notation.

I will handle map first, then folds.

Map

Let's take a look at the definition of map for lists:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

First, if we were to write treeMap, what would its type be? Defining the function is easier if you have an idea of what its type should be.

We want it to work on a Tree of some type, and it should return another Tree of some type. What treeMap does is applying a function on each element of the tree, so we also need a function. In short:

treeMap :: (a -> b) -> Tree a -> Tree b

See how this is similar to the list example?