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

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.

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.

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.

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.

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:

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

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`

` OCaml`

`# if 100 > 99 then 0 else 1;;`

`- : int = 0`

The expression between ** if** and

`then`

`100 > 99`

) must have type `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 `then`

`else`

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.

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’`

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?A programmer writes

`1+2 * 3+4`

. What does this evaluate to? What advice would you give him?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`

?What happens when you try to evaluate the expression

`1 / 0`

? Why?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?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?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`

?

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`

` 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^{3} 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:

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`

`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`

Here is the evaluation:

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

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

Write a function which returns

`true`

if both of its arguments are non-zero, and`false`

otherwise. What is the type of your function?Write a recursive function which, given a number

*n*, calculates the sum 1 + 2 + 3 + … +*n*. What is its type?Write a function

`power x n`

which raises`x`

to the power`n`

. Give its type.Write a function

`isconsonant`

which, given a lower-case character in the range`’a’`

…`’z’`

, determines if it is a consonant.What is the result of the expression

`let`

`x = 1`

`in`

`let`

`x = 2`

`in`

`x + x`

?Can you suggest a way of preventing the non-termination of the

`factorial`

function in the case of a zero or negative argument?

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:

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.

In the previous chapter, we used the conditional expression
** if** …

`then`

`else`

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

We can rewrite this using pattern matching:

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?

Here is how to write it using pattern matching:

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:

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

Now in pattern matching style:

The type of a whole ** match**
…

`with`

`->`

arrow, all of which must be alike:We use pattern matching whenever it is easier to read and understand
than ** if**
…

`then`

`else`

Rewrite the

`not`

function from the previous chapter in pattern matching style.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*.Use pattern matching to write a function which, given two numbers

*x*and*n*, computes*x*^{n}.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?

What does

`match`

`1 + 1`

`with`

`2 ->`

`match`

`2 + 2`

`with`

`3 -> 4 | 4 -> 5`

evaluate to?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.

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:

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

in our patterns, this time using it to deconstruct
rather than construct the list:Here is how the evaluation proceeds:

This works by recursion over the list, then addition of all the
resultant `1`

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

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

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:

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

:

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:

We have seen how to use the `@`

(append) operator to
concatenate two lists:

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`

.

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

:

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:

Here’s how the evaluation proceeds:

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:

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

:

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

:

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

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?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?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.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?Write a function

`member`

of typewhich returns*α*→*α*list → bool`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`

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

Look again at our list appending function:

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.

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:

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

:

Here is the whole evaluation of `sort [53; 9; 2; 6; 19]`

.
We have missed out the detail of each `insert`

operation.

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

Notice that the type ** α list → α
list** rather than

`<=`

(used
inside `insert`

) work for types other than 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*^{2}. 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*^{2}. 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 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_{2}*n*, and the same
for the bottom half. So, the total work done is 2 × log_{2}*n* × *n*,
which is proportional to *n*log_{2}*n*.

In

`msort`

, we calculate the value of the expression`length l / 2`

twice. Modify`msort`

to remove this inefficiency.We know that

`take`

and`drop`

can fail if called with incorrect arguments. Show that this is never the case in`msort`

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

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

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’]]`

Combine the

`sort`

and`insert`

functions into a single`sort`

function.

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.

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:

For example,

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.

For example,

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`

:

We can use `map`

like this:

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

`f`

. In
the same way, the result list has type `f`

(in our `halve`

example, `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:

`fun`

` x -> x / 2`

and, thus, write:

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:

Now, if we make our own comparison operator:

we can use it with our new version of the `msort`

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`

So, for example:

and

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

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?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.Express your function

`cliplist`

again, this time using an anonymous function instead of`clip`

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

Write a function

`filter`

which takes a function of typeand an*α*→ booland returns a list of just those elements of the argument list for which the given function returns*α*list`true`

.Write the function

`for_all`

which, given a function of typeand an argument list of type*α*→ boolevaluates to*α*list`true`

if and only if the function returns`true`

for every element of the list. Give examples of its use.Write a function

`mapl`

which maps a function of typeover a list of type*α*→*β*to produce a list of type*α*list list.*β*list list

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.

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`

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.

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.Write another function

`smallest_or_zero`

which uses the`smallest`

function but if`Not_found`

is raised, returns zero.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.

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

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

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:

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

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

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

Define a function

`replace`

which is like`add`

, but raises`Not_found`

if the key is not already there.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.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.

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.

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.

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

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:

With partial application, we can write

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.

The function `f x y`

has type ** α
→ β →
γ** which can
also be written

`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 -> …`

Rewrite the summary paragraph at the end of this chapter for the three argument function

`g a b c`

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

.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.Write a function

`mapll`

which maps a function over lists of lists of lists. You must not use theconstruct. Is it possible to write a function which works like`let rec`

`map`

,`mapl`

, or`mapll`

depending upon the list given to it?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.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.

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:

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.

And now the same functions with our new sequence type:

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

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:

Here’s a suitable type for such expressions:

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:

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.

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

Now write a function of type rect →

**int**to calculate the area of a given rect.Write a function which rotates a rect such that it is at least as tall as it is wide.

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

`take`

,`drop`

, and`map`

functions for the sequence type.Extend the expr type and the

`evaluate`

function to allow raising a number to a power.Use the option type to deal with the problem that

`Division_by_zero`

may be raised from the`evaluate`

function.

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.

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:

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.

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

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.

Write a function of type

*α*→*α*tree →**bool**to determine if a given element is in a tree.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.

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

Write a function

`tree_of_list`

which builds a tree representation of a dictionary from a list representation of a dictionary.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.

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.

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.

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:

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:

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

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

Normally *β* will be **unit**. Now we can redefine
`print_dict`

using `iter`

:

For example:

` OCaml`

`# print_dict [(1, "one"); (2, "two"); (3, "three")];;`

`1`

`one`

`2`

`two`

`3`

`three`

`- : unit = ()`

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

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:

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")]`

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`

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

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")]`

We have introduced the types **unit**, **in_channel**, and **out_channel**, and the
exception `End_of_file`

. Here are the functions we have
used:

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.

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.

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.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:Adding the special tabulation character

`\t`

after each number will line up the columns.Write a function to count the number of lines in a given file.

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.

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

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

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`

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

OCaml allows us to use ** begin** and

`end`

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

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`

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