OCaml from the Very Beginning

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.

Published in the United Kingdom by Coherent Press, Cambridge

Copyright Coherent Press 2013. Last updated 2022.

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.

ISBN 978-0-9576711-0-2 Paperback

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

#

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

OCaml

# 1 + 2;;
- : int = 3

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:

OCaml

# exit 0;;

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:

OCaml

# 1 + 3^CInterrupted
# 1 + 2;;
- : int = 3

We are ready to begin.

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:

image

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:

image

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:

OCaml

# 1 + 2 * 3;;
- : int = 7

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:

image

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:

5 * -2 : int

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

true
false

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

Here are all the comparison operators:

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

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:

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:

OCaml

# ’c’;;
- : char = ’c’

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:

OCaml

# if 100 > 99 then 0 else 1;;
- : int = 0

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:

image

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

  1. What are the types of the following expressions and what do they evaluate to, and why?

    17

    1 + 2 * 3 + 4

    800 / 80 / 8

    400 > 200

    1 <> 1

    true || false

    true && false

    if true then false else true

    ’%’

    ’a’ + ’b’

  2. Consider the evaluations of the expressions 1 + 2 mod 3, (1 + 2) mod 3, and 1 + (2 mod 3). What can you conclude about the + and mod operators?

  3. A programmer writes 1+2 * 3+4. What does this evaluate to? What advice would you give him?

  4. The range of numbers available is limited. There are two special numbers: min_int and max_int. What are their values on your computer? What happens when you evaluate the expressions max_int + 1 and min_int - 1?

  5. What happens when you try to evaluate the expression 1 / 0? Why?

  6. Can you discover what the mod operator does when one or both of the operands are negative? What about if the first operand is zero? What if the second is zero?

  7. Why not just use, for example, the integer 0 to represent false and the integer 1 for true? Why have a separate bool type at all?

  8. What is the effect of the comparison operators like < and > on alphabetic values of type char? For example, what does ’p’ < ’q’ evaluate to? What is the effect of the comparison operators on the booleans, true and false?

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:

OCaml

# 200 * 200 * 200;;
- : int = 8000000

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

image

If we try an argument of the wrong type, the program will be rejected:

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

Here is a function which determines if an integer is negative:

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?

image

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)?

image

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

Here is the evaluation:

image

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

  1. Write a function which multiplies a given number by ten. What is its type?

  2. Write a function which returns true if both of its arguments are non-zero, and false otherwise. What is the type of your function?

  3. Write a recursive function which, given a number n, calculates the sum 1 + 2 + 3 + … + n. What is its type?

  4. Write a function power x n which raises x to the power n. Give its type.

  5. Write a function isconsonant which, given a lower-case character in the range ’a’’z’, determines if it is a consonant.

  6. What is the result of the expression  let x = 1 in let x = 2 in x + x ?

  7. Can you suggest a way of preventing the non-termination of the factorial function in the case of a zero or negative argument?

Note on Notation

From now on, instead of showing the actual OCaml session…

OCaml

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

…we will usually just show the program in a box, together with its type:

image

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:

image

We can rewrite this using pattern matching:

image

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?

image

Here is how to write it using pattern matching:

image

If we miss out one or more cases, OCaml will warn us:

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:

image

Finally, let us rewrite Euclid’s Algorithm from the previous chapter:

image

Now in pattern matching style:

image

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:

image

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

Questions

  1. Rewrite the not function from the previous chapter in pattern matching style.

  2. Use pattern matching to write a recursive function which, given a positive integer n, returns the sum of all the integers from 1 to n.

  3. Use pattern matching to write a function which, given two numbers x and n, computes xn.

  4. For each of the previous three questions, comment on whether you think it is easier to read the function with or without pattern matching. How might you expect this to change if the functions were much larger?

  5. What does match 1 + 1 with 2 -> match 2 + 2 with 3 -> 4 | 4 -> 5 evaluate to?

  6. There is a special pattern x..y to denote continuous ranges of characters, for example ’a’..’z’ will match all lowercase letters. Write functions islower and isupper, each of type char bool, to decide on the case of a given letter.

Making Lists

A list is a collection of elements. Here is a list of three integers:

[1; 2; 3]

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”):

[]

It has neither a head nor a tail. Here is a list with just a single element:

[5]

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:

[false; true; false]  :  bool list

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

image

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:

image

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:

image

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:

image

Here is how the evaluation proceeds:

image

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:

image

A very similar function can be used to add a list of integers:

image

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:

image

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:

image

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:

image

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:

image

Consider the evaluation of odd_elements [2; 4; 2; 4; 2]:

image

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:

image

We have seen how to use the @ (append) operator to concatenate two lists:

image

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.

image

Consider the evaluation of append [1; 2; 3] [4; 5; 6]:

image

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:

image

Here’s how the evaluation proceeds:

image

This is a simple definition, but not very efficient – can you see why?

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:

image

For example, here’s the evaluation for take 2 [2; 4; 6; 8; 10]:

image

And for drop 2 [2; 4; 6; 8; 10]:

image

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:

[[1]; [2; 3]; [4; 5; 6]]  :  (int list) list

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

[] : α list list

from the list of lists containing one element which is the empty list

[[]] : α list list

Questions

  1. Write a function evens which does the opposite to odds, returning the even numbered elements in a list. For example, evens [2; 4; 2; 4; 2] should return [4; 4]. What is the type of your function?

  2. Write a function count_true which counts the number of true elements in a list. For example, count_true [true; false; true] should return 2. What is the type of your function? Can you write a tail recursive version?

  3. Write a function which, given a list, builds a palindrome from it. A palindrome is a list which equals its own reverse. You can assume the existence of rev and @. Write another function which determines if a list is a palindrome.

  4. Write a function drop_last which returns all but the last element of a list. If the list is empty, it should return the empty list. So, for example, drop_last [1; 2; 4; 8] should return [1; 2; 4]. What about a tail recursive version?

  5. Write a function member of type α α list bool which returns true if an element exists in a list, or false if not. For example, member 2 [1; 2; 3] should evaluate to true, but member 3 [1; 2] should evaluate to false.

  6. Use your member function to write a function make_set which, given a list, returns a list which contains all the elements of the original list, but has no duplicate elements. For example, make_set [1; 2; 3; 3; 1] might return [2; 3; 1]. What is the type of your function?

  7. Can you explain why the rev function we defined is inefficient? How does the time it takes to run relate to the size of its argument? Can you write a more efficient version using an accumulating argument? What is its efficiency in terms of time taken and space used?

Two Different Ways of Thinking

Look again at our list appending function:

image

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

Look at the first list. If it is empty, return the second list. Otherwise, pull apart the first list, looking at its head and tail. Make a recursive call to append the tail to the second list, and then cons the head onto the result. Return this.

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

The empty list appended to another list is that list. Otherwise, the first list is non-empty, so it has a head and a tail. Call them h and t. Clearly append (h :: t) b is equal to h :: append t b. Since this reduces the problem size, progress is made.

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.

image

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:

image

Consider the evaluation of insert 3 [1; 1; 2; 3; 5; 9]:

image

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

image

Here’s the full program, known as insertion sort:

image

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:

image

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 n2. 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 n2. 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:

image

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:

image

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.

image

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:

image

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 log2n, and the same for the bottom half. So, the total work done is 2 × log2n × n, which is proportional to nlog2n.

Questions

  1. In msort, we calculate the value of the expression length l / 2 twice. Modify msort to remove this inefficiency.

  2. We know that take and drop can fail if called with incorrect arguments. Show that this is never the case in msort.

  3. Write a version of insertion sort which sorts the argument list into reverse order.

  4. Write a function to detect if a list is already in sorted order.

  5. We mentioned that the comparison functions like  <  work for many OCaml types. Can you determine, by experimentation, how they work for lists? For example, what is the result of [1; 2] < [2; 3]? What happens when we sort the following list of type char list list? Why?

    [[’o’; ’n’; ’e’]; [’t’; ’w’; ’o’]; [’t’; ’h’; ’r’; ’e’; ’e’]]

  6. Combine the sort and insert functions into a single sort function.

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:

image

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:

image

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:

image

For example,

image

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.

image

For example,

image

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:

image

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:

image

We can use map like this:

image

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

image

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:

image

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:

image

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:

fun x -> x / 2

and, thus, write:

image

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:

image

Now, if we make our own comparison operator:

image

we can use it with our new version of the msort function:

image

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

So, for example:

image

and

image

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

Questions

  1. Write a simple recursive function calm to replace exclamation marks in a char list with periods. For example calm [’H’; ’e’; ’l’; ’p’; ’!’; ’ ’; ’F’; ’i’; ’r’; ’e’; ’!’] should evaluate to [’H’; ’e’; ’l’; ’p’; ’.’; ’ ’; ’F’; ’i’; ’r’; ’e’; ’.’]. Now rewrite your function to use map instead of recursion. What are the types of your functions?

  2. Write a function clip which, given an integer, clips it to the range 1…10 so that integers bigger than 10 round down to 10, and those smaller than 1 round up to 1. Write another function cliplist which uses this first function together with map to apply this clipping to a whole list of integers.

  3. Express your function cliplist again, this time using an anonymous function instead of clip.

  4. Write a function apply which, given another function, a number of times to apply it, and an initial argument for the function, will return the cumulative effect of repeatedly applying the function. For instance, apply f 6 4 should return f (f (f (f (f (f 4)))))). What is the type of your function?

  5. Modify the insertion sort function from the preceding chapter to take a comparison function, in the same way that we modified merge sort in this chapter. What is its type?

  6. Write a function filter which takes a function of type α bool and an α list and returns a list of just those elements of the argument list for which the given function returns true.

  7. Write the function for_all which, given a function of type α bool and an argument list of type α list evaluates to true if and only if the function returns true for every element of the list. Give examples of its use.

  8. Write a function mapl which maps a function of type α β over a list of type α list list to produce a list of type β list list.

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:

OCaml

# 10 / 0;;
Exception: Division_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.

image

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:

image

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.

image

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

image

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:

image

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

  1. Write a function smallest which returns the smallest positive element of a list of integers. If there is no positive element, it should raise the built-in Not_found exception.

  2. Write another function smallest_or_zero which uses the smallest function but if Not_found is raised, returns zero.

  3. Write an exception definition and a function which calculates the largest integer smaller than or equal to the square root of a given integer. If the argument is negative, the exception should be raised.

  4. Write another function which uses the previous one, but handles the exception, and simply returns zero when a suitable integer cannot be found.

  5. Comment on the merits and demerits of exceptions as a method for dealing with exceptional situations, in contrast to returning a special value to indicate an error (such as -1 for a function normally returning a positive number).

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:

image

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:

image

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:

image

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

image

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:

image

Now, we can store a dictionary as a list of pairs:

image

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:

image

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

image

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

image

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:

image

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:

image

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

  1. Write a function to determine the number of different keys in a dictionary.

  2. Define a function replace which is like add, but raises Not_found if the key is not already there.

  3. Write a function to build a dictionary from two equal length lists, one containing keys and another containing values. Raise the exception Invalid_argument if the lists are not of equal length.

  4. Now write the inverse function: given a dictionary, return the pair of two lists – the first containing all the keys, and the second containing all the values.

  5. Define a function to turn any list of pairs into a dictionary. If duplicate keys are found, the value associated with the first occurrence of the key should be kept.

  6. Write the function union a b which forms the union of two dictionaries. The union of two dictionaries is the dictionary containing all the entries in one or other or both. In the case that a key is contained in both dictionaries, the value in the first should be preferred.

More with Functions

Look again at the type of a simple function with more than one argument:

image

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.

In truth, the function add is a function which, when you give it an integer, gives you a function which, when you give it an integer, gives the sum.

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:

map (add 6) [10; 20; 30]

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

map (fun x -> x * 2) [10; 20; 30]

we may write

map (( * ) 2) [10; 20; 30]

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

image

With partial application, we can write

image

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:

image

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:

image

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

  1. Rewrite the summary paragraph at the end of this chapter for the three argument function g a b c.

  2. Recall the function member x l which determines if an element x is contained in a list l. What is its type? What is the type of member x? Use partial application to write a function member_all x ls which determines if an element is a member of all the lists in the list of lists ls.

  3. Why can we not write a function to halve all the elements of a list like this: map (( / ) 2) [10; 20; 30]? Write a suitable division function which can be partially applied in the manner we require.

  4. Write a function mapll which maps a function over lists of lists of lists. You must not use the let rec construct. Is it possible to write a function which works like map, mapl, or mapll depending upon the list given to it?

  5. Write a function truncate which takes an integer and a list of lists, and returns a list of lists, each of which has been truncated to the given length. If a list is shorter than the given length, it is unchanged. Make use of partial application.

  6. Write a function which takes a list of lists of integers and returns the list composed of all the first elements of the lists. If a list is empty, a given number should be used in place of its first element.

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:

OCaml

# type colour = Red | Green | Blue | Yellow;;
type colour = Red | Green | Blue | Yellow

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:

image

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

image

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:

image

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:

image

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:

image

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:

image

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.

image

And now the same functions with our new sequence type:

image

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:

image

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

image

Here’s a suitable type for such expressions:

image

For example, the expression 1 + 2 * 3 is represented in this data type as:

Add (Num 1, Multiply (Num 2, Num 3))

We can now write a function to evaluate expressions:

image

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

  1. Design a new type rect for representing rectangles. Treat squares as a special case.

  2. Now write a function of type rect int to calculate the area of a given rect.

  3. Write a function which rotates a rect such that it is at least as tall as it is wide.

  4. Use this function to write one which, given a rect list, returns another such list which has the smallest total width and whose members are sorted narrowest first.

  5. Write take, drop, and map functions for the sequence type.

  6. Extend the expr type and the evaluate function to allow raising a number to a power.

  7. Use the option type to deal with the problem that Division_by_zero may be raised from the evaluate function.

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.

image

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:

image

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:

image

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:

image

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.

image

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:

image

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:

image

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:

image

which would be written as

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.

image

Alternatively, we may use the option type to avoid exceptions:

image

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.

image

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

image

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

  1. Write a function of type α α tree bool to determine if a given element is in a tree.

  2. Write a function which flips a tree left to right such that, if it were drawn on paper, it would appear to be a mirror image.

  3. Write a function to determine if two trees have the same shape, irrespective of the actual values of the elements.

  4. Write a function tree_of_list which builds a tree representation of a dictionary from a list representation of a dictionary.

  5. Write a function to combine two dictionaries represented as trees into one. In the case of clashing keys, prefer the value from the first dictionary.

  6. Can you define a type for trees which, instead of branching exactly two ways each time, can branch zero or more ways, possibly different at each branch? Write simple functions like size, total, and map using your new type of tree.

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:

OCaml

# print_int 100;;
100- : unit = ()

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:

image

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:

image

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:

OCaml

# print_dict_entry (1, "one");;
1
one
- : unit = ()

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:

image

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

image

Normally β will be unit. Now we can redefine print_dict using iter:

image

For example:

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.

image

We can run this function and type in some suitable values:

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:

image

Now, typing mistakes can be fixed interactively:

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:

image

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.

image

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

Now we have written a file, we can read it back in:

image

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:

image

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:

image

Questions

  1. Write a function to print a list of integers to the screen in the same format OCaml uses – i.e. with square brackets and semicolons.

  2. Write a function to read three integers from the user, and return them as a tuple. What exceptions could be raised in the process? Handle them appropriately.

  3. In our read_dict function, we waited for the user to type 0 to indicate no more data. This is clumsy. Implement a new read_dict function with a nicer system. Be careful to deal with possible exceptions which may be raised.

  4. Write a function which, given a number x, prints the x-times table to a given file name. For example, table "table.txt" 5 should produce a file table.txt containing the following:

    image

    Adding the special tabulation character \t after each number will line up the columns.

  5. Write a function to count the number of lines in a given file.

  6. Write a function copy_file of type string string unit which copies a file line by line. For example, copy_file "a.txt" "b.txt" should produce a file b.txt identical to a.txt. Make sure you deal with the case where the file a.txt cannot be found, or where b.txt cannot be created or filled.

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

# let x = ref 0;;
val x : int ref = {contents = 0}

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

# let p = !x;;
val p : int = 0

We can update the contents of the reference using the :=  operator:

# x := 50;;
- : unit = ()

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.

# let q = !x;;
val q : int = 50
# p;;
- : int = 0

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

image

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

if x = 0 then a := 0 else ()

can be written as

if x = 0 then a := 0

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:

image

OCaml allows us to use begin and end instead, for readability:

image

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

image

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

image

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.

image

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:

Warning 26: unused variable line.

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: