In OCaml from the Very Beginning John Whitington takes a no-prerequisites approach to teaching a modern general-purpose programming language. Each small, self-contained chapter introduces a new topic, building until the reader can write quite substantial programs. There are plenty of questions and, crucially, worked answers and hints.

OCaml from the Very Beginning will appeal both to new programmers, and experienced programmers eager to explore functional languages such as OCaml. It is suitable both for formal use within an undergraduate or graduate curriculum, and for the interested amateur.

John Whitington founded a software company which uses OCaml extensively. He teaches functional programming to students of Computer Science at the University of Cambridge.

This publication is in copyright. Subject to statutory exception no reproduction of any part may take place without the written permission of Coherent Press. A catalogue record for this book is available from the British Library.

Preface

This book is based on the Author’s experience of teaching programming to students in the University of Cambridge supervisions system. In particular, working with students for the first-year undergraduate course “Foundations of Computer Science”, based on Standard ML and lectured for many years by Lawrence C. Paulson.

An interesting aspect of supervising students from a wide range of backgrounds (some with no previous experience at all taking Computer Science as an additional subject within the Cambridge Natural Sciences curriculum, and some with a great deal of programming experience already) is the level playing field which the ML family of languages (like OCaml) provide. Sometimes, those students with least prior programming experience perform the best.

I have tried to write a book which has no prerequisites – and with which any intelligent undergraduate ought to be able to cope, whilst trying to be concise enough that someone coming from another language might not be too annoyed by the tone.

Special note to those who have already written programs

When I was a boy, our class was using a word processor for the first time. I wanted a title for my story, so I typed it on the first line and then, placing the cursor at the beginning, held down the space bar until the title was roughly in the middle. My friend taught me how to use the centring function, but it seemed more complicated to me, and I stuck with the familiar way – after all, it worked. Later on, of course, when I had more confidence and experience, I realized he had been right.

When starting a language which is fundamentally different from those you have seen before, it can be difficult to see the advantages, and to try to think of every concept in terms of the old language. I would urge you to consider the possibility that, at the moment, you might be the boy holding down the space bar.

Acknowledgments

Inevitably, the approach here owes a debt to that taken by Lawrence C. Paulson, both in his lecture notes and in his book “ML for the Working Programmer” (Cambridge University Press, 1996). Question 3 in Chapter 11 is inspired by an examination question of his. I was taught Standard ML by Professor Paulson and Andrei Serjantov in Autumn 2000. Mark Shinwell has been a constant source of helpful discussion. Robin Walker and latterly Andrew Rice have arranged the supervisions system at Queens’ College within which I have taught since 2004. I am grateful to the developers of OCaml who have provided such a pleasant environment in which to write programs. Helpful comments on an earlier draft were provided by Martin DeMello, Damien Doligez, Arthur Guillon, Zhi Han, Robert Jakob, Xavier Leroy, Florent Monnier, and Benjamin Pierce. And, of course, I thank all my students, some of whom are now working with OCaml for a living.

Getting Ready

This book is about teaching the computer to do new things by writing computer programs. Just as there are different languages for humans to speak to one another, there are different programming languages for humans to speak to computers.

We are going to be using a programming language called OCaml. It might already be on your computer, or you may have to find it on the internet and install it yourself. You will know that you have OCaml working when you see something like this:

OCaml is waiting for us to type something. Try typing 1 + 2;; followed by the Enter key. You should see this:

OCaml is telling us the result of the calculation. To leave OCaml, give the exit 0 command, again ending with ;; to tell OCaml we have finished typing:

You should find yourself back where you were before. If you make a mistake when typing, you can press Ctrl-C (hold down the Ctrl key and tap the c key). This will allow you to start again:

Starting Off

We will cover a fair amount of material in this chapter and its questions, since we will need a solid base on which to build. You should read this with a computer running OCaml in front of you.

Consider first the mathematical expression 1 + 2 × 3. What is the result? How did you work it out? We might show the process like this:

How did we know to multiply 2 by 3 first, instead of adding 1 and 2? How did we know when to stop? Let us underline the part of the expression which is dealt with at each step:

We chose which part of the expression to deal with each time using a familiar mathematical rule – multiplication is done before addition. We stopped when the expression could not be processed any further.

Computer programs in OCaml are just like these expressions. In order to give you an answer, the computer needs to know all the rules you know about how to process the expression correctly. In fact, 1 + 2 × 3 is a valid OCaml expression as well as a valid mathematical one, but we must write * instead of ×, since there is no × key on the keyboard:

Here, # is OCaml prompting us to write an expression, and 1 + 2 * 3;; is what we typed (the semicolons followed by the Enter key tell OCaml we have finished our expression). OCaml responds with the answer 7. OCaml also prints int, which tells us that the answer is a whole number, or integer.

Let us look at our example expression some more. There are two operators: + and ×. There are three operands: 1, 2, and 3. When we wrote it down, and when we typed it into OCaml, we put spaces between the operators and operands for readability. How does OCaml process it? Firstly, the text we wrote must be split up into its basic parts: 1, +, 2, *, and 3. OCaml then looks at the order and kind of the operators and operands, and decides how to parenthesize the expression: (1+(2×3)). Now, processing the expression just requires dealing with each parenthesized section, starting with the innermost, and stopping when there are no parentheses left:

OCaml knows that × is to be done before +, and parenthesizes the expression appropriately. We say the × operator has higher precedence than the + operator.

An expression is any valid OCaml program. To produce an answer, OCaml evaluates the expression, yielding a special kind of expression, a value. In our previous example, 1 + 2 × 3, 1 + 6, and 7 were all expressions, but only 7 was a value.

Each expression (and so each value) has a type. The type of 7 is int (it is an integer). The types of the expressions 1 + 6 and 1 + 2 × 3 are also int, since they will evaluate to a value of type int. The type of any expression may be worked out by considering the types of its sub-expressions, and how they are combined to form the expression. For example, 1 + 6 has type int because 1 is an int, 6 is an int, and the + operator takes two integers and gives another one (their sum). Here are the mathematical operators on integers:

Operator	Description
a `+` b	addition
a `-` b	subtract b from a
a `*` b	multiplication
a `/` b	divide a by b, returning the whole part
a `mod` b	divide a by b, returning the remainder

The mod, *, and / operators have higher precedence than the + and - operators. For any operator ⊕ above, the expression a ⊕ b ⊕ c is equivalent to (a ⊕ b) ⊕ c rather than a ⊕ (b ⊕ c) (we say the operators are left associative). We sometimes write down the type of an expression after a colon when working on paper, to keep it in mind:

(negative numbers are written with - before them). Of course, there are many more types than just int. Sometimes, instead of numbers, we would like to talk about truth: either something is true or it is not. For this we use the type bool which represents boolean values, named after the English mathematician George Boole (1815–1864) who pioneered their use. There are just two things of type bool:

How can we use these? One way is to use one of the comparison operators, which are used for comparing values to one another. For example:

OCaml

# 99 > 100;;
- : bool = false
# 4 + 3 + 2 + 1 = 10;;
- : bool = true

Notice that if we try to use operators with types for which they are not intended, OCaml will not accept the program at all, showing us where our mistake is by underlining it:

Operator	Description
a `=` b	true if a and b are equal
a `<` b	true if a is less than b
a `<=` b	true if a is less than or equal to b
a `>` b	true if a is more than b
a `>=` b	true if a is more than or equal to b
a `<>` b	true if a is not equal to b

OCaml

# 1 + true;;
Error: This expression has type bool but an expression was expected of type
int

You can find more information about error messages in OCaml in the appendix “Coping with Errors” at the back of this book.

There are two operators for combining boolean values (for instance, those resulting from using the comparison operators). The expression a && b evaluates to true only if expressions a and b both evaluate to true. The expression a || b evaluates to true only if a evaluates to true, b evaluates to true, or both do. The && operator (pronounced “and”) is of higher precedence than the || operator (pronounced “or”), so a && b || c is the same as (a && b) || c.

A third type we shall be using is char which holds a single character, such as ‘a’ or ‘?’. We write these in single quotation marks:

So far we have looked only at operators like +, mod, and = which look like familiar mathematical ones. But many constructs in programming languages look a little different. For example, to choose a course of evaluation based on some test, we use the if … then … else construct:

The expression between if and then (in our example 100 > 99) must have type bool – it evaluates to either true or false. The types of the expression to choose if true and the expression to choose if false must be the same as one another – here they are both of type int. The whole expression evaluates to the same type – int – because either the then part or the else part is chosen to be the result of evaluating the whole expression:

We have covered a lot in this chapter, but we need all these basic tools before we can write interesting programs. Make sure you work through the questions on paper, on the computer, or both, before moving on. Hints and answers are at the back of the book.

Questions

Names and Functions

So far we have built only tiny toy programs. To build bigger ones, we need to be able to name things so as to refer to them later. We also need to write expressions whose result depends upon one or more other things.

Before, if we wished to use a sub-expression twice or more in a single expression, we had to type it multiple times:

Instead, we can define our own name to stand for the result of evaluating an expression, and then use the name as we please:

OCaml

# let x = 200;;
val x : int = 200
# x * x * x;;
- : int = 8000000

To write this all in a single expression, we can use the let … = … in construct:

OCaml

# let x = 200 in x * x * x;;
- : int = 8000000
# let a = 500 in (let b = a * a in a + b);;
- : int = 250500

We can also make a function, whose value depends upon some input (we call this input an argument – we will be using the word “input” later in the book to mean something different):

OCaml

# let cube x = x * x * x;;
val cube : int -> int = <fun>
# cube 200;;
- : int = 8000000

We chose cube for the name of the function and x for the name of its argument. When we typed the function in, OCaml replied by telling us that its type is int → int. This means it is a function which takes an integer as its argument, and, when given that argument, evaluates to an integer. To use the function, we just write its name followed by a suitable argument. In our example, we calculated 200³ by giving the cube function 200 as its argument.

The cube function has type int → int, we gave it an integer 200, and so the result is another integer. Thus, the type of the expression cube 200 is int – remember that the type of any expression is the type of the thing it will evaluate to, and cube 200 evaluates to 8000000, an integer. In diagram form:

OCaml

# let cube x = x * x * x;;
val cube : int -> int = <fun>
# cube false;;
Error: This expression has type bool but an expression was expected of type
int

OCaml

# let neg x = if x < 0 then true else false;;
val neg : int -> bool = <fun>
# neg (-30);;
- : bool = true

(We added parentheses to distinguish from neg - 30). But, of course, this is equivalent to just writing

OCaml

# let neg x = x < 0;;
val neg : int -> bool = <fun>
# neg (-30);;
- : bool = true

because x < 0 will evaluate to the appropriate boolean value on its own – true if x < 0 and false otherwise. Here is another function, this time of type char → bool. It determines if a given character is a vowel or not:

OCaml

# let isvowel c =
c = ’a’ || c = ’e’ || c = ’i’ || c = ’o’ || c = ’u’;;
val isvowel : char -> bool = <fun>
# isvowel ’x’;;
- : bool = false

Notice that we typed the function over two lines. This can be done by pressing the Enter key in between lines. OCaml knows that we are finished when we type ;; followed by Enter as usual. Notice also that we pressed space a few times so that the second line appeared a little to the right of the first. This is known as indentation and does not affect the meaning of the program at all – it is just for readability.

There can be more than one argument to a function. For example, here is a function which checks if two numbers add up to ten:

OCaml

# let addtoten a b =
a + b = 10;;
val addtoten : int -> int -> bool = <fun>
# addtoten 6 4;;
- : bool = true

The type is int → int → bool because the arguments are both integers, and the result is a boolean. We use the function in the same way as before, but writing two integers this time, one for each argument the function expects.

A recursive function is one which uses itself. Consider calculating the factorial of a given number – the factorial of 4 (written 4! in mathematics), for example, is 4 × 3 × 2 × 1. Here is a recursive function to calculate the factorial of a positive number. Note that it uses itself in its own definition.

OCaml

# let rec factorial a =
if a = 1 then 1 else a * factorial (a - 1);;
val factorial : int -> int = <fun>
# factorial 4;;
- : int = 24

We used let rec instead of let to indicate a recursive function. How does the evaluation of factorial 4 proceed?

For the first three steps, the else part of the conditional expression is chosen, because the argument a is greater than one. When the argument is equal to one, we do not use factorial again, but just evaluate to one. The expression built up of all the multiplications is then evaluated until a value is reached: this is the result of the whole evaluation. It is sometimes possible for a recursive function never to finish – what if we try to evaluate factorial (-1)?

The expression keeps expanding, and the recursion keeps going. Helpfully, OCaml tells us what is going on:

OCaml

# let rec factorial a =
if a = 1 then 1 else a * factorial (a - 1);;
val factorial : int -> int = <fun>
# factorial (-1);;
Stack overflow during evaluation (looping recursion?).

This is an example of an error OCaml cannot find by merely looking at the program – it can only be detected during evaluation. Later in the book, we will see how to prevent people who are using our functions from making such mistakes.

One of the oldest methods for solving a problem (or algorithm) still in common use is Euclid’s algorithm for calculating the greatest common divisor of two numbers (that is, given two positive integers a and b, finding the biggest positive integer c such that neither a/c nor b/c have a remainder). Euclid was a Greek mathematician who lived about three centuries before Christ. Euclid’s algorithm is simple to write as a function with two arguments:

OCaml

# let rec gcd a b =
if b = 0 then a else gcd b (a mod b);;
val gcd : int -> int -> int = <fun>
# gcd 64000 3456;;
- : int = 128

Finally, here is a simple function on boolean values. In the previous chapter, we looked at the && and || operators which are built in to OCaml. The other important boolean operator is the not function, which returns the boolean complement (opposite) of its argument – true if the argument is false, and vice versa. This is also built in, but it is easy enough to define ourselves, as a function of type bool → bool.

OCaml

# let not x =
if x then false else true;;
val not : bool -> bool = <fun>
# not true;;
- : bool = false

Almost every program we write will involve functions such as these, and many larger ones too. In fact, languages like OCaml are often called functional languages.

Questions

Note on Notation

OCaml

# let rec factorial a =
if a = 1 then 1 else a * factorial (a - 1);;
val factorial : int -> int = <fun>

If you prefer to compose your programs in a text editing program, and copy-and-paste them into OCaml, you can do that too. Just make sure you end with ;; to let OCaml know you have finished entering the program.

Later on, when we write larger programs, we will see how to use OCaml to load our programs from external files.

Case by Case

In the previous chapter, we used the conditional expression if … then … else to define functions whose results depend on their arguments. For some of them we had to nest the conditional expressions one inside another. Programs like this are not terribly easy to read, and expand quickly in size and complexity as the number of cases increases.

OCaml has a nicer way of expressing choices – pattern matching. For example, recall our factorial function:

We can read this as “See if a matches the pattern 1. If it does, just return 1. If not, see if it matches the pattern _. If it does, the result is a * factorial (a - 1).” The pattern _ is special – it matches anything. Remember our isvowel function from the previous chapter?

OCaml

# let isvowel c =
    match c with
      ’a’ -> true
    | ’e’ -> true
    | ’i’ -> true
    | ’o’ -> true
    | ’u’ -> true;;
# Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
'b'
val isvowel : char -> bool

OCaml does not reject the program, because there may be legitimate reasons to miss cases out, but for now we will make sure all our pattern matches are complete. Notice that we had to repeat true five times. This would be awkward if the expression to be calculated was more complicated. We can combine patterns like this:

The type of a whole match … with … expression is determined by the types of the expressions on the right hand side of each -> arrow, all of which must be alike:

We use pattern matching whenever it is easier to read and understand than if … then … else expressions.

Questions

Making Lists

We write a list between square brackets [ and ], separating the elements with semicolons. The list above has type int list, because it is a list of integers. All elements of the list must have the same type. The elements in the list are ordered (in other words, [1; 2; 3] and [2; 3; 1] are not the same list).

The first element is called the head, and the rest are collectively called the tail. In our example, the head is the integer 1 and the tail is the list [2; 3]. So you can see that the tail has the same type as the whole list. Here is a list with no elements (called “the empty list” or sometimes “nil”):

Its head is the integer 5 and its tail is the empty list []. So every non-empty list has both a head and a tail. Lists may contain elements of any type: integers, booleans, functions, even other lists. For example, here is a list containing elements of type bool:

OCaml defines two operators for lists. The :: operator (pronounced “cons”) is used to add a single element to the front of an existing list:

The cons operation is completed in a constant amount of time, regardless of the length of the list. The @ operator (pronounced “append”) is used to combine two lists together:

This takes time proportional to the length of the list on the left hand side of the @ operator (that is, a list of length 100 will take roughly twice as long as one of length 50). We will see why soon.

Now, how do we write functions using lists? We can use pattern matching as usual, with some new types of pattern. For example, here’s a function which tells us if a list is empty:

The argument has type α list (which OCaml prints on the screen as ’a list) because this function does not inspect the individual elements of the list, it just checks if the list is empty. And so, this function can operate over any type of list. The greek letters α, β, γ etc. stand for any type. If two types are represented by the same greek letter they must have the same type. If they are not, they may have the same type, but do not have to. Functions like this are known as polymorphic. We can also use :: in our patterns, this time using it to deconstruct rather than construct the list:

This works by recursion over the list, then addition of all the resultant 1s. It takes time proportional to the length of the list. Can you see why? It also takes space proportional to the length of the list, because of the intermediate expression 1 + (1 + (1 + … which is built up before any of the + operations are evaluated – this expression must be stored somewhere whilst it is being processed. Since h is not used in the expression 1 + length t, this function is also polymorphic. Indeed we can replace h in the pattern with _ since there is no use giving a name to something we are not going to refer to:

However, since we are actually using the individual list elements (by adding them up), this function is not polymorphic – it operates over lists of type int list only. If we accidentally miss out a case, OCaml will alert us, and give an example pattern which is not matched:

There is a way to deal with the excessive space usage from the building up of a large intermediate expression 1 + 1 + 1 + … in our length function, at the cost of readability. We can “accumulate” the 1s as we go along in an extra argument. At each recursive step, the accumulating argument is increased by one. When we have finished, the total is returned:

We wrapped it up in another function to make sure we do not call it with a bad initial value for the accumulating argument. Here is an example evaluation:

Now, the space taken by the calculation does not relate in any way to the length of the list argument. Recursive functions which do not build up a growing intermediate expression are known as tail recursive. Functions can, of course, return lists too. Here is a function to return the list consisting of the first, third, fifth and so on elements in a list:

You might notice that the first two cases in the pattern match return exactly their argument. By reversing the order, we can reduce this function to just two cases:

How might we implement list append ourselves, if it was not provided? Consider a function append a b. If the list a is the empty list, the answer is simply b. But what if a is not empty? Then it has a head h and a tail t. So we can start our result list with the head, and the rest of the result is just append t b.

This takes time proportional to the length of the first list – the second list need not be processed at all. What about reversing a list? For example, we want rev [1; 2; 3; 4] to evaluate to [4; 3; 2; 1]. One simple way is to reverse the tail of the list, and append the list just containing the head to the end of it:

Two more useful functions for processing lists are take and drop which, given a number and a list, either take or drop that many elements from the list:

Note that these functions contain incomplete pattern matches – OCaml tells us so when we type them in. The function fails if the arguments are not sensible – that is, when we are asked to take or drop more elements than are in the argument list. Later on, we will see how to deal with that problem. Note also that for any sensible value of n, including zero, take n l and drop n l split the list into two parts with no gap. So drop and take often appear in pairs.

Lists can contain anything, so long as all elements are of the same type. So, of course, a list can contain lists. Here’s a list of lists of integers:

Each element of this list is of type int list (we can also omit the parentheses and write int list list). Within values of this type, it is important to distinguish the list of lists containing no elements

Questions

Two Different Ways of Thinking

There are two ways to think about this computation. One way is to imagine the actions the computer might take to calculate the result:

Alternatively, we can consider each match case to be an independent statement of truth, thinking the same way about the whole function:

It is very useful to be able to think in these two ways about functions you write, and to be able to swap between them in the mind with ease.

Sorting Things

Lists often need to be in sorted order. How might we write a function to sort a list of integers? Well, a list with zero elements is already sorted. If we do not have an empty list, we must have a head and a tail. What can we do with those? Well, we can sort the tail by a recursive call to our sort function. So, now we have the head, and an already sorted list. Now, we just need to write a function to insert the head in an already sorted list. We have reduced the problem to an easier one.

Now we just need to write the insert function. This takes an element and an already-sorted list, and returns the list with the element inserted in the right place:

Here is the whole evaluation of sort [53; 9; 2; 6; 19]. We have missed out the detail of each insert operation.

Notice that the type α list → α list rather than int list → int list. This is because OCaml’s comparison functions like <= (used inside insert) work for types other than int. For example, OCaml knows how to compare characters in alphabetical order:

How long does our sorting function take to run if the list to be sorted has n elements? Under the assumption that our argument list is arbitrarily ordered rather than sorted, each insert operation takes time proportional to n (the element might need to be inserted anywhere). We must run the insert function as many times as there are elements so, adding these all up, the sort function takes time proportional to n². You might argue that the first insert operations only have to work with a very small list, and that this fact should make the time less that n². Can you see why that is not true? What happens if the list is sorted already?

A more efficient algorithm can be found by considering a basic operation a little more complex than insert, but which still operates in time proportional to the length of the argument list. Such a function is merge, which takes two already sorted lists, and returns a single sorted list:

When x and y are both the empty list, the first case is picked because l matches the empty list. Here is how merge proceeds:

So merge can take two sorted lists, and produce a longer, sorted list, containing all the elements from both lists. So, how can we use this to sort a list from scratch? Well, we can use length, take, and drop from the previous chapter to split the list into two halves. Now, we must use a recursive call to sort each half, and then we can merge them. This is known as merge sort.

The case for the single element is required because, if we split it into two halves, of length one and zero, the recursion would not end – we would not have reduced the size of the problem.

How does msort work? Consider the evaluation of msort on the list [53; 9; 2; 6; 19]. We will skip the evaluation of the merge, drop, take, and length functions, concentrating just on msort:

From now on we will not be showing these full evaluations all the time – but when you are unsure of how or why a function works, you can always write them out on paper yourself.

How long does it take?

How long does merge sort take to run? We can visualize it with the following diagram, in which we have chosen a list of length eight (a power of two) for convenience.

[6; 4; 5; 7; 2; 5; 3; 4]
[6; 4; 5; 7][2; 5; 3; 4]
[6; 4][5; 7][2; 5][3; 4]
[6][4][5][7][2][5][3][4]
[4; 6][5; 7][2; 5][3; 4]
[4; 5; 6; 7][2; 3; 4; 5]
[2; 3; 4; 4; 5; 5; 6; 7]

In the top half of the diagram, the lists are being taken apart using take and drop, until they are small enough to already be sorted. In the bottom half, they are being merged back together.

How long does each row take? For the top half: to split a list into two halves takes time proportional to the length of the list. On the first line, we do this once on a list of length eight. On the second line, we do it twice on lists of length four, and so on. So each line takes the same time overall. For the bottom half, we have another function which takes time proportional to the length of its argument – merge – so each line in the bottom half takes time proportional to the length too.

So, how many lines do we have? Well, in the top half we have roughly log₂n, and the same for the bottom half. So, the total work done is 2 × log₂n × n, which is proportional to nlog₂n.

Questions

Loading a Program from a File

Now that we are building larger functions, we might like to store them between sessions, rather than typing them in every time. For example, compose a file like this in a text editor:

Save the file in same directory (folder) as you enter OCaml from, under the name lists.ml. We can then tell OCaml to use the contents of that file like this:

It is exactly the same as typing it in manually – the functions length and append will now be available for use. Errors and warnings will be reported as usual. Note that the #use command is not part of the OCaml language for expressions – it is just a command we are giving to OCaml.

Functions upon Functions upon Functions

Often we need to apply a function to every element of a list. For example, doubling each of the numbers in a list of integers. We could do this with a simple recursive function, working over each element of a list:

The result list does not need to have the same type as the argument list. We can write a function which, given a list of integers, returns the list containing a boolean for each: true if the number is even, false if it is odd.

It would be tedious to write a similar function each time we wanted to apply a different operation to every element of a list – can we build one which works for any operation? We will use a function as an argument:

The map function takes two arguments: a function which processes a single element, and a list. It returns a new list. We will discuss the type in a moment. For example, if we have a function halve:

Now, let us look at that type: (α → β) → α list → β list. We can annotate the individual parts:

We have to put the function f in parentheses, otherwise it would look like map had four arguments. It can have any type α → β. That is to say, it can have any argument and result types, and they do not have to be the same as each other – though they may be. The argument has type α list because each of its elements must be an appropriate argument for f. In the same way, the result list has type β list because each of its elements is a result from f (in our halve example, α and β were both int). We can rewrite our evens function to use map:

In this use of map, α was int, β was bool. We can make evens still shorter: when we are just using a function once, we can define it directly, without naming it:

This is called an anonymous function. It is defined using fun, a named argument, the -> arrow and the function definition (body) itself. For example, we can write our halving function like this:

We use anonymous functions when a function is only used in one place and is relatively short, to avoid defining it separately.

In the preceding chapter we wrote a sorting function and, in one of the questions, you were asked to change the function to use a different comparison operator so that the function would sort elements into reverse order. Now, we know how to write a version of the msort function which uses any comparison function we give it. A comparison function would have type α → α → bool. That is, it takes two elements of the same type, and returns true if the first is “greater” than the second, for some definition of “greater” – or false otherwise.

So, let us alter our merge and msort functions to take an extra argument – the comparison function:

In fact, we can ask OCaml to make such a function from an operator such as <= or + just by enclosing it in parentheses and spaces:

OCaml

# ( <= )
- : 'a -> 'a -> bool = <fun>
# ( <= ) 4 5
- : bool = true

The techniques we have seen in this chapter are forms of program reuse, which is fundamental to writing manageable large programs.

Questions

When Things Go Wrong

Some of the functions we have written so far have had a single, correct answer for each possible argument. For example, there’s no number we cannot halve. However, when we use more complicated types such as lists, there are plenty of functions which do not always have an answer – a list might not have a head or a tail, for example. Our take and drop functions were unsatisfactory in case of invalid arguments. For example, take 3 [’a’] would simply return []. This is bad practice – we are hiding errors rather than confronting them.

OCaml has a mechanism for reporting such run-time errors (these are quite different from the type errors OCaml reports when it refuses to accept a program at all). This mechanism is exceptions.

There are some built-in exceptions in OCaml. For example Division_by_zero, which is raised when a program tries to divide a number by zero:

In order to signal bad arguments in functions like take and drop, we can rewrite them using the built-in exception Invalid_argument, which also carries a message written between double quotation marks. Typically we use this to record the name of the function which failed. The following program shows take and drop rewritten to use the Invalid_argument exception using raise. Note that these functions deal with two problems of our previous versions: a negative argument, and being asked to take or drop more than the number of elements in the list.

We can define our own exceptions, using exception. They can carry information along with them, of a type we choose:

OCaml

# exception Problem;;
exception Problem
# exception NotPrime of int;;
exception NotPrime of int

We have defined two exceptions – Problem, and NotPrime which carries an integer along with it. Exceptions must start with a capital letter. The of construct can be used to introduce the type of information which travels along with an exception. Once they are defined we may use them in our own functions, using raise:

OCaml

# exception Problem;;
exception Problem
# let f x = if x < 0 then raise Problem else 100 / x;;
val f : int -> int = <fun>
# f 5
- : int = 20
# f (-1);;
Exception: Problem.

Exceptions can be handled as well as raised. An exception handler deals with an exception raised by an expression. Exception handlers are written using the try … with construct:

The safe_divide function tries to divide x by y, but if the expression x / y raises the built-in exception Division_by_zero, instead we return zero. Thus, our safe_divide function succeeds for every argument.

How do the types work here? The expression x / y has type int and so the expression we substitute in case of Division_by_zero must have the same type: int, which indeed it does. And so, our rule that each expression must have one and only one type is not violated – safe_divide always returns an int.

Here is another example. The function last returns the last element of a list:

The pattern match is incomplete, so whilst OCaml accepts the program it can fail at run-time. We can tidy up the situation by raising the built-in exception Not_found:

The type of a function gives no indication of what exceptions it might raise or handle; it is the responsibility of the programmer to ensure that exceptions which should be handled always are – this is an area in which the type system cannot help us. Later in this book, we will see some alternatives to exceptions for occasions when they are likely to be frequently raised, allowing the type system to make sure we have dealt with each possible circumstance.

Questions

Looking Things Up

Many programs make use of a structure known as a dictionary. A real dictionary is used for associating definitions with words; we use “dictionary” more generally to mean associating some unique keys (like words) with values (like definitions). For example, we might like to store the following information about the number of people living in each house in a road:

The house number is the key, the number of people living in the house is the value. The order of keys is unimportant – we just need to be able to associate each key with one (and only one) value. It would be very inconvenient to store two lists, one of house numbers and one of people. For one thing, we would have way of guaranteeing the two lists were of equal length. What we would like is a way of representing pairs like (1, 4) and then having a single list of those. To make a pair in OCaml, just write it with parentheses and a comma:

It has the type int × int, which we pronounce as “int cross int”. When printed on the screen, * is used instead of × just as with multiplication. The two parts of the pair need not have the same type:

We can write simple functions to extract the first and second element using pattern matching:

In fact, since pairs can only take one form (unlike lists, which have two forms: empty or consisting of a head and a tail), OCaml lets us use the pattern directly in place of the argument:

Notice the parentheses around int × int in the type. Otherwise, it would be the type of a pair of an integer and an integer list:

What operations might we want on dictionaries? We certainly need to look up a value given a key:

For example, lookup 4 census evaluates to 3, whereas lookup 9 census raises Not_found. Another basic operation is to add an entry (we must replace it if it already exists, to maintain the property that each key appears at most once in a dictionary).

For example, add 6 2 [(4, 5); (6, 3)] evaluates to [(4, 5); (6, 2)] (the value for key 6 is replaced), whereas add 6 2 [(4, 5); (3, 6)] evaluates to [(4, 5); (3, 6); (6, 2)] (the new entry for key 6 is added). Removing an element is easy:

The function always succeeds – even if the key was not found. We can use exception handling together with our lookup operation to build a function which checks if a key exists within a dictionary:

If lookup k d succeeds, true will be returned. If not, an exception will be raised, which key_exists will handle itself, and return false. Note that we did not give a name to the result of lookup k l because we always return true if it succeeds.

Pairs are just a particular instance of a more general construct – the tuple. A tuple may contain two or more things. For example, (1, false, ’a’) has type int × bool × char.

Questions

More with Functions

We have been considering functions like this as taking two arguments and returning a result. In fact, the truth is a little different. The type int → int → int can also be written as int → (int → int). OCaml lets us omit the parentheses because → is a right-associative operator in the language of types. This gives us a clue.

This would be of no particular interest to us, except for one thing: we can give a function with two arguments just one argument at a time, and it turns out to be rather useful. For example:

OCaml

# let add x y = x + y
val add : int -> int -> int = <fun>
# let f = add 6
val f : int -> int = <fun>
# f 5
- : int = 11

Here, we have defined a function f by applying just one argument to add. This gives a function of type int → int which adds six to any number. We then apply 5 to this function, giving 11. When defining f, we used partial application (we applied only some of the arguments). In fact, even when applying all the arguments at once, we could equally write (add 6) 5 rather than add 6 5. We can add six to every element in a list:

Here, add 6 has the type int → int, which is an appropriate type to be the first argument to map when mapping over a list of integers. We can use partial application to simplify some examples from earlier in the book. We mentioned that you can write, for example, ( * ) to produce a function from an operator. It has type int → int → int. We may partially apply this function, so instead of writing

Recall the function to map something over a list of lists from the questions to Chapter 6:

Can you see why? The partially applied function map f is of type α list → β list, which is exactly the right type to pass to map when mapping over lists of lists. In fact, we can go even further and write:

Here, map (map f) has type α list list → β list list so when an f is supplied to mapl, a function is returned requiring just the list. This is partial application at work again.

You can see the real structure of multiple-argument functions, by writing add using anonymous functions:

This makes it more obvious that our two-argument add function is really just composed of one-argument functions, but let add x y = x + y is much clearer! We can apply one or more arguments at a time, but they must be applied in order. Everything in this chapter also works for functions with more than two arguments.

Summary

The function f x y has type α → β → γ which can also be written α → (β → γ). Thus, it takes an argument of type α and returns a function of type β → γ which, when you give it an argument of type β returns something of type γ. And so, we can apply just one argument to the function f (which is called partial application), or apply both at once. When we write let f x y = … this is just shorthand for let f = fun x -> fun y -> …

Questions

New Kinds of Data

So far, we have considered the simple types int, bool, char, the compound type list, and tuples. We have built functions from and to these types. It would be possible to encode anything we wanted as lists and tuples of these types, but it would lead to complex and error-strewn programs. It is time to make our own types. New types are introduced using type. Here’s a type for colours:

The name of our new type is colour. It has four constructors, written with an initial capital letter: Red, Green, Blue, and Yellow. These are the possible forms a value of type colour may take. Now we can build values of type colour:

Let us extend our type to include any other colour which can be expressed in the RGB (Red, Green, Blue) colour system (each component ranges from 0 to 255 inclusive, a standard range giving about 16 million different colours).

We use of in our new constructor, to carry information along with values built with it. Here, we are using something of type int × int × int. Notice that the list cols of type colour list contains varying things, but they are all of the same type, as required by a list. We can write functions by pattern matching over our new type:

Types may contain a type variable like α to allow the type of part of the new type to vary – i.e. for the type to be polymorphic. For example, here is a type used to hold either nothing, or something of any type:

OCaml

# type 'a option = None | Some of 'a;;
type 'a option = None | Some of 'a

We can read this as “a value of type α option is either nothing, or something of type α”. For example:

The option type is useful as a more manageable alternative to exceptions where the lack of an answer is a common (rather than genuinely exceptional) occurrence. For example, here is a function to look up a value in a dictionary, returning None instead of raising an exception if the value is not found:

Now, there is no need to worry about exception handling – we just pattern match on the result of the function.

In addition to being polymorphic, new types may also be recursively defined. We can use this functionality to define our own lists, just like the built-in lists in OCaml but without the special notation:

OCaml

# type 'a sequence = Nil | Cons of 'a * 'a sequence;;
type 'a sequence = Nil | Cons of 'a * 'a sequence

We have called our type sequence to avoid confusion. It has two constructors: Nil which is equivalent to [], and Cons which is equivalent to the :: operator. Cons carries two pieces of data with it – one of type α (the head) and one of type α sequence (the tail). This is the recursive part of our definition. Now we can make our own lists equivalent to OCaml’s built-in ones:

Now you can see why getting at the last element of a list in OCaml is harder than getting at the first element – it is deeper in the structure. Let us compare some functions on OCaml lists with the same ones on our new sequence type. First, the ones for built-in lists.

Notice how all the conveniences of pattern matching such as completeness detection and the use of the underscore work for our own types too.

A Type for Mathematical Expressions

Our sequence was an example of a recursively-defined type, which can be processed naturally by recursive functions. Mathematical expressions can be modeled in the same way. For example, the expression 1 + 2 × 3 could be drawn like this:

Notice that, in this representation, we never need parentheses – the diagram is unambiguous. We can evaluate the expression by reducing each part in turn:

Building our own types leads to clearer programs with more predictable behaviour, and helps us to think about a problem – often the functions are easy to write once we have decided on appropriate types.

Questions

Growing Trees

We have used lists to represent collections of elements of like type but varying length, and tuples to represent collections of things of any type but fixed length. Another common type is the binary tree, which is used to represent structures which branch, such as the arithmetical expressions we constructed in the last chapter.

How can we represent such trees using an OCaml type? When we built our version of the OCaml list type, we had two constructors – Cons to hold a head and a tail, and Nil to represent the end of the list. With a tree, we need a version of Cons which can hold two tails – the left and right, and we still need a version of Nil.

Our type is called tree, and is polymorphic (can hold any kind of data at the branches). There are two constructors: Br for branches, which hold three things in a tuple: an element, the left sub-tree, and the right sub-tree. If it is not a Br, it is a Lf (leaf), which is used to signal that there is no left, or no right sub-tree. Here are some representations in our new type of integer trees:

The empty tree is simply Lf. You can see now why we used abbreviated constructor names – even small trees result in long textual representations. Let us write some simple functions on trees. To calculate the number of elements in the tree, we just count one for each branch, and zero for each leaf:

Notice that the recursive function follows the shape of the recursive type. A similar function can be used to add up all the integers in an int tree:

How can we calculate the maximum depth of a tree? The depth is the longest path from the root (top) of the tree to a leaf.

We defined a function max which returns the larger of two integers. Then, in our main function, we count a leaf as zero depth, and calculate the depth of a branch as one plus the maximum of the left and right sub-trees coming from that branch. Now consider extracting all of the elements from a tree into a list:

Notice that we chose to put all the elements on the left branch before the current element, and all the elements in the right branch after. This is arbitrary (it is clear that there are multiple answers to the question “How can I extract all the elements from a tree as a list?”). Before we consider real applications of trees, let us look at one more function. Here is how to map over trees:

Notice the similarity to our map function for lists, both in the type and the definition.

Using trees to build better dictionaries

We have seen that arithmetic expressions can be drawn as trees on paper, and we have designed an OCaml data type for binary trees to hold any kind of element. Now it is time to introduce the most important application of trees: the binary search tree, which is another way of implementing the dictionary data structure we described in Chapter 7.

The most important advantage of a tree is that it is often very much easier to reach a given element. When searching in a dictionary defined as a list, it took on average time proportional to the number of items in the dictionary to find a value for a key (the position of the required entry is, on average, halfway along the list). If we use a binary tree, and if it is reasonably nicely balanced in shape, that time can be reduced to the logarithm base two of the number of elements in the dictionary. Can you see why?

We can use our existing tree type. In the case of a dictionary, it will have type (α × β) tree, in other words a tree of key-value pairs where the keys have some type α and the values some type β. For this example, we are going to be using another built-in type, string. A string is a sequence of characters written between double quotation marks. We have seen these as messages attached to exceptions, but they are a basic OCaml type too.

So, our tree representing a dictionary mapping integers like 1 to their spellings like “one” would have type (int × string) tree:

Br ((3, "three"), Br ((1, "one"), Lf, Br ((2, "two"), Lf, Lf)), Br ((4, "four"), Lf, Lf))

If we arrange the tree such that, at each branch, everything to the left has a key less than the key at the branch, and everything to the right has a key greater than that at the branch, we have a binary search tree.

Lookup is simple: start at the top, and if we have not found the key we are looking for, go left or right depending upon whether the required key is smaller or larger than the value at the current branch. If we reach a leaf, the key was not in the tree (assuming the tree is a well-formed binary search tree), and we raise an exception.

How can we insert a new key-value pair into an existing tree? We can find the position to insert by using the same procedure as the lookup function – going left or right at each branch as appropriate. If we find an equal key, we put our new value there instead. Otherwise, we will end up at a leaf, and this is the insertion point – thus, if the key is not in the dictionary when insert is used, it will be added in place of an existing leaf.

For example, if we wish to insert the value "zero" for the key 0 in the tree drawn above, we would obtain

The shape of the tree is dependent upon the order of insertions into the tree – if they are in order (or reverse order), we obtain a rather inefficient tree – no better a dictionary than a list in fact. However, on average, we obtain a reasonably balanced tree, and logarithmic lookup and insertion times.

Lists and trees are examples of data structures. The design of an algorithm and its data structures are intimately connected.

Questions

In and Out

We have considered a function (and indeed, a whole program composed of many functions) to take a chunk of data, do some calculations, and then produce a result. This assumption has allowed us to write neat, easily understood programs.

However, some computer programs do not have all data available at the beginning of the program (or even the beginning of a given function). The user might provide new data interactively, or the program might fetch data from the internet, or two or more programs might communicate with one another in real time.

We must learn how to write such programs, whilst understanding the utility of restricting such complications to as small a part of the program as possible – interactivity turns out to be surprisingly hard to reason about, since the result of a function may no longer depend only on its initial argument.

Writing to the screen

OCaml has a built-in function print_int which prints an integer to the screen:

What is the type of this function? Well, it is a function, and it takes an integer as its argument. It prints the integer to the screen, and then returns…what? Nothing! OCaml has a special type to represent nothing, called unit. There is exactly one thing of type unit which is written () and is called “unit”. So, the function print_int has type int → unit.

There is another built-in function print_string of type string → unit to print a string, and another print_newline to move to the next line. This function has type unit → unit because it requires no substantive argument and produces no useful result. It is only wanted for its “side-effect”.

We can produce several side-effects, one after another, using the ; symbol. This evaluates the expression on its left hand side, throws away the result (which will normally be unit anyway), and then evaluates the expression to its right hand side, returning the result (which is often unit too). The type of the expression x ; y is thus the type of y. For example, we can write a function to write to the screen an int × string pair as an integer on one line, followed by a string on another:

Notice we have added a second call to print_newline, so that our function can be called several times in a row without intervening calls to print_newline. We wrote the function applications all on one line to emphasize that ; behaves a little like an operator. However, for convenience, we would normally write it like this:

This makes it look rather like ; is used to end each expression, but just remember that ; is a bit like an operator – notice that there is no ; after the last print_newline (). Let us see how print_dict_entry is used in practice:

How might we print a whole dictionary (represented as a list of entries) this way? Well, we could write our own function to iterate over all the entries:

Better, we can extract this method into a more general one, for doing an action on each element of a list:

OCaml

# print_dict [(1, "one"); (2, "two"); (3, "three")];;
1
one
2
two
3
three
- : unit = ()

Reading from the keyboard

Now we should like to write a function to read a dictionary as an (int × string) list. We will use two built-in OCaml functions. The function read_int of type unit → int waits for the user to type in an integer and press the Enter key. The integer is then returned. The function read_line of type unit → string waits for the user to type any string and press the enter key, returning the string.

We want the user to enter a series of keys and values (integers and strings), one per line. They will enter zero for the integer to indicate no more input. Our function will take no argument, and return a dictionary of integers and strings, so its type will be unit → (int × string) list.

OCaml

# read_dict ();;
1
oak
2
ash
3
elm
0
- : (int * string) list = [(1, "oak"); (2, "ash"); (3, "elm")]

But there is a problem. What happens if we type in something which is not an integer when an integer is expected?

OCaml

# read_dict ();;
1
oak
ash
Exception: Failure "int_of_string".

We must handle this exception, and ask the user to try again. Here’s a revised function:

OCaml

# read_dict ();;
1
oak
ash
This is not a valid integer. Please try again.
2
ash
3
elm
0
- : (int * string) list = [(1, "oak"); (2, "ash"); (3, "elm")]

Using files

It is inconvenient to have to type new data sets in each time, so we will write functions to store a dictionary to a file, and then to read it back out again.

OCaml has some basic functions to help us read and write from places data can be stored, such as files. Places we can read from have type in_channel and places we can write to have type out_channel. Here are functions for writing a dictionary of type (int × string) to a channel:

We are using the functions output_string and output_char to write the data in the same format we used to print it to the screen. There is no output_int function, so we have used the built-in string_of_int function to build a string from the integer. The character ’\n’ is a special one, representing moving to the next line (there is no output_newline function).

How do we obtain such a channel? The function open_out gives an output channel for filename given as a string. It has type string → out_channel. After we have written the contents to the file, we must call close_out (which has type out_channel → unit) to properly close the file.

After running this function, you should find a file of the chosen name on your computer in the same folder from which you are running OCaml. If you are not sure where the file is being put, consult the documentation for your OCaml implementation, or use a full file path such as "C:/file.txt" or "/home/yourname/file.txt", again depending on your system. In the following example, we are reading a dictionary from the user and writing it to file as file.txt:

OCaml

# dictionary_to_file "file.txt" (read_dict ());;
1
oak
2
ash
3
elm
0
- : unit

We have written a function entry_of_channel to read a single integer and string (one element of our dictionary) from an input channel using the built-in functions input_line and int_of_string, and a function dictionary_of_channel to read all of them as a dictionary. It makes use of the built-in exception End_of_file to detect when there is no more in the file. Now, we can build the main function to read our dictionary from the file:

The process is the same as for dictionary_to_file but we use open_in and close_in instead of open_out and close_out.

OCaml

# dictionary_of_file "file.txt";;
- : (int * string) list = [(1, "oak"); (2, "ash"); (3, "elm")]

Summary of functions

We have introduced the types unit, in_channel, and out_channel, and the exception End_of_file. Here are the functions we have used:

Questions

Putting Things in Boxes

So far, we have considered “pure” functions which have no side-effects, and functions which have the side-effect of reading or writing information to and from, for example, files. When we assigned a value to a name, that value could never change. Sometimes, it is convenient to allow the value of a name to be changed – some algorithms are more naturally expressed in this way.

OCaml provides a construct known as a reference which is a box in which we can store a value. We build a reference using the built-in function ref of type α → α ref. For example, let us build a reference with initial contents 0. It will have type int ref.

OCaml tells us that x is a reference of type int ref which currently has contents 0. We can extract the current contents of a reference using the ! operator, which has type α ref → α.

The := operator has type α ref → α → unit, since it takes a reference and a new value to put in it, puts the value in, and returns nothing. It is only useful for its side-effect. Now, we can get the contents with ! again.

Notice that p is unchanged. Here’s a function to swap the contents of two references:

We needed to use a temporary name t to store the contents of a. Can you see why?

This type of programming, which consists of issuing a number of commands, in order, about which references are to be altered and how, is known as imperative programming. OCaml provides some useful structures for imperative programming with references. We will look at these quickly now, and in a moment build a bigger example program to show why they are useful.

For readability, OCaml lets us miss out the else part of the if … then … else … construct if it would just be (), which is if we are doing nothing in the else case, so

and if x is not zero, the expression will just evaluate to (). Due to this, when putting imperative code inside if … then … else … constructs, we need to surround the inner imperative expressions with parentheses so the meaning is unambiguous:

Doing it again and again

There are two ways to repeat an action. To perform an action a fixed number of times, we use the for … = … to … do … done construct. For example,

for x = 1 to 5 do print_int x; print_newline () done

evaluates the expression print_int x; print_newline () five times: once where x is 1, once where x is 2 etc, so the result is:

# for x = 1 to 5 do print_int x; print_newline () done;
1
2
3
4
5
- : unit = ()

This is known as a “for loop”. Note that the type of the whole for … = … to … do … done expression is unit irrespective of the type of the expression(s) inside it.

There is another looping construct – this time for evaluating an expression repeatedly until some condition is true. This is the while … do … done construct. It takes a boolean condition, and evaluates a given expression repeatedly, zero or more times, until the boolean condition is false. For example, here is a function which, given a positive integer, calculates the lowest power of two greater than or equal to that number (i.e. for the argument 37, the result will be 64).

The while loop continues until the contents of the reference t is greater than or equal to x. At that point, it ends, and the contents of t is returned from the function. Again, note that the type of the whole while … do … done construct is unit.

Example: text file statistics

We are going to write a program to count the number of words, sentences and lines in a text file. We shall consider the opening paragraph of Kafka’s “Metamorphosis”.

There are newline characters at the end of each line, save for the last. You can cut and paste or type this into a text file to try these examples out. Here, it is saved as gregor.txt.

We will just count lines first. To this, we will write a function channel_statistics to gather the statistics by reading an input channel and printing them. Then we will have a function to open a named file, call our first function, and close it again.

Notice the use of true as the condition for the while construct. This means the computation would carry on forever, except that the End_of_file exception must eventually be raised. Note also that OCaml emits a warning when reading the channel_statistics function:

This is an example of a warning we can ignore – we are not using the actual value line yet, since we are just counting lines without looking at their content. Running our program on the example file gives this:

OCaml

# file_statistics "gregor.txt";;
There were 8 lines.
- : unit = ()

Let us update the program to count the number of words, characters, and sentences. We will do this simplistically, assuming that the number of words can be counted by counting the number of spaces, and that the sentences can be counted by noting instances of ’.’, ’!’, and ’?’. We can extend the channel_statistics function appropriately – file_statistics need not change:

We have used the built-in function String.iter of type (char → unit) → string → unit which calls a function we supply on each character of a string.

Substituting this version of channel_statistics (if you are cutting and pasting into OCaml, be sure to also paste file_statistics in again afterwards, so it uses the new channel_statistics), gives the following result on our example text:

OCaml

# file_statistics "gregor.txt";;
There were 8 lines, making up 464 characters with 80 words in 4 sentences.
- : unit = ()

Adding character counts

We should like to build a histogram, counting the number of times each letter of the alphabet or other character occurs. It would be tedious and unwieldy to hold a hundred or so references, and then pattern match on each possible character to increment the right one. OCaml provides a data type called array for situations like this.

An array is a place for storing a fixed number of elements of like type. We can introduce arrays by using [| and |], with semicolons to separate the elements:

OCaml

# let a = [|1; 2; 3; 4; 5|];;
val a : int array = [|1; 2; 3; 4; 5|]

We can access an element inside our array in constant time by giving the position of the element (known as the subscript) in parentheses, after the array name and a period:

Notice that the first element has subscript 0, not 1. We can update any of the values in the array, also in constant time, like this:

# a.(4) <- 100;;
- : unit = ()
# a;;
a : int array = [|1; 2; 3; 4; 100|]

If we try to access or update an element which is not within range, an exception is raised:

There are some useful built-in functions for dealing with arrays. The function Array.length of type α array → int returns the length of an array:

In contrast to finding the length of a list, the time taken by Array.length is constant, since it was fixed when the array was created. The Array.make function is used for building an array of a given length, initialized with given values. It takes two arguments – the length, and the initial value to be given to every element. It has type int → α → α array.

# Array.make 6 true;;
- : bool array = [|true; true; true; true; true; true|]
# Array.make 10 'A';;
- : char array = [|'A'; 'A'; 'A'; 'A'; 'A'; 'A'; 'A'; 'A'; 'A'; 'A'|]
# Array.make 3 (Array.make 3 5);;
- : int array array = [|[|5; 5; 5|]; [|5; 5; 5|]; [|5; 5; 5|]|]

Back to our original problem. We want to store a count for each possible character. We cannot subscript our arrays with characters directly, but each character has a special integer code (its so-called “ASCII code”, a common encoding of characters as integers in use since the 1960s), and we can convert to and from these using the built-in functions int_of_char and char_of_int. For example:

OCaml

# int_of_char 'C';;
- : int = 67
# char_of_int 67;;
- : char = 'C'

The numbers go from 0 to 255 inclusive (they do not all represent printable characters, for example the newline character ’\n’ has code 10). So, we can store our histogram as an integer array of length 256.

Our main function is getting rather long, so we will write a separate one which, given the completed array prints out the frequencies. If there were no instances of a particular character, no line is printed for that character.

Now, we can alter our channel_statistics to create an appropriate array, and update it, once again using String.iter:

OCaml

# file_statistics "gregor.txt";;
There were 8 lines, making up 464 characters with 80 words in 4 sentences.
Character frequencies:
For character ' ' (character number 32) the count is 80.
For character ',' (character number 44) the count is 6.
For character '-' (character number 45) the count is 1.
For character '.' (character number 46) the count is 4.
For character 'G' (character number 71) the count is 1.
For character 'H' (character number 72) the count is 2.
For character 'O' (character number 79) the count is 1.
For character 'S' (character number 83) the count is 1.
For character 'T' (character number 84) the count is 1.
For character 'a' (character number 97) the count is 24.
For character 'b' (character number 98) the count is 10.
For character 'c' (character number 99) the count is 6.
For character 'd' (character number 100) the count is 25.
For character 'e' (character number 101) the count is 47.
For character 'f' (character number 102) the count is 13.
For character 'g' (character number 103) the count is 5.
For character 'h' (character number 104) the count is 22.
For character 'i' (character number 105) the count is 30.
For character 'k' (character number 107) the count is 4.
For character 'l' (character number 108) the count is 23.
For character 'm' (character number 109) the count is 15.
For character 'n' (character number 110) the count is 21.
For character 'o' (character number 111) the count is 27.
For character 'p' (character number 112) the count is 3.
For character 'r' (character number 114) the count is 20.
For character 's' (character number 115) the count is 24.
For character 't' (character number 116) the count is 21.
For character 'u' (character number 117) the count is 6.
For character 'v' (character number 118) the count is 4.
For character 'w' (character number 119) the count is 6.
For character 'y' (character number 121) the count is 10.
For character 'z' (character number 122) the count is 1.
- : unit = ()

The most common character is the space. The most common alphabetic character is ’e’.

Questions

The Other Numbers

The only numbers we have considered until now have been the integers. For a lot of programming tasks, they are sufficient. And, except for their limited range and the possibility of division by zero, they are easy to understand and use. However, we must now consider the real numbers.

It is clearly not possible to represent all numbers exactly – they might be irrational like π or e and have no finite representation. For most uses, a representation called floating-point is suitable, and this is how OCaml’s real numbers are stored. Not all numbers can be represented exactly, but arithmetic operations are very quick.

Floating-point numbers have type float. We can write a floating-point number by including a decimal point somewhere in it. For example 1.6 or 2. or 386.54123. Negative floating-point numbers are preceded by the -. characters just like negative integers are preceded by the - character. Similarly, we write +. -. *. /. for the standard arithmetic operators on floating-point numbers. Exponentiation is written with the ** operator.

OCaml

# 1.5;;
- : float = 1.5
# 6.;;
- : float = 6.
# -.2.3456;;
- : float = -2.3456
# 1.0 +. 2.5 *. 3.0;;
- : float = 8.5
# 1.0 /. 1000.0;;
- : float = 0.001
# 1. /. 100000.;;
- : float = 1e-05
# 3000. ** 10.;;
- : float = 5.9049e+34
# 3.123 -. 3.;;
- : float = 0.12300000000000022

Notice an example of the limits of precision in floating-point operations in the final lines. Note also that very small or very large numbers are written using scientific notation (such as 5.9049e+34 above). We can find out the range of numbers available:

OCaml

# max_float;;
- : float = 1.79769313486231571e+308
# min_float;;
- : float = 2.22507385850720138e-308

Working with floating-point numbers requires care, and a comprehensive discussion is outside the scope of this book. These challenges exist in any programming language using the floating-point system. For example, evaluating 1. /. 0. gives the special value infinity (there is no Division_by_zero exception for floating-point operations). There are other special values such as neg_infinity and nan (“not a number”). We will leave these complications for now – just be aware that they are lurking and must be confronted when writing robust numerical programs.

A number of standard functions are provided, both for operating on floating-point numbers and for converting to and from them, some of which are listed here:

Let us write some functions with floating-point numbers. We will write some simple operations on vectors in two dimensions. We will represent a point as a pair of floating-point numbers of type float × float such as (2.0, 3.0). We will represent a vector as a pair of floating-point numbers too. Now we can write a function to build a vector from one point to another, one to find the length of a vector, one to offset a point by a vector, and one to scale a vector to a given length:

Notice that we have to be careful about division by zero, just as with integers. We have used tuples for the points because it is easier to read this way – we could have passed each floating-point number as a separate argument instead, of course.

Floating-point numbers are often essential, but must be used with caution. You will discover this when answering the questions for this chapter. Some of these questions require using the built-in functions listed in the table above.

Questions

The OCaml Standard Library

OCaml is provided with a wide range of useful built-in functions, in addition to the ones we have already seen, called the OCaml Standard Library. These functions are divided into modules, one for each area of functionality (in the next chapter, we will learn how to write our own modules). Here are a few examples of modules in the standard library:

We will take the List module as an example. You can find the documentation for the OCaml Standard Library installed with your copy of OCaml, or on the internet.

The functions from a module can be used by putting a period (full stop) between the module name and the function. For example the length function in the List module can be used like this:

We will talk about val in the next chapter. Sometimes, more information is required:

In the documentation, we are told what the function does for each argument, and what exceptions may be raised. Functions which are not tail-recursive and so may fail on huge arguments are marked as such.

The questions for this chapter use functions from the standard library, so you will need to have a copy of the documentation to hand.

Questions

Building Bigger Programs

So far we have been writing little programs and testing them interactively in OCaml. However, to conquer the complexity of the task of writing larger programs, tools are needed to split them into well-defined modules, each with a given set of types and functions. We can then build big systems without worrying that some internal change to a single module will affect the whole program. This process of modularization is known as abstraction, and is fundamental to writing large programs, a discipline sometimes called software engineering.

In this chapter, you will have to create text files and type commands into the command prompt of your computer. If you are not sure how to do this, or the examples in this chapter do not work for you, ask a friend or teacher. In particular, if using Microsoft Windows, some of the commands may have different names.

Making a module

We will be building a modular version of our text statistics program from Chapter 13. First, write the text file shown in below (but not the italic annotations) and save it as textstat.ml (OCaml programs live in files with lowercase names ending in .ml).

The first line is a comment. Comments in OCaml are written between (* and *). We use comments in large programs to help the reader (who might be someone else, or ourselves some time later) to understand the program.

We have then introduced a type for our statistics. This will hold the number of words, characters, and sentences. We have then written a function stats_from_channel which for now just returns zeros for all the statistics.

Now, we can issue a command to turn this program into a pre-processed OCaml module. This compiles the program into an executable. The module can then be loaded into interactive OCaml, or used to build standalone programs. Execute the following command:

You can see that the name of the OCaml compiler is ocamlc. If there are errors in textstat.ml they will be printed out, including the line and character number of the problem. You must fix these, and try the command again. If compilation succeeds, you will see the file textstat.cmo in the current directory. There will be other files, but we are not worried about those yet. Let us load our pre-compiled module into OCaml:

OCaml

# #load "textstat.cmo";;
# Textstat.stats_from_file "gregor.txt";;
- : int * int * int * int = (0, 0, 0, 0)

Note that #load is different from our earlier #use command – that was just reading a file as if it had been cut and pasted – we are really loading the compiled module here.

Filling out the module

Let us add a real stats_from_channel function, to produce a working text statistics module. We will also add utility functions for retrieving individual statistics from the stats type:

OCaml

# #load "textstat.cmo";;
# let s = Textstat.stats_from_file "gregor.txt";;
val s : Textstat.stats = (8, 464, 80, 4)
# Textstat.lines s;;
- : int = 8
# Textstat.characters s;;
- : int = 464
# Textstat.words s;;
- : int = 80
# Textstat.sentences s;;
- : int = 4

You might ask why we need the functions lines, characters etc. when the information is returned in the tuple. Let us discuss that now.

Making an interface

We said that modules were for creating abstractions, so that the implementation of an individual module could be altered without changing the rest of the program. However, we have not achieved that yet – the details of the internal type are visible to the program using the module, and that program would break if we changed the type of stats to hold an additional statistic. In addition, the internal count_words function is available, even though the user of the module is not expected to use it.

What we would like to do is to restrict the module so that only the types and functions we want to be used directly are available. For this, we use an interface. Interfaces are held in files ending in .mli, and we can write one for our module. Here is our interface:

In this interface, we have exposed every type and function. Types are written in the same way as in the .ml file. Functions are written with val, followed by the name, a colon, and the type of the function. We can compile this by giving the .mli file together with the .ml file when using ocamlc:

The ocamlc compiler has created at least two files: textstat.cmo as before and textstat.cmi (the compiled interface). You should find this operates exactly as before when loaded into OCaml. Now, let us remove the definition of the type from the interface, to make sure that the stats type is hidden, and its parts can only be accessed using the lines, characters, words, and sentences functions. We will also remove the declaration for stats_from_channel to demonstrate that functions we do not need can be hidden too:

Now, if we compile the program again with ocamlc textstat.mli textstat.ml, we see that the stats_of_channel function is now not accessible, and the type of stats is now hidden, or abstract.

OCaml

# #load "textstat.cmo";;
# let s = Textstat.stats_from_file "gregor.txt";;
val s : Textstat.stats = <abstr>
# Textstat.lines s;;
- : int = 8
# Textstat.characters s;;
- : int = 464
# Textstat.words s;;
- : int = 80
# Textstat.sentences s;;
- : int = 4
# Textstat.stats_from_channel;;
Error: Unbound value Textstat.stats_from_channel

We have successfully separated the implementation of our module from its interface – we can now change the stats type internally to hold extra statistics without invalidating existing programs. This is abstraction in a nutshell.

Building standalone programs

Now it is time to cut ourselves free from interactive OCaml, and build standalone programs which can be executed directly. Let us add another file stats.ml which will use functions from the Textstat module to create a program which, when given a file name, prints some statistics about it:

Let us compile this standalone program using ocamlc, giving a name for the executable program using the -o option:

$ ./stats gregor.txt
Words: 80
Characters: 464
Sentences: 4
Lines: 8
$ ./stats not_there.txt
An error occurred: Sys_error("not_there.txt: No such file or directory")
$ ./stats
Usage: stats <filename>

This output might look different on your computer, depending on your operating system. On most computers, the ocamlopt compiler is also available. If we type

we obtain an executable which is much faster than before, and completely independent of OCaml – it can run on any computer which has the same processor and operating system (such as Windows or Mac OS X) as yours, with no need for an OCaml installation. On the other hand, the advantage of ocamlc is that it produces a program which can run on any computer, so long as OCaml support is installed.

Questions

Answers to Questions

1. Starting Off

The expression 17 is of type int and is a value already. The expression 1 + 2 * 3 + 4 is of type int and evaluates to the value 11, since the multiplication is done first. The expression 800 / 80 / 8 has type int. It is the same as (800 / 80) / 8 rather than 800 / (80 / 8) and evaluates to 1.

The expression 400 > 200 has type bool because this is the type of the result of the comparison operator >. It evaluates to true. Similarly, 1 <> 1 has type bool and evaluates to false. The expression true || false is of type bool and evaluates to true since one of the operands is true. Similarly, true && false evaluates to false since one of the operands is false. The expression if true then false else true evaluates to false since the first (then) part of the conditional expression is chosen, and takes the place of the entire expression.

The expression ’%’ is of type char and is already a value. The expression ’a’ + ’b’ has no type – it gives a type error because the + operator does not operate on characters.

The mod operator is of higher precedence than the + operator. So 1 + 2 mod 3 and 1 + (2 mod 3) are the same expression, evaluating to 1 + 2 which is 3, but (1 + 2) mod 3 is the same as 3 mod 3, which is 0.

The expression evaluates to 11. The programmer seems to be under the impression that spacing affects evaluation order. It does not, and so this use of space is misleading.

The expression max_int + 1 evaluates to a number equal to min_int. Likewise, min_int - 1 evaluates to a number equal to max_int. The number line “wraps around”. This leads to the odd situation that max_int + 1 < max_int evaluates to true. It follows that when writing programs, we must be careful about what happens when numbers may be very large or very small.

We will talk about such exceptions later in the book. They are used for program errors which cannot necessarily be found just by looking at the program text, but are only discovered during evaluation.

This illustrates how even simple mathematical operators require careful specification when programming – we must be explicit about the rules.

It prevents unexpected values: what would happen if an integer other than 1 and 0 was calculated in the program – what would it mean? It is better just to use a different type. We can then show more easily that a program is correct.

The lowercase characters are in alphabetical order, for example ’p’ < ’q’ evaluates to true. The uppercase characters are similarly ordered. The uppercase letters are all “smaller” than the lowercase characters, so for example ’A’ < ’a’ evaluates to true. For type bool, false is considered “less than” true.

2. Names and Functions

Just take in an integer and return the number multiplied by ten. The function takes and returns an integer, so the type is int → int.

We must take two integer arguments, and use the && and <> operators to test if they are both non-zero. So the result will be of type bool. The whole type will therefore be int → int → bool.

OCaml

# let both_non_zero x y =
x <> 0 && y <> 0;;
val both_non_zero : int -> int -> bool = <fun>

Our function should take an integer, and return another one (the sum). So, it is type will be int → int. The base case is when the number is equal to 1. Then, the sum of all numbers from 1…1 is just 1. If not, we add the argument to the sum of all the numbers from 1…(n−1).

OCaml

# let rec sum n =
if n = 1 then 1 else n + sum (n - 1);;
val sum : int -> int = <fun>

The function is recursive, so we used let rec instead of let. What happens if the argument given is zero or negative?

The function will have type int → int → int. A number to the power of 0 is 1. A number to the power of 1 is itself. Otherwise, the answer is the current n multiplied by n^x − 1.

OCaml

# let rec power x n =
if n = 0 then 1 else
(if n = 1 then x else
x * power x (n - 1));;
val power : int -> int -> int = <fun>

Notice that we had to put one if … then … else inside the else part of another to cope with the three different cases. The parentheses are not actually required, though, so we may write it like this:

OCaml

# let rec power x n =
if n = 0 then 1 else
if n = 1 then x else
x * power x (n - 1);;
val power : int -> int -> int = <fun>

In fact, we can remove the case for n = 1 since power x 1 will reduce to x * power x 0 which is just x.

The function isconsonant will have type char → bool. If a lower case character in the range ’a’…’z’ is not a vowel, it must be a consonant. So we can reuse the isvowel function we wrote earlier, and negate its result using the not function:

OCaml

# let isconsonant c = not (isvowel c);;
val isconsonant : char -> bool = <fun>

The expression is the same as let x = 1 in (let x = 2 in x + x), and so the result is 4. Both instances of x in x + x evaluate to 2 since this is the value assigned to the name x in the nearest enclosing let expression.

We could simply return 0 for a negative argument. The factorial of 0 is 1, so we can change that too, and say our new function finds the factorial of any non-negative number:

OCaml

# let rec factorial x =
if x < 0 then 0 else
if x = 0 then 1 else
x * factorial (x - 1);;
val factorial : int -> int = <fun>

Note that factorial can fail in other ways too – if the number gets too big and “wraps around”. For example, on the author’s computer, factorial 40 yields -2188836759280812032.

3. Case by Case

We can just pattern match on the boolean. It does not matter, in this instance, which order the two cases are in.

(A match case belongs to its nearest enclosing match). So the expression evaluates to 5.

These two solutions have differing behaviour upon erroneous arguments (such as punctuation). Can you see why?

4. Listing Things

But we can perform the same trick as before, by reversing the cases, to reduce their number:

This is like counting the length of a list, but we only count if the current element is true.

We can use an accumulating argument in an auxiliary function to make a tail recursive version:

To make a palindrome from any list, we can append it to its reverse. To check if a list is a palindrome, we can compare it for equality with its reverse (the comparison operators work over almost all types).

We pattern match with three cases. The empty list, where we have reached the last element, and where we have yet to reach it.

We can build a tail recursive version by adding an accumulating list, and reversing it when finished (assuming a tail recursive rev, of course!)

The empty list cannot contain the element; if there is a non-empty list, either the head is equal to the element we are looking for, or if not, the result of our function is just the same as the result of recursing on the tail.

Note that we are using the property that the || operator only evaluates its right hand side if the left hand side is false to limit the recursion – it really does stop as soon as it finds the element.

If a list is empty, it is already a set. If not, either the head exists somewhere in the tail or it does not; if it does exist in the tail, we can discard it, since it will be included later. If not, we must include it.

The first part of the evaluation of rev takes time proportional to the length of the list, processing each element once. However, when the lists are appended together, the order of the operations is such that the first argument becomes longer each time. The @ operator, as we know, also takes time proportional to the length of its first argument. And so, this accumulating of the lists takes time proportional to the square of the length of the list.

By using an additional accumulating argument, we can write a version which operates in time proportional to the length of the list.

5. Sorting Things

Simply add an extra let to define a name representing the number we will take or drop:

The argument to take or drop is length l / 2 which is clearly less than or equal to length l for all possible values of l. Thus, take and drop always succeed. In our case, take and drop are only called with length l more than 1, due to the pattern matching.

We may simply replace the <= operator with the >= operator in the insert function.

We require a function of type α list → bool. List of length zero and one are, by definition, sorted. If the list is longer, check that its first two elements are in sorted order. If this is true, also check that the rest of the list is sorted, starting with the second element.

Lists are compared starting with their first elements. If the elements differ, they are compared, and that is the result of the comparison. If both have the same first element, the second elements are considered, and so on. If the end of one list is reached before the other, the shorter list is considered smaller. For example:

These are the same principles you use to look up a word in a dictionary: compare the first letters – if same, compare the second etc. So, when applied to the example in the question, it has the effect of sorting the words into alphabetical order.

We have renamed the second argument of the insert function to avoid confusion.

Chapter 6. Functions upon Functions upon Functions

Our function will have type char list → char list. We just match on the argument list: if it is empty, we are done. If it starts with an exclamation mark, we output a period, and carry on. If not, we output the character unchanged, and carry on:

To use map instead, we write a simple function calm_char to process a single character. We can then use map to build our main function:

This avoids the explicit recursion of the original, and so it is easier to see what is going on.

We require a function apply f n x which applies function f a total of n times to the initial value x. The base case is when n is zero.

The function f must take and return the same type α, since its result in one iteration is fed back in as its argument in the next. Therefore, the argument x and the final result must also have type α. For example, for α = int, we might have a power function:

We can add an extra argument to the insert function, and use that instead of the comparison operator:

We cannot use map here, because the result list will not necessarily be the same length as the argument list. The function will have type (α → bool) → α list → α list.

For example, filter (fun x -> x mod 2 = 0) [1; 2; 4; 5] evaluates to [2; 4].

For example, we can see if all elements of a list are positive: for_all (fun x -> x > 0) [1; 2; -1] evaluates to false. Notice that we are relying on the fact that && only evaluates its right hand side when the left hand side is true to limit the recursion.

The function will have type (α → β) → α list list → β list list. We use map on each element of the list.

We have used explicit recursion to handle the outer list, and map to handle each inner list.

Chapter 7. When Things go Wrong

The function smallest_inner takes a currently smallest found integer, a boolean value found indicating if we have found any suitable value or not, and the list of integers. It is started with max_int as the current value, so that any number is smaller than it, and false for found because nothing has been found yet.

Thus, the function raises an exception in the case of an empty list, or one which is non-empty but contains no positive integer, and otherwise returns the smallest positive integer in the list.

We just surround the call to smallest with an exception handler for Not_found.

We write a function sqrt_inner which, given a test number x and a target number n squares x and tests if it is more than n. If it is, the answer is x - 1. The test number will be initialized at 1. The function sqrt raises our exception if the argument is less than zero, and otherwise begins the testing process.

Chapter 8. Looking Things Up

Since the keys must be unique, the number of different keys is simply the length of the list representing the dictionary – so we can just use the usual length function.

The type is the same as for the add function. However, if we reach the end of the list, we raise an exception, since we did not manage to find the entry to replace.

The function takes a list of keys and a list of values and returns a dictionary. So it will have type α list → β list → (α × β) list.

This will have the type (α × β) list → α list × β list. For the first time, we need to return a pair, building up both result lists element by element. This is rather awkward, since we will need the tails of both of the eventual results, so we can attach the new heads. We can do this by pattern matching.

Here’s a sample evaluation (we cannot really show it in the conventional way, so you must work through it whilst looking at the function definition):

Since the inner pattern match has only one form, and is complete, we can use let instead:

We can use our member function which determines whether an element is a member of a list, building up a list of the keys we have already seen, and adding to the result list of key-value pairs only those with new keys.

We pattern match on the first list – if it is empty, the result is simply b. Otherwise, we add the first element of the first list to the union of the rest of its elements and the second list.

We can verify that the elements of dictionary a have precedence over the elements of dictionary b by noting that add replaces a value if the key already exists.

Chapter 9. More with Functions

The function g a b c has type α → β → γ → δ which can also be written α → (β → (γ → δ)). Thus, it takes an argument of type α and returns a function of type β → (γ → δ) which, when you give it an argument of type β returns a function of type γ → δ which, when you give it an argument of type γ returns something of type δ. And so, we can apply just one or two arguments to the function g (which is called partial application), or apply all three at once. When we write let g a b c = … this is just shorthand for let g = fun a -> fun b -> fun c -> …

The type of member is α → α list → bool, so if we partially apply the first argument, the type of member x must be α list → bool. We can use the partially-applied member function and map to produce a list of boolean values, one for each list in the argument, indicating whether or not that list contains the element. Then, we can use member again to make sure there are no false booleans in the list.

Which do you think is clearer? Why do we check for the absence of false rather than the presence of true?

The function ( / ) 2 resulting from the partial application of the / operator is the function which divides two by a given number, not the function which divides a given number by two. We can define a reverse divide function…

The function map has type (α → β) → α list → β list. The function mapl we wrote has type (α → β) → α list list → β list list. So the function mapll will have type (α → β) → α list list list → β list list list. It may be defined thus:

It is not possible to write a function which would map a function f over a list, or list of lists, or list of lists of lists depending upon its argument, because every function in OCaml must have a single type. If a function could map f over an α list list it must inspect its argument enough to know it is a list of lists, thus it could not be used on a β list unless β = α list.

We can write a function to truncate a single list using our take function, being careful to deal with the case where there is not enough to take, and then use this and map to build truncate itself.

Here we have used partial application of truncate to build a suitable function for map. Note that we could use exception handling instead of calling length, saving time:

First, define a function which takes the given number and a list, returning the first element (or the number if none). We can then build the main function, using partial application to make a suitable function to give to map:

Chapter 10. New Kinds of Data

We need two constructors – one for squares, which needs just a single integer (the length of a side), and one for rectangles which needs two integers (the width and height, in that order):

The name of our new type is rect. A rect is either a Square or a Rectangle. For example,

This will be a function of type rect → rect. Squares remain unaltered, but if we have a rectangle with a bigger width than height, we rotate it by ninety degrees.

We will use map to perform our rotation on any rects in the argument list which need it. We will then use the sorting function from the previous chapter which takes a custom comparison function so as to just compare the widths.

We follow the same pattern as for the list type, being careful to deal with exceptional circumstances:

Chapter 11. Growing Trees

Our function will have type α → α tree → bool. It takes a element to look for, a tree holding that kind of element, and returns true if the element is found, or false otherwise.

Note that we have placed the test x = y first of the three to ensure earliest termination upon finding an appropriate element.

Our function will have type α tree → α tree. A leaf flips to a leaf. A branch has its left and right swapped, and we must recursively flip its left and right sub-trees too.

We can check each part of both trees together. Leaves are considered equal, branches are equal if their left and right sub-trees are equal.

There will be no key clashes, because the argument should already be a dictionary. If it is not, earlier keys are preferred since insert replaces existing keys.

We can make list dictionaries from both tree dictionaries, append them, and build a new tree from the resultant list.

The combined list may not be a dictionary (because it may have repeated keys), but tree_of_list will prefer keys encountered earlier. So, we put entries from t’ after those from t.

We will use a list for the sub-trees of each branch, with the empty list signifying there are no more i.e. that this is the bottom of the tree. Thus, we only need a single constructor.

type ’a mtree = Branch of ’a * ’a mtree list

In fact, when there is only one pattern to match, we can put it directly in place of the function’s argument, simplifying these definitions:

Chapter 12. In and Out

OCaml

# [1; 2; 3];;
- : int list = [1; 2; 3]
# print_integers [1; 2; 3];;
[1; 2; 3; ]- : unit = ()

There is an extra space after the last element, and a semicolon too. We can fix this, at the cost of a longer program:

OCaml

# [1; 2; 3];;
- : int list = [1; 2; 3]
# print_integers [1; 2; 3];;
[1; 2; 3]- : unit = ()

We must deal with the exception raised when read_int attempts to read something which is not an integer, as before. When that exception is caught, we try again, by recursively calling ourselves. The function ends when three integers are input correctly, returning them as a tuple.

You may wonder why we used nested let … in … structures rather than just writing (read_int (), read_int (), read_int ()) – the evaluation order of a tuple is not specified and OCaml is free to do what it wants.

We ask the user how many dictionary entries will be entered, eliminating the need for a special “I have finished” code. First, a function to read a given number of integer–string pairs, dealing with the usual problem of malformed integers:

And now, asking the user how many entries there will be, and calling our first function:

Notice that we defined, raised, and handled our own exception BadNumber to deal with the user asking to read a negative number of dictionary entries – this would cause read_dict_number to fail to return.

If we write a function to build the list of integers from 1 to n (or the empty list if n is zero):

We can then write a function to output a table of a given size to an output channel.

Look at this carefully. We are using nested calls to iter to build the two-dimensional table from one-dimensional lists. Can you separate this into more than one function? Which approach do you think is more readable?

We can test write_table_channel most easily by using the built-in output channel stdout which just writes to the screen:

OCaml

# write_table_channel stdout 5;;
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
- : unit = ()

Now we just need to wrap it in a function to open an output file, write the table, and close the output, dealing with any errors which may arise.

In addition to raising Invalid_argument in the case of a negative number, we handle all possible exceptions to do with opening, writing to, and closing the file, re-raising them as our own, predefined one. Is this good style?

We write a simple function to count the lines in a channel by taking a line, ignoring it, and adding one to the result of taking another line; our recursion ends when an End_of_file exception is raised – it is caught and 0 ends the summation.

The main function countlines just opens the file, calls the first function, and closes the file. Any errors are caught and re-raised using the built-in Failure exception.

As usual, let us write a function to deal with channels, and then deal with opening and closing files afterward. Our function takes an input channel and an output channel, adds the line read from the input to the output, follows it with a newline character, and continues. It only ends when the End_of_file exception is raised inside input_line and caught.

Now we wrap it up, remembering to open and close both files and deal with the many different errors which might occur.

Chapter 13. Putting Things in Boxes

Two references, x and y, of type int ref have been created. Their initial values are 1 and 2. Their final values are 2 and 4. The type of the expression is int because this is the type of !x + !y, and the result is 6.

The expression [ref 5; ref 5] is of type int ref list. It contains two references each containing the integer 5. Changing the contents of one reference will not change the contents of the other. The expression let x = ref 5 in [x; x] is also of type int ref list and also contains two references to the integer 5. However, altering one will alter the other:

OCaml

# let r = let x = ref 5 in [x; x];;
val r : int ref list = [{contents = 5}; {contents = 5}]
# match r with h::_ -> h := 6;;
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]
- : unit = ()
# r;;
- : int ref list = [{contents = 6}; {contents = 6}]

We can write a function forloop which takes a function of type int → α (where alpha would normally be unit), together with the start and end numbers:

OCaml

# forloop print_int 2 10;;
2345678910- : unit = ()
# forloop print_int 2 2;;
2- : unit = ()

Note that this works for the empty array, because a for construct where the second number is less than the first never executes its expression.

Since we wish to reverse the array in place, our function will have type α array → unit. Our method is to proceed from the first element to the half-way point, swapping elements from either end of the array. If the array has odd length, the middle element will not be altered.

We will represent the int array array as an array of columns so that a.(x).(y) is the element in column x and row y.

The difference between the codes for ’a’ and ’A’, or ’z’ and ’Z’ is 32, so we add or subtract as appropriate. Codes not in those ranges are unaltered.

Periods, exclamation marks and question marks may appear in multiples, leading to a wrong answer. The number of characters does not include newlines. It is not clear how quotations would be handled. Counting the words by counting spaces is inaccurate – a line with ten words will count only nine.

Chapter 14. The Other Numbers

We calculate the ceiling and floor, and return the closer one, being careful to make sure that a point equally far from the ceiling and floor is rounded up.

The behaviour with regard to values such as infinity and nan is fine, since it always returns the result of either floor or ceil.

The whole part is calculated using the built-in floor function. We return a tuple, the first number being the whole part, the second being the original number minus the whole part. In the case of a negative number, we must be careful – floor always rounds downward, not toward zero!

We need to determine at which column the asterisk will be printed. It is important to make sure that the range 0…1 is split into fifty equal sized parts, which requires some careful thought. Then, we just print enough spaces to pad the line, add the asterisk, and a newline character.

No allowance has been made here for bad arguments (for example, b smaller than a). Can you extend our program to move the zero-point to the middle of the screen, so that the sine function can be graphed even when its result is less than zero?

Chapter 15. The OCaml Standard Library

To make a tail-recursive one, we can use an accumulator, reversing each list as we append it, and reversing the result. List.rev is tail-recursive already.

We can use List.mem, partially applied, to map over the list of lists. We then make sure that false is not in the resultant list, again with List.mem.

The String.iter function calls a user-supplied function of type char → unit on each character of the string. We can use this to increment a counter when an exclamation mark is found.

We can use the String.map function, which takes a user-supplied function of type char → char and returns a new string, where each character is the result of the mapping function on the character in the same place in the old string.

Notice that we have taken advantage of partial application to erase the last argument as usual.

We can use the functions create, add_string, and contents from the Buffer module together with the usual list iterator List.iter:

We repeatedly check if the string we are looking for is right at the beginning of the string to be searched. If not, we chop one character off the string to be searched, and try again. Every time we find a match, we increment a counter.

You might consider that writing this function with lists of characters rather than strings would be easier. Unfortunately, it would be slow, and these kinds of searching tasks are often required to be very fast.

Chapter 16. Building Bigger Programs

First, we extend the Textstat module to allow frequencies to be counted and expose it through the interface. Here is the interface q1.mli:

We can write two little functions – one to read all the lines from a file, and one to write them. The main function, then, reads the command line to find the input and output file names, reads the lines from the input, reverses the list of lines, and writes them out. If a problem occurs, the exception is printed out. If the command line is badly formed, we print a usage message and exit.

Note that there is a problem if the file has no final newline – it will end up with one. How might you solve that?

We can simply do something (or nothing) a huge number of times using a for loop.

On many systems, typing time followed by a space and the usual command will print out on the screen how long the program took to run. For example, on the author’s computer:

$ ocamlc bigloop.ml -o bigloop
$ time ./bigloop

real  0m1.896s
user  0m1.885s
sys   0m0.005s

$ ocamlopt bigloop.ml -o bigloop
$ time ./bigloop

real  0m0.022s
user  0m0.014s
sys   0m0.003s

You can see that, when compiled with ocamlc, it takes 1.9s to run, but when compiled with ocamlopt just 0.022s.

We can get all the lines in the file using our getlines function from question two. The main function simply calls string_in_line on each line, printing it if true is returned.

The interesting function is string_in_line. To see if term is in line we start at position 0. The condition for the term having been found is a combination of boolean expressions. The first ensures that we are not so far through the string that the expression could not possibly fit at the current position. The second checks to see if the term is found at the current position by using the function String.sub from the OCaml Standard Library. If not, we carry on.

Hints for Questions

1. Starting Off

Try to work these out on paper, and then check by typing them in. Remember that the type of an expression is the type of the value it will evaluate to. Can you show the steps of evaluation for each expression?

Type each expression in. What number does each evaluate to? Can you work out which operator (mod or +) is being calculated first?

2. Names and Functions

The function takes one integer, and returns that integer multiplied by ten. So what must its type be?

What does the function take as arguments? What is the type of its result? So what is the whole type? You can use the <> and && operators here.

This will be a recursive function, so remember to use let rec. What is the sum of all the integers from 1…1? Perhaps this is a good base case.

This will be a recursive function. What happens when you raise a number to the power 0? What about the power 1? What about a higher power?

Try adding parentheses to the expression in a way which does not change its meaning. Does this make it easier to understand?

When does it not terminate? Can you add a check to see when it might happen, and return 0 instead? What is the factorial of 0 anyway?

3. Case by Case

We are pattern matching on a boolean value, so there are just two cases: true and false.

Convert the if … then … else structure of the sum function from the previous chapter into a pattern matching structure.

You will need three cases as before – when the power is 0, 1 or greater than 1 – but now in the form of a pattern match.

There will be two cases in each function – the special range pattern x..y, and _ for any other character.

4. Listing Things

Consider three cases: (1) the argument list is empty, (2) the argument list has one element, (3) the argument list has more than one element a::b::t. In the last case, which element do we need to miss out?

The function will have type bool list→ int. Consider the empty list, the list with true as its head, and the list with false as its head. Count one for each true and zero for each false.

The function to make a palindrome is trivial; to detect if a list is a palindrome, consider the definition of a palindrome – a list which equals its own reverse.

Consider the cases (1) the empty list, (2) the list with one element, and (3) the list with more than one element. For the tail recursive version, use an accumulating argument.

Can any element exist in the empty list? If the list is not empty, it must have a head and a tail. What is the answer if the element we are looking for is equal to the head? What do we do if it is not?

The empty list is already a set. If we have a head and a tail, what does it tell us to find out if the head exists within the tail?

Consider in which order the @ operators are evaluated in the reverse function. How long does each append take? How many are there?

5. Sorting Things

Consider adding another let before let left and let right.

Consider the situations in which take and drop can fail, and what arguments msort gives them at each recursion.

What will the type of the function be? Lists of length zero and one are already sorted – so these will be the base cases. What do we do when there is more than one element?

2. Names and Functions

The function calm is simple recursion on lists. There are three cases – the empty list, a list beginning with ’!’ and a list beginning with any other character. In the second part of the question, write a function calm_char which processes a single character. You can then use map to define a new version of calm.

Look back at the section on anonymous functions. How can clip be expressed as an anonymous function? So, how can we use it with map?

We want a function of the form let rec apply f n x = … which applies f to x a total of n times. What is the base case? What do we do in that case? What otherwise?

You will need to add the extra function as an argument to both insert and sort and use it in place of the <= operator in insert.

There are three possibilities: the argument list is empty, true is returned when its head is given to the function f, or false is returned when its head is given to the function f.

If the input list is empty, the result is trivially true – there cannot possibly be any elements for which the function does not hold. If not, it must hold for the first one, and for all the others by recursion.

Chapter 7. When Things go Wrong

Make sure to consider the case of the empty list, where there is no smallest positive element, and also the non-empty list containing entirely zero or negative numbers.

First, write a function to find the number less than or equal to the square root of its argument. Now, define a suitable exception, and wrap up your function in another which, on a bad argument, raises the exception or otherwise calls your first function.

Use the try … with construct to call your function and handle the exception you defined.

Chapter 7. Looking Things Up

The type will be the same as for the add function, but we only replace something if we find it there – when do we know we will not find it?

The function takes a list of keys and a list of values, and returns a dictionary. So it will have type α list → β list → (α × β) list. Try matching on both lists at once – what are the cases?

This function takes a list of pairs and produces a pair of lists. So its type must be (α × β) list → α list × β list.

For the base case (the empty dictionary), we can see that the result should be ([], []). But what to do in the case we have (k, v) :: more? We must get names for the two parts of the result of our function on more, and then cons k and v on to them – can you think of how to do that?

You can keep a list of the keys which have already been seen, and use the member function to make sure you do not add to the result list a key-value pair whose key has already been included.

The function will take two dictionaries, and return another – so you should be able to write down its type easily.

Try pattern matching on the first list – when it is empty, the answer is trivial – what about when it has a head and a tail?

Chapter 9. More with Functions

Try building a list of booleans, each representing the result of member on a list.

The / operator differs from the * operator in an important sense. What is it?

The type of map is (α → β) → α list → β list. The type of mapl is (α → β) → α list list → β list list. So, what must the type of mapll be? Now, look at our definition of mapl – how can we extend it to lists of lists of lists?

Use our revised take function to process a single list. You may then use map with this (partially applied) function to build the truncate function.

Build a function firstelt which, given the number and a list, returns the first element or that number. You can then use this function (partially applied) together with map to build the main firstelts function.

Chapter 10. New Kinds of Data

The type will have two constructors: one for squares, requiring only a single integer, and one for rectangles, requiring two: one for the width and one for the height.

The function will have type rect → int. Work by pattern matching on the two constructors of your type.

Work by pattern matching on your type. What happens to a square. What to a rectangle?

First, we need to rotate the rectangles as needed – you have already written something for this. Then, we need to sort them according to width. Can you use our sort function which takes a custom comparison function for this?

Chapter 11. Growing Trees

The type will be α → α tree → bool. That is, it takes an element to search for, and a tree containing elements of the same type, and returns true if the element is found, and false if not. What happens if the tree is a leaf? What if it is a branch?

The function will have type α tree → α tree. What happens to a leaf? What must happen to a branch and its sub-trees?

If the two trees are both Lf, they have the same shape. What if they are both branches? What if one is a branch and the other a leaf or vice versa?

We have already written a function for inserting an element into an existing tree.

Try using list dictionaries as an intermediate representation. We already know how to build a tree from a list.

Consider using a list of sub-trees for a branch. How can we represent a branch which has no sub-trees?

Chapter 12. In and Out

You can use the print_string and print_int functions. Be careful about what happens when you print the last number.

You can use the read_int function to read an integer from the user. Be sure to give the user proper instructions, and to deal with the case where read_int raises an exception (which it will if the user does not type an integer).

One way would be to ask the user how many dictionary entries they intend to type in first. Then we do not need a special code to signal the end of input.

Try writing a function to build a list of integers from 1 to n. Can you use that to build the table and print it? The iter and/or map functions may come in useful. Deal with a channel in your innermost function – the opening and closing of the file can be dealt with elsewhere.

The input_line function can be used – how many times can you call it until End_of_file is raised?

We can read lines from the file using input_line and write using output_string – make sure the newlines do not get lost! How do we know when we are done? Write a function to copy a line from one channel to another – we can deal with opening and closing the files separately.

Chapter 13. Putting Things in Boxes

Consider the initial values of the references, and then work through how each one is altered by each part of the expression. What is finally returned as the result of the expression?

Try creating a value for each list in OCaml. Now try getting the head of the list, which is a reference, and updating its contents to another integer. What has happened in each case?

Try writing a function forloop which takes a function to be applied to each number, and the start and end numbers. It should call the given function on each number. What should happen when the start number is larger than the end number?

Type them in if you are stuck. Can you work out why each expression has the type OCaml prints?

We want a function of type int array → int. Try a for loop with a reference to accumulate the sum.

Consider swapping elements from opposite ends of the array – the problem is symmetric.

To build an array of arrays, you will need a use Array.make to build an array of empty arrays. You can then set each of the elements of the main array to a suitably sized array, again created with Array.make. Once the structure is in place, putting the numbers in should be simple.

What is the difference between the codes for ’a’ and ’A’? What about ’z’ and ’Z’?

Chapter 14. The Other Numbers

This is simple arithmetic. The function will take two points and return another, so it will have type float × float → float × float → float × float.

Consider the built-in function floor. What should happen in the case of a negative number?

Calculate the column number for the asterisk carefully. How can it be printed in the correct column?

You will need to call the star function with an appropriate argument at points between the beginning and end of the range, as determined by the step.

Chapter 15. The OCaml Standard Library

Create a buffer, add all the strings to it in order, and then return its contents.

String.sub is useful here. You can compare strings with one another for equality, as with any other type.

Chapter 16. Building Bigger Programs

You will need to alter the Textstat module to calculate the histogram and allow it to be accessed through the module’s interface. Then, alter the main program to retrieve and print the extra information.

You will need functions to read and write the lines. You can read the required input and output filenames from Sys.argv. What should we do in case of an error, e.g. a bad filename?

Consider doing something a very large number of times. You should avoid printing information to the screen, because the printing speed might dominate, and the differing computation speeds may be hard to notice.

Start with a function to search for a given string inside another. You might find some functions from the String module in the OCaml Standard Library to be useful, or you can write it from first principles. Once this is done, the rest is simple.

Coping with Errors

It is very hard to write even small programs correctly the first time. An unfortunate but inevitable part of programming is the location and fixing of mistakes. OCaml has a range of messages to help you with this process.

Here are descriptions of the common messages OCaml prints when a program cannot be accepted or when running it causes a problem (a so-called “run-time error”). We also describe warnings OCaml prints to alert the programmer to a program which, though it can be accepted for evaluation, might contain mistakes.

Errors

These are messages printed when an expression could not be accepted for evaluation, due to being malformed in some way. No evaluation is attempted. You must fix the expression and try again.

Syntax error

This error occurs when OCaml finds that the program text contains things which are not valid words (such as if, let etc.) or other basic parts of the language, or when they exist in invalid combinations – this is known as syntax. Check carefully and try again.

OCaml has underlined where it thinks the error is. Since this error occurs for a wide range of different mistakes and problems, the underlining may not pinpoint the exact position of your mistake.

Unbound value …

This error occurs when you have mentioned a name which has not been defined (technically “bound to a value”). This might happen if you have mistyped the name.

This expression has type … but an expression was expected of type …

You will see this error very frequently. It occurs when the expression’s syntax is correct (i.e. it is made up of valid words and constructs), and OCaml has moved on to type-checking the expression prior to evaluation. If there is a problem with type-checking, OCaml shows you where a mismatch between the expected and actual type occurred.

OCaml

# 1 + true;;
Error: This expression has type bool but an expression was expected of type
int

In this example, OCaml is looking for an integer on the right hand side of the + operator, and finds something of type bool instead.

It is not always as easy to spot the real source of the problem, especially if the function is recursive. Nevertheless, a careful look at the program will often shine light on the problem – look at each function and its arguments, and try to find your mistake.

This function is applied to too many arguments

OCaml

# let f x = x + 1;;
val f : int -> int = <fun>
# f x y;;
Error: This function is applied to too many arguments;
maybe you forgot a `;'

The phrase “maybe you forgot a ‘;’ ” applies to imperative programs where accidently missing out a ‘;’ between successive function applications might commonly lead to this error.

Unbound constructor …

OCaml

# type t = Roof | Wall | Floor;;
type t = Roof | Wall | Floor
# Window;;
Error: Unbound constructor Window

The constructor … expects … argument(s), but is applied here to … argument(s)

This error occurs when the wrong kind of data is given to a constructor for a type. It is just another type error, but we get a specialised message.

OCaml

# type p = A of int | B of bool;;
type p = A of int | B of bool
# A;;
Error: The constructor A expects 1 argument(s),
but is applied here to 0 argument(s)

Run-time Errors

In any programming language powerful enough to be of use, some errors cannot be detected before attempting evaluation of an expression (until “run-time”). The exception mechanism is for handling and recovering from these kinds of problems.

Stack overflow during evaluation (looping recursion?)

This occurs if the function builds up a working expression which is too big. This might occur if the function is never going to stop because of a programming error, or if the argument is just too big.

OCaml

# let rec f x = 1 + f (x + 1);;
val f : int -> int = <fun>
# f 0;;
Stack overflow during evaluation (looping recursion?).

Find the cause of the unbounded recursion, and try again. If it is really not a mistake, rewrite the function to use an accumulating argument (and so, to be tail recursive).

Exception: Match_failure …

This occurs when a pattern match cannot find anything to match against. You would have been warned about this possibility when the program was originally entered. For example, if the following function f were defined as

In this example, the match failure occurred in the top level (i.e. the interactive OCaml we are using), at line one, character ten.

Exception: …

OCaml

# exception Exp of string;;
exception Exp of string
# raise (Exp "Failed");;
Exception: Exp "Failed".

This can occur for built-in exceptions like Division_by_Zero or Not_found or ones the user has defined like Exp above.

Warnings

Warnings do not stop an expression being accepted or evaluated. They are printed after an expression is accepted but before the expression is evaluated. Warnings are for occasions where OCaml is concerned you may have made a mistake, even though the expression is not actually malformed. You should check each new warning in a program carefully.

This pattern-matching is not exhaustive

This warning is printed when OCaml has determined that you have missed out one or more cases in a pattern match. This could result in a Match_failure exception being raised at run-time.

OCaml

# let f x = match x with 0 -> 1;;
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
1
val f : int -> int = <fun>

Helpfully, it is able to generate an example of something the pattern match does not cover, so this should give you a hint about what has been missed out. You may ignore the warning if you are sure that, for other reasons, this case can never occur.

This match case is unused

This occurs when two parts of the pattern match cover the same case. In this situation, the second one could never be reached, so it is almost certain the programmer has made a mistake.

OCaml

# let f x = match x with _ -> 1 | 0 -> 0;;
Warning 11: this match case is unused.
val f : int -> int = <fun>

In this case, the first case matches everything, so the second cannot ever match.

This expression should have type unit

Sometimes when writing imperative programs, we ignore the result of some side-effect-producing function. However, this can indicate a mistake.

OCaml

# f 1; 2;;
Warning 10: this expression should have type unit.
- : int = 2

It is better to use the built-in ignore function in these cases, to avoid this warning: