<figure><img src="image_1.png" /></figure>

HAL
open science

# Learn Programming with OCaml. Algorithms and Data Structures

Sylvain Conchon, Jean-Christophe Filliâtre, Urmila Nair

► To cite this version:

Sylvain Conchon, Jean-Christophe Filliâtre, Urmila Nair. Learn Programming with OCaml. Algorithms and Data Structures. 2025. hal-04943932

HAL Id: hal-04943932

https://hal.science/hal-04943932v1

Submitted on 12 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
Learn Programming with OCaml

Algorithms and Data Structures

Sylvain Conchon & Jean-Christophe Filliâtre

Translated by Urmila Nair

February 11, 2025
The OCaml Software Foundation funded the translation of this book into En-
glish by Urmila Nair, and suggested that the result be made Open Access. The
present English version is thus available under the license CC BY SA 4.0.

Compiled from commit 4cf4843 on February 11, 2025.
For our wives and daughters
# Contents

## Preface

IX

## I Programming with OCaml

1

### 1 The Working Environment

3

1.1 The Compiler and the Interpreter
3

1.2 A First OCaml Program
4

1.3 Programming Environments
5

1.4 Installing OCaml Libraries
6

### 2 First Steps with OCaml

7

2.1 Leap Years
8

2.2 The Monte-Carlo Method
16

2.3 Drawing a Cardioid
27

2.4 The Mandelbrot Set
33

2.5 Sieve of Eratosthenes
40

— openly licensed via CC BY SA 4.0 —
<table><tbody><tr><td>2.6</td><td>Drawing a Curve</td><td>47</td></tr><tr><td>2.7</td><td>Copying a File</td><td>58</td></tr><tr><td>2.8</td><td>Reversing the Order of Lines in a Text</td><td>66</td></tr><tr><td>2.9</td><td>Converting Integers from an Arbitrary Base</td><td>74</td></tr><tr><td>2.10</td><td>Breakout without Bricks</td><td>83</td></tr><tr><td>2.11</td><td>Logo Turtle</td><td>95</td></tr><tr><td>2.12</td><td>Playing a Musical Score</td><td>102</td></tr><tr><td>2.13</td><td>Quadtrees</td><td>112</td></tr><tr><td>2.14</td><td>Solving the N-Queens Problem</td><td>118</td></tr><tr><td>2.15</td><td>Exercises</td><td>131</td></tr><tr><td><b>3</b></td><td><b>OCaml Concepts: A Closer Look</b></td><td><b>145</b></td></tr><tr><td>3.1</td><td>Type-Checking Algorithm</td><td>145</td></tr><tr><td>3.2</td><td>Runtime Model</td><td>150</td></tr><tr><td>3.3</td><td>Analyzing the Execution Time of a Program</td><td>156</td></tr><tr><td>3.4</td><td>Exercises</td><td>160</td></tr><tr><td><b>II</b></td><td><b>Data Structures</b></td><td><b>163</b></td></tr><tr><td><b>4</b></td><td><b>Arrays</b></td><td><b>165</b></td></tr><tr><td>4.1</td><td>Resizeable Arrays</td><td>165</td></tr><tr><td>4.2</td><td>Bit Vectors</td><td>171</td></tr><tr><td>4.3</td><td>Ropes</td><td>180</td></tr><tr><td>4.4</td><td>Persistent Arrays</td><td>197</td></tr><tr><td>4.5</td><td>Exercises</td><td>201</td></tr><tr><td><b>5</b></td><td><b>Sets and Dictionaries</b></td><td><b>207</b></td></tr><tr><td>5.1</td><td>Binary Search Trees</td><td>208</td></tr><tr><td>5.2</td><td>AVL Trees</td><td>216</td></tr><tr><td>5.3</td><td>Hash Tables</td><td>227</td></tr><tr><td>5.4</td><td>Prefix Trees</td><td>238</td></tr><tr><td>5.5</td><td>Patricia Trees</td><td>248</td></tr><tr><td>5.6</td><td>Exercises</td><td>260</td></tr></tbody></table>
<table><tbody><tr><td><strong>6</strong></td><td><strong>Queues</strong></td><td><strong>267</strong></td></tr><tr><td>6.1</td><td>Imperative Queues</td><td>267</td></tr><tr><td>6.2</td><td>Persistent Queues</td><td>272</td></tr><tr><td>6.3</td><td>Imperative Priority Queues</td><td>274</td></tr><tr><td>6.4</td><td>Persistent Priority Queues</td><td>285</td></tr><tr><td>6.5</td><td>Exercises</td><td>289</td></tr><tr><td><strong>7</strong></td><td><strong>Graphs</strong></td><td><strong>295</strong></td></tr><tr><td>7.1</td><td>Adjacency Matrix</td><td>297</td></tr><tr><td>7.2</td><td>Adjacency Lists</td><td>301</td></tr><tr><td>7.3</td><td>Adjacency Dictionaries</td><td>302</td></tr><tr><td>7.4</td><td>Performance Comparison</td><td>308</td></tr><tr><td>7.5</td><td>Exercices</td><td>309</td></tr><tr><td><strong>8</strong></td><td><strong>Disjoint Sets</strong></td><td><strong>313</strong></td></tr><tr><td>8.1</td><td>The Basic Idea</td><td>313</td></tr><tr><td>8.2</td><td>Implementation</td><td>315</td></tr><tr><td>8.3</td><td>Exercises</td><td>319</td></tr><tr><td><strong>9</strong></td><td><strong>Zippers</strong></td><td><strong>323</strong></td></tr><tr><td>9.1</td><td>Zippers on Lists</td><td>323</td></tr><tr><td>9.2</td><td>Zippers on Trees</td><td>327</td></tr><tr><td>9.3</td><td>Cursors</td><td>335</td></tr><tr><td>9.4</td><td>Exercises</td><td>338</td></tr><tr><td><strong>III</strong></td><td><strong>Algorithmic Techniques and Applications</strong></td><td><strong>341</strong></td></tr><tr><td><strong>10</strong></td><td><strong>Arithmetic</strong></td><td><strong>343</strong></td></tr><tr><td>10.1</td><td>Euclid's Algorithm</td><td>343</td></tr><tr><td>10.2</td><td>Exponentiation by Squaring</td><td>345</td></tr><tr><td>10.3</td><td>Modular Arithmetic</td><td>346</td></tr><tr><td>10.4</td><td>Matrix Calculus</td><td>350</td></tr><tr><td>10.5</td><td>Exercises</td><td>353</td></tr></tbody></table>
<table><tr><td>11 Dynamic Programming and Memoization</td><td>357</td></tr><tr><td>11.1 Basic Idea</td><td>357</td></tr><tr><td>11.2 Mechanical Memoization</td><td>361</td></tr><tr><td>11.3 Differences between Memoization and Dynamic Programming</td><td>364</td></tr><tr><td>11.4 Hash-consing</td><td>366</td></tr><tr><td>11.5 Exercises</td><td>372</td></tr><tr><td>12 Sorting Algorithms</td><td>375</td></tr><tr><td>12.1 Insertion Sort</td><td>376</td></tr><tr><td>12.2 Quicksort</td><td>378</td></tr><tr><td>12.3 Merge Sort</td><td>386</td></tr><tr><td>12.4 Heapsort</td><td>393</td></tr><tr><td>12.5 Optimal Complexity</td><td>400</td></tr><tr><td>12.6 Experimental Evaluation</td><td>400</td></tr><tr><td>12.7 Exercises</td><td>404</td></tr><tr><td>13 Graph Algorithms</td><td>413</td></tr><tr><td>13.1 Breadth-First Search</td><td>413</td></tr><tr><td>13.2 Depth-First Search</td><td>416</td></tr><tr><td>13.3 Shortest Path</td><td>419</td></tr><tr><td>13.4 Minimum spanning tree</td><td>428</td></tr><tr><td>13.5 Exercises</td><td>432</td></tr><tr><td>Index</td><td>449</td></tr></table>
Preface

Learning to program is difficult. To program well requires knowledge of algo-
rithms, imagination, foresight, mastery of a programming language. Most of all,
it requires experience, since the difficulties are often hidden in the details. This
book offers a synthesis based on our own experience, both as programmers and
as teachers of programming.

It is important to remember that style is essential to programming. The same
algorithm can be written in a given language in multiple ways; only some of these
are simultaneously elegant and efficient, which is what the programmer should
strive for, above all else. This is why we chose to use a concrete programming
language, OCaml, rather than pseudocode.

The book is divided into three parts. Part I is an introduction to the OCaml
language. It is aimed at beginners, including both novice programmers and more
experienced programmers who do not know OCaml. Various small programs
will enable the reader to discover the basic concepts of programming and the
OCaml language. Parts II and III focus on fundamental algorithmic concepts,
with a view to enabling readers to write their own programs in an efficient
and structured manner. Algorithmic concepts are presented directly in OCaml

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
syntax, and all the programs in this book can be readily reused.

## Who Should Read This Book

The book is aimed at teachers, students, and programmers seeking to discover and use the OCaml language effectively. For teachers and students, the book may be used as a textbook in courses on algorithms or functional programming. It contains numerous code samples and exercises. For OCaml programmers, it may serve as a reference text in the study of specific data structures or algorithms.

## The Book's Companion Website

All the programs in this book have been compiled and tested with OCaml version 4.14.0. The programs are available at the following address:

http://programmer-avec-ocaml.lri.fr/

## Acknowledgements

We would like to thank François Pottier for discussions regarding the creation of this book. We are also very grateful to our colleagues Arthur Charguéraud and Frédéric Voisin for their careful and constructive revision of the text. We would also like to thank everyone who read and commented on it: Thomas Braibant, Martin Clochard, David Declerck, Léon Gondelman, Louis Mandel, Simão Melo de Sousa, Mattias Roux. Finally, we thank the Eyrolles editorial team for their precious help in putting the book together.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
# Part I

## Programming with OCaml

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
<figure><img src="image_3.png" /></figure>
# 1

# The Working Environment

The OCaml language is available for use with the main operating systems (Linux, macOS, Windows). It can be obtained at the following address:

https://ocaml.org/

The site contains installation instructions for these systems. Once you have installed OCaml, you will have access to the following tools: an interpreter, *ocaml*; two compilers, *ocamlc* and *ocamlopt*; and a package manager, *opam*. We briefly present these four tools below.

## 1.1 The Compiler and the Interpreter

The OCaml system includes two compilers: *ocamlc* and *ocamlopt*. The first generates portable code, independent of the hardware architecture; the second generates more efficient native code (X86, ARM, etc.). You can use either of these two tools to compile the programs given in this book. The system also includes an interactive version, namely, the program *ocaml*. This is an interpreter or *t LEVEL* that executes a read-eval-print loop (REPL).

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
## 1.2 A First OCaml Program

We illustrate the use of these tools with a simple program that displays the message `Hello world!` on the screen. It can be written as follows:

```ocaml
let () = print_string "Hello world!\n"
```

This is itself a complete program. We will go into the details of such programs in the next chapter. If the program is stored in a file `hello.ml`, it can be compiled from within a terminal<fnref n="1" /> using `ocamlc`, as follows:

```bash
> ocamlc hello.ml
```

We can then execute the resulting binary, `a.out`, with the expected result:

```bash
> ./a.out
Hello world!
```

The binary can be given a different name using the compiler's `-o` option:

```bash
> ocamlc -o hello hello.ml
> ./hello
Hello world!
```

To use the interpreter, it suffices to type the command `ocaml` in a terminal. The program then displays a prompt in the form of the character `#`, prompting the user to enter an expression.

```bash
> ocaml
OCaml version 4.14.0
#
```

To be evaluated, the expression must end with two semicolons `;;` followed by a carriage return. The `tLEVEL` verifies that the expression is syntactically correct and well-typed. It then evaluates the expression and displays the result. Thus, in order to display the message `Hello world!` on the screen, it suffices to type:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —

<footnote n="1">¹The symbol `>` designates the terminal prompt from which commands are launched.</footnote>
```
> ocaml
OCaml version 4.14.0

# let () = print_string "Hello world!\n";;
Hello world!
#
```

In addition to the result, the toplevel also displays the type inferred by OCaml for the expression that has been entered. For example, if you enter the mathematical expression $1+4 \times 2$, the interpreter returns the following response:

```
# 1 + 4 * 2;;
- : int = 9
#
```

This shows that the expression is of type `int` (the type of integers), and that its result is 9. From now on, we will present the expression entered by the user and the interpreter's response against a **gray background**. Thus, the evaluation of the preceding expression will be presented, as follows:

```
# 1 + 4 * 2 ;;
- : int = 9
```

To exit the toplevel, type the command `#quit`, as follows:

```
# #quit;;
>
```

A simpler way to do this is to press the keys `ctrl` and `D` simultaneously.

## 1.3 Programming Environments

As with many other programming languages, you can work with OCaml using your preferred text editor (Emacs, Visual Studio Code, etc.). The text editor may be configured with OCaml-specific syntax coloring, error highlighting, and so forth.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
In this text, we will use the tool **dune** to automate the compilation process. This tool can be obtained via the **opam** package manager, and can be installed by typing the following command in a terminal:

> opam install dune

Another solution is to use the tool **make**. This requires writing a configuration file (**Makefile**) specific to OCaml.

## Online Environments

There are also online solutions for using OCaml without installing it on your machine. One example is the online interpreter TryOCaml, available at the following address:

https://try.ocamlpro.com/

Another example is the website

https://replit.com/

which offers online environments for a number of languages, among them OCaml.

## 1.4 Installing OCaml Libraries

The community of OCaml users has developed a number of OCaml libraries. The easiest way to install them is to use the package manager **opam**. In the next chapter, we will use a graphics library, which may be installed as follows:

> opam install graphics

We will explain later how to use this library and, more generally, any library installed using **opam**.
2

First Steps with OCaml

The best way to learn a programming language is by programming. We therefore present below fourteen (little) programs to get started with OCaml. The aim is to introduce the basic constructions and ideas of the language.
Program 1 [leap_year.ml] — Leap Year

```ocaml
let year = read_int ()
let leap =
    (year mod 4 = 0 && year mod 100 <> 0) || year mod 400 = 0
let msg = if leap then "is" else "is not"
let () = Printf printf "%d %s a leap year\n" year msg
```

## 2.1 Leap Years

<figure><img src="image_4.png" /></figure>

### Ideas introduced

* the general form of a program

* the `let` construct

* calling a function

* basic types (`int`, `bool`, `string`)

* standard library (`Printf`, `Sys`, etc.), module system

* access to program arguments (`Sys.argv`)

* access to the elements of an array (notation `t.(i)`)

Our first program, `leap_year.ml`, determines if a given year is a leap year. We can compile it using `ocamlc`.

```
> ocamlc -o leap_year leap_year.ml
```

When the program is launched, it waits for the user to enter a year. It then prints whether the year is a leap year or not.

```
> ./leap_year
2013
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
2013 is not a leap year

Let us now consider the structure of this program. The first line reads an integer from standard input:

let year = read_int ()

This line alone contains several notions of the OCaml language. Firstly, it is a *variable declaration* of the form:

let year = ...

This initializes a new variable `year` with the result of the expression to the right of the symbol `=`. The type of the variable `year` does not have to be declared; it is automatically deduced by the compiler or the interpreter. The expression to the right of the symbol `=` is a *function call*. It is a call to the predefined function `read_int`.

... = read_int ()

Here, `()` indicates that the function `read_int` does not take any meaningful argument. It only returns an integer, read from standard input.

The second line introduces a boolean variable `leap` whose value is `true` if and only if `year` is a leap year, that is, if it is divisible by 4 but not by 100, or if it is divisible by 400.

let leap =
  (year mod 4 = 0 && year mod 100 <> 0) || year mod 400 = 0

The infix operator `mod` returns the remainder of integer division. The operators `&&` and `||` represent the boolean AND and OR, respectively. As with `year`, the type of the variable `leap` is deduced automatically. The following line introduces a third variable, `msg`, which contains a string:

let msg = if leap then "is" else "is not"

The variable `msg` will contain the string `"is"` if `leap` is true, and the string `"is not"` if it is false. (Strings are delimited by double quotes `"`.) Note that the construction `if-then-else` is used here to construct an expression, namely, a string.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Finally, the last line prints a message that indicates whether or not the year entered is a leap year.

```ocaml
let () = Printfelmprintf "%d %s a leap year\n" year msg
```

This is achieved by calling the library function `Printfelmprintf` with three arguments: a formatting string `"%d %s a leap year\n"` together with the two values, `year` and `msg`, which respectively replace `%d` and `%s` in the printed message. As you can see, the function call is denoted by simply juxtaposing the function and its arguments. Unlike other languages, OCaml does not use parentheses around arguments.

```ocaml
... = Printfelmprintf "%d %s a leap year\n" year msg
```

We refer the reader to the OCaml manual for further information on the standard library and, in particular, on the function `Printfelmprintf`. The manual is available online at the address: https://ocaml.org/manual. Finally, note that the call to the function `printf` is contained in a declaration of a specific form:

```ocaml
let () = ...
```

This is somewhat enigmatic, and will be left so for the present. It will be explained when we discuss pattern matching in sections 2.6 *Drawing a Curve* and 2.12 *Playing a Musical Score*. For now, suffice it to say that in general an OCaml program is a series of declarations that are evaluated from top to bottom, that is, in the order in which they appear in the source file. Unlike languages like C or Java, there is no `main` entry point. The specific form `let () = ...` is used in order to maintain the same format in case of expressions that do not return a value. When this form is used, OCaml verifies that the expression does indeed not return a value.

## Additional Information

### The Command Line

Rather than reading the year from standard input, we can pass it on the command line. In that case, the program is invoked as follows:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
> ./leap_year 2013
2013 is not a leap year

To do this, we replace the line `let year = read_int ()` with:

`let year = int_of_string Sys.argv.(1)`

This line calls the predefined function `int_of_string` with `Sys.argv.(1)` as argument. The value `Sys.argv.(1)` contains the year passed as parameter on the command line. As is the case with other programming languages (Java or C, for example), we can retrieve the values passed to the program in the form of an array of strings, designated `Sys.argv` in OCaml. More precisely, the array is called `argv`, and it is available within the `Sys` module, which consists of an interface to the operating system. The notation `Sys.argv` involves the *module system* of OCaml, that organizes libraries in terms of units, called *modules*, which themselves contain different values. Without getting into the details of the module system, suffice it to say for now that we refer to a value in a module by writing the name of the module, followed by the name of the value, separated by a dot. (We will discuss this in greater detail in section 2.11 *Logo Turtle*.) Thus, `Sys.argv` must be read as “the array `argv` that belongs to the module `Sys`.”

We use the notation `t.(i)` to access the i-th element of an array `t`. We will return to the notion of arrays in section 2.5 *The Sieve of Eratosthenes*. The first element of `Sys.argv` is `Sys.argv.(0)` since arrays are indexed starting from 0. This is the program's name (here `leap_year`). The second element is `Sys.argv.(1)`. This is the first parameter passed to the program (2013 in our example). Since it is a string, it must be converted into an integer by calling the function `int_of_string`, which belongs to the module `Stdlib`. This is a special module for which it is not necessary to write `Stdlib.f`.

## Type-Checking

Let us now condier some additional details regarding the datatypes introduced in our first program. While the types of variables are inferred automatically, it is also possible to display them using the `-i` option of the compiler:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```
> ocamlc -i leap_year.ml
val year : int
val leap : bool
val msg : string
```

We thus see that the variables `year`, `leap`, and `msg` are respectively of type `int`, `bool`, and `string`. These are three predefined types in OCaml. Let us examine these and other related types using the toplevel.

## Types `int`, `int32`, and `int64`

Let us begin with the type `int`, which corresponds to processor-native integers, also called machine integers. An integer constant can be written in decimal, binary (prefix `0b`), octal (prefix `0o`) or hexadecimal (prefix `0x`) notations. Thus, the decimal constant `91` can be written as `0b1011011` in binary, as `0o133` in octal, and as `0x5B` in hexadecimal.

The usual operations on the type `int` are addition (`+`), subtraction (`-`), multiplication (`*`), integer division (`/`), and remainder (`mod`).

```ocaml
# 2 * (7 / 2) + 7 mod 2;;
- : int = 7
```

For greater clarity, the digits may be separated using an underscore (`_`).

```ocaml
# 0x2f_ff_ff_ff + 268_435_456;;
- : int = 1073741823
```

The precision of the type `int` depends on the machine architecture. The minimum and maximum values of the type `int` are given by the two constants `min_int` and `max_int`.

```ocaml
# min_int;;
- : int = -1073741824
```

On a 32-bit machine, values of type `int` are encoded as 31-bit signed integers<fnref n="1" />, so that `min_int` and `max_int` have the values $-2^{30}$ and $2^{30}-1$, respectively. On

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —

<footnote n="1">¹One bit is used by OCaml's automatic memory management system; see section 3.2 *Runtime Model* in chapter 3.</footnote>
a 64-bit machine, the values of type `int` are encoded as 63-bit signed integers. The machine representation of integers uses the two's complement representation and may be manipulated with the help of shift operations (`lsl`, `lsr`, and `asr`) and bitwise operations (`land`, `lor`, `lxor`, and `lnot`). For example, you can test the fifth bit of the representation of the integer 42 using:

```h
# 42 land (1 lsl 5);;
- : int = 32
```

To manipulate 32-bit or 64-bit signed integers, OCaml offers two specific types: `int32` and `int64`. The integer constants of type `int32` (or `int64`) are written with the suffix `l` (or `L`).

```h
# 1231;;
- : int32 = 1231
# 10_000_000_000_000L;;
- : int64 = 100000000000000L
```

The arithmetic operations on these two types may be found in the OCaml modules `Int32` and `Int64`.

## The Type `bool`

The type `bool` represents boolean values, that is, `true` and `false`. The operations on the type `bool` are conjunction (`&&`), disjunction (`||`), and negation (`not`).

```h
# not true && false || true;;
- : bool = true
```

Negation has the highest priority, followed by conjunction, and then disjunction. The preceding expression is therefore read as:

```h
# ((not true) && false) || true;;
- : bool = true
```

The evaluation order of the operations `&&` and `||` is fixed from left to right. Furthermore, the second argument is evaluated only if necessary, that is, only

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
if the first argument of the operation `&&` (respectively, `||`) is true (respectively, false). These are the only operations for which the evaluation order is specified. Furthermore, these are the only operations whose evaluation is lazy.

The comparison operations `=`, `<>`, `<`, `>`, `<=`, and `>=` return a boolean.

```ocaml
# 1 < 2 && 3 = 4;;
- : bool = false
```

Boolean expressions are mainly used in the conditional construction `if e1 then e2 else e3`. Depending on whether the expression `e1` is true or false, either the expression `e2` or the expression `e3` is evaluated.

```ocaml
# if 1 < 2 then 3 else 4;;
- : int = 3
```

As is clear in this example, the construction `if then else` is an expression like any other. In particular, for this expression to be well-typed, the two branches `e2` and `e3` must have the same type, which is then the type of the expression as a whole.

## Types `char` and `string`

Characters are represented by the type `char`. They are written between single quotes: `'a'`. Characters that are not printable are entered using a notation of the form `'\c'`, where `c` can be a character (`n`, `r`, `t`, `\`), or an ASCII code (between 0 and 255), written with three decimal digits (`\ddd`) or two hexadecimal digits (`\ddd`).

```ocaml
# 'a';;
- : char = 'a'
# '\n';;
- : char = '\n'
# '\\';;
- : char = '\\'
# '\126';;
- : char = '~~'
# '\x7E';;
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
- : char = 'a'

You can convert a character to its ASCII code and vice versa with the help of the functions `Char.code` and `Char.chr` of the `Char` module.

Strings are represented by the type `string`. They are written within double quotes: `"abc"`. Within a string, characters that are not printable may be entered with the same syntax used for the type `char`.

# "a";;
- : string = "a"
# "hello world\n";;
- : string = "hello world\n"
# "";;
- : string = ""
# "abc\126def";;
- : string = "abc~def"

As is clear in this example, the string "a" does not have the same type as the character 'a'. In general, there is no conversion between these two types. You can access the i-th character of a string `s` with the notation `s.[i]`, the first character having index 0.

# "abc".[1];;
- : char = 'b'

The length of a string is given by the function `String.length` of the module `String`. Finally, two strings can be concatenated using the operator `^`.

# String.length("abc" ^ "def");
- : int = 6

The reader is referred to the OCaml manual for further details regarding the modules presented in this chapter.

## Input/Output

The simplest input/output functions are those that print values of basic types, such as `print_string`, which was used above to print `Hello world`. Other such

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
functions include `print_char`, `print_int`, and `print_float`; `print_newline`, to print a carriage return; and `print_endline`, to print a string followed by a carriage return. These six printing functions write to standard output. To write to standard error, there are six other functions: `prerr_char`, `prerr_string`, etc. Likewise, there are functions that read from standard input, namely `read_int`, `read_float`, and `read_line`. There is also a variant of the function `printf` to write to standard error, `printf.eprintf`. You will find more details regarding input/output in section 2.7 *Copying a File*.

## 2.2 The Monte-Carlo Method

<figure><img src="image_5.png" /></figure>

### Ideas introduced

* side effects, expression sequences, references (`ref` keyword)

* local variables (`let-in` construct)

* `for` loops

* floating-point numbers (type `float`)

* random number generation using the module `Random`

Our second program (see page 18), `approx_pi.ml`, calculates the value of $\pi$ experimentally using the Monte-Carlo method. This method consists in randomly generating points in a square of side 1, whose area is therefore 1, and then counting the number of those points that lie within a quarter circle of radius 1 inscribed in this square. The area of the quarter circle is $\pi/4$. Figure 2.1 illustrates the idea.

We compile the program `approx_pi.ml`, for instance using `ocamlopt` (for greater efficiency), as follows:

```
> ocamlopt -o approx_pi approx_pi.ml
```

We then execute the program and give it the number of points to be generated. If this number is sufficiently large, the proportion of points contained within the

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
<figure><img src="image_6.png" /><figcaption>Figure 2.1: Computation of $\pi$ using the Monte-Carlo method.</figcaption></figure>

quarter circle approaches the ratio of the area of the quarter circle to that of the square, that is, $\pi/4$. We obtain the following results:

```
> ./approx_pi
500
3.136000
> ./approx_pi
5000
3.113600
> ./approx_pi
50000
3.149920
> ./approx_pi
500000
3.142184
```

In practice, however, this method yields a value of $\pi$ that is accurate only to a few decimal places. For example, with 10 million points, the value is accurate only to the third decimal place.

As in our first program, the first line of `approx_pi.ml` obtains the number $n$ of points to be generated by reading an integer from standard input:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Program 2 [approx_pi.ml] — Approximation of π

``` Ocaml
let n = read_int ()

let () =
  let p = ref 0 in
  for k = 1 to n do
    let x = Random.float 1.0 in
    let y = Random.float 1.0 in
    if x *. x +. y *. y <= 1.0 then
      p := !p + 1
    done;
    let pi = 4.0 *. float !p / . float n in
    Printf printf "%f\n" pi
```

``` Ocaml
let n = read_int ()
```

The rest of the program uses a loop to generate $n$ points at random. In each iteration of the loop, we increase by 1 the contents of a variable initialized with 0 if the generated point lies within the quarter circle of radius 1. At the end, we display the approximate value of $\pi$, which equals four times the ratio of the number of points within the quarter circle to the total number of points.

Computing in this manner, by modifying the contents of a variable, is called computation by side effects. More generally, the term side effect is used in relation to expressions that do not return a value when evaluated. As we have mentioned in the previous section, a declaration of the form `let () = ...` is used to evaluate such expressions.

The rest of the program consists in the expression that follows the `=` sign. It begins with the initialization of a variable `p` using a declaration of the form:

``` Ocaml
let p = ... in
...
```

This declaration introduces a *local variable*, whose use or *scope* is restricted to

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
the expression that follows the keyword `in`. This kind of declaration is useful when one wishes to restrict the visibility of a variable, whether to prevent its usage in other parts of the program or because one wishes to hide temporarily another variable with the same name.

The variable `p` is initialized with a *reference*, that is, a memory cell, the contents of which can be modified, and which initially contains the value 0. This reference will be used to count the number of points that fall within the quarter circle.

```pascal
let p = ref 0 in
...
```

The variable `p` is created by calling the predefined function `ref` (defined in the `Stdlib` module) with the integer 0 as argument. The application of this function has the effect of allocating a new memory cell and initializing its contents to 0. The type of `p` inferred by OCaml is `int ref`, read as "a reference containing a value of type `int`."

The next line introduces a *for loop* that evaluates the expression situated between the keywords `do` and `done n` times, while varying the contents of a variable `k` from 1 to `n`:

```pascal
for k = 1 to n do
  ...
done
```

The variable `k` is the *index* of the loop, and the expression between `do` and `done` is the *body* of the loop. The index `k` is initialized with the value 1. Then, the body is evaluated. This is the first iteration of the loop. Then, `k` is increased, and the body is evaluated again. This is the second iteration of the loop. And so on and so forth. Following the evaluation for which `k` equals `n`, the loop terminates.

The body of the loop begins by generating the coordinates of a point $(x, y)$ randomly within the square of side 1.

```pascal
let x = Random.float 1.0 in
let y = Random.float 1.0 in
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
To this end, two local variables, `x` and `y`, are initialized by two calls to the function `Random.float` with the floating-point number 1.0 as argument. Each of these calls returns a floating-point number between 0 and 1 (including 0 and excluding 1). As we will see later, OCaml makes a strong distinction between floating-point numbers, which are of type `float`, and integers, which are of type `int`. Crucially, a dot must be inserted after the number 1 to represent the floating-point number 1. We thus write `1.0` or `1.` to distinguish it from the integer 1 of type `int`.

The conditional that follows increases the contents of the reference `p` if the point `(x, y)` is within the quarter circle, that is, if `x² + y² ≤ 1`.

```ocaml
if x *. x +. y *. y <= 1.0 then
  p := !p + 1
```

As we see in the expression `x *. x +. y *. y`, the arithmetic operators on floating-point numbers are also distinguished syntactically from operators on integers: A dot `.` must be added after the sign of each operator (`+`, `-`, etc.). Thus, `+.` is the addition operator on floats, `.*` the multiplication operator, etc. However, the same operator `<=` is used to compare floats and integers. (See chapter 3 for further details on comparison operators.)

The expression `p := !p + 1` is used to increase the reference `p` by 1. Here, the assignment operator `:=` serves to modify the contents of a reference, and the prefix unary *dereference* operator `!` is used to retrieve the contents of a reference. Thus, if `p` is a reference of type `int ref`, the value `!p` is of type `int`. The loop ends after the iteration for which `k` equals `n`. The evaluation then continues with the expression that follows the `;` operator.

```ocaml
for k = 1 to n do
  ...
done;
```

Such a series of evaluations is called an *expression sequence*. For an expression sequence to be accepted by OCaml, the expression before the semicolon must not return a value, that is, it must only perform side effects.

The declaration that follows the `for` loop defines a local variable `pi` containing the approximation of $\pi$.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
let pi = 4.0 * . float !p / . float n in

In order to perform a division of floating-point numbers, the integer values !p and n are converted into floats using the function `float` (defined in the `Stdlib` module). Finally, we display the approximation of $\pi$ thus calculated using the function `FORMAT`:

FORMAT `FORMAT` "%f\n" pi

Just as we used `%d` in a formatting string to display an integer, here we use `%f` to display a float.

### Additional Information

Here, we present further explanations regarding the ideas introduced in this second program.

#### The Type `float`

Real numbers are represented in the computer using a specific kind of encoding called *floating-point numbers*, or more simply *floats*. In OCaml, floating-point numbers are encoded using the double-precision IEEE 754 standard (64 bits). There are no single-precision (32 bits) floating-point numbers in OCaml.

As we noted earlier, the type of floating-point numbers is `float`. A constant of type `float` is written either in decimal notation (for example, `3.14`) or in scientific notation (for example, `6.02214e23`). A dot must always be used in the decimal notation, to indicate that the constant is not of type `int`. In case of scientific notation, however, the dot is not compulsory.

```ocaml
# 3 ;;
- : int = 3
# 3. ;;
- : float = 3.
# 1e6 ;;
- : float = 1000000.
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Operations on the type `float` are distinct from those on the type `int`. They are followed by a dot, as in case of floating-point constants: `+`, `-`, `*`, `/`. Unlike in other languages, arithmetic operations thus have different names depending on whether integers or floats are involved, and there are no implicit conversions between the types `int` and `float`.

```ocaml
# 2 +. 3.14;;
Error: This expression has type int but an expression was
       expected of type float
```

The conversion functions `float` and `truncate` must be used to convert integers to floats and vice versa.

```ocaml
# 3.14 /. float 2;;
- : float = 1.57
# truncate 3.141592;;
- : int = 3
```

Numerous operations on the type `float` are available in the `Stdlib` module, such as exponentiation `**`, square root `sqrt`, trigonometric functions, logarithmic functions, etc. Thus, the value of $\pi$, which is not predefined in OCaml, could be calculated using the following expression:

```ocaml
# 4. *. atan 1.;;
- : float = 3.14159265358979312
```

Unlike the type `int`, the type `float` includes three additional values, `neg_infinity`, `infinity`, and `nan`, that represent calculations that have no meaningful result.

```ocaml
# -1. / . 0.;;
- : float = neg_infinity
# 1. / . 0.;;
- : float = infinity
# 0. / . 0.;;
- : float = nan
```

Unlike other languages, OCaml offers only one type of floating-point numbers, namely, 64-bit double-precision floats conforming to the IEEE 754 stan-

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Floats lie between a minimum value `min_float` and a maximum value `max_float`.

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

### The let and let-in Constructs

The `let` and `let-in` constructs are used, respectively, to define global and local variables. Two important points must be noted regarding variables:

* Variables are necessarily initialized.

* The type of a variable is automatically inferred.

The first point results simply from the fact that variables can only be defined using the constructions `let` and `let-in`, whose syntax requires an expression for the initial value. The second point is specific to the OCaml language.

You can use the `totype` to find out the type inferred for a variable. For instance, if we type the following declaration:

```c
# let x = 1+2;;
```

The interpreter displays the response:

```
val x : int = 3
```

This indicates that we have defined a global variable `x`, initialized with the integer 3. The type of `x` is inferred from the expression `1+2`, namely, `int`.

It is equally important to master the *scoping rules* of variables declared by a `let` or `let-in` construct. The scope of a global variable `x` begins immediately after the declaration `let x = ...` used to define it. This scope extends until the end of the program. The scope of a local variable introduced with the `let-in` construct is limited to the expression that follows the keyword `in`. Thus, each of the three declarations below triggers a scoping error:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```ocaml
# let x = x + 1;;
Error: Unbound value x
# (let v = 1 + 2 in v * v) + v;;
Error: Unbound value v
# let z = 1 + z in z * 2;;
Error: Unbound value z
```

The three declarations above illustrate an important rule regarding variable usage: To be used, a variable must have been declared beforehand. The following program is therefore correct:

```ocaml
let x = 10
let y = x+2
```

By contrast, the program below is wrong:

```ocaml
let y = x+2
let x = 10
```

It is important to note that in the expression `let x = e1 in e2; e3`, the scope of the variable `x` extends to the entire expression `e2; e3`. The precedence of the operator `;` is higher than that of the construction `let`. In other words, this expression must be read as: `let x = e1 in (e2; e3)`. Program 2.2 uses this scoping rule in the declaration of the local variable `p`.

```ocaml
let () =
  let p = ... in
  for k = 1 to n do
    ...
    p := !p + 1
  done;
let pi = 4. * float !p / . float n in
...
```

Thus, the variable `p` is visible both in the `for` loop and in the body of the declaration of the variable `pi`.

You can use the same name for several variables, including those of different types. The use of a variable `x` always refers to the nearest declaration. Consider

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
the following program as an example:

```pascal
let x = 10
let y = x + 2
let x = 20
let () = Printfprintf("x=%d y=%d\n" x y
```

The declaration `let x = 20` defines a new variable `x`, which hides the scope of the previous one. The message displayed when you execute the program is therefore `x=20 y=12`.

### The for Loop

As we have seen in our example, `for` loops are used to evaluate a given expression a certain number of times. They have the following form:

```pascal
for i = e1 to e2 do
  e
  done
```

The index of the loop, the variable `i`, is introduced by the `for` construct. Its value cannot be modified by the user. Its scope is limited to the body of the loop (the expression `e`), and therefore it cannot be used in the expressions `e1` and `e2`. These two expressions are evaluated only once, before the execution of the loop. This can be observed with the following program:

```pascal
let () =
  for i = (Printfprintf "*"; 0) to (Printfprintf "."; 5) do
    Printfprintf "%d" i
  done
```

When you execute this program, it displays the string `*.012345`. The evaluation of the `for` loop begins with the initialization of the index `i` with the value of the expression `(Printfprintf "*"; 0)`. The evaluation of this sequence first causes the symbol `*` to be printed. Then, the integer `0` is returned. The fact that the second printed character is a dot `.` indicates that the expression `(Printfprintf "."; 5)`, which corresponds to the final value of the index, is

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
evaluated next. As the rest of the message contains only the numbers displayed by the expression `Formatprintf "%d" i` of the body of the loop, it may be deduced that the expressions `e1` and `e2` are not evaluated again. It is also important to note that if the value of `e1` is strictly greater than that of `e2`, the body of the loop is never executed.

There is also a variant of the `for` construct that goes backwards. For example, the following program displays the numbers 9 8 7 6 5 4 3 2 1 0, in this order.

```ocaml
let () =
    for i = 9 downto 0 do
        Formatprintf "%d " i
done
```

Note that the index can only be increased or decreased by 1 in each iteration. For other increments, it is possible to use a `while` loop, which will be discussed later.

For the sake of completeness, let us note that the body of the `for` loop in program 2.2 does not make use of the loop index `k`. The OCaml compiler can detect this and emit a warning, if we add the command-line option `-w +a`:

```
> ocamlopt -w +a -o approx_pi approx_pi.ml
Warning 35 [unused-for-index]: unused for-loop index k.
```

A solution is to avoid naming the index of the loop, by replacing it with an underscore `_`.

```ocaml
for _ = 1 to n do
```

This does not change the behavior of the `for` loop in any way.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
### 2.3 Drawing a Cardioid

<figure><img src="image_7.png" /></figure>

**Ideas introduced**

* open directive

* library (extension .cma)

* library Graphics

* function ignore

Our third program (see page 28), `cardioid.ml`, draws a cardioid, that is, a curve that represents the trajectory of a fixed point on a circle that turns around a second circle of the same diameter, as shown in figure 2.2.

<figure><img src="image_8.png" /><figcaption>Figure 2.2: Drawing a cardioid.</figcaption></figure>

Mathematically, a cardioid is an algebraic plane curve that may be defined by the following parametric equations:

$$ \begin{cases} x(\theta) = a (1 - \sin(\theta)) \cos(\theta) \\ y(\theta) = a (1 - \sin(\theta)) \sin(\theta) \end{cases} $$

where a is the radius of each circle.

To trace the cardioid, we use the OCaml library `Graphics`, which allows you to open a two-dimensional graphical window and draw in it using elementary graphical functions. This library contains a single module, also called `Graphics`. Since we will be using a number of functions of this module, the program begins with a directive to open the module:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 3 [cardioid.ml] — Drawing a cardioid

```ocaml
open Graphics

let () = open_graph " 300x200"

let () =
  moveto 200 150;
  for i = 0 to 200 do
    let th = atan 1. * . float i / . 25. in
    let r = 50. * . (1. -. sin th) in
    lineto (150 + truncate (r *. cos th))
      (150 + truncate (r *. sin th))
  done;
  ignore (read_key())
```

### open Graphics

We will thus be able to use the values and functions of this library without having to prefix them each time with the name of the module, `Graphics`.

The following line opens a graphical window with the function `open_graph`. This function takes as argument a string indicating the window's dimensions.

```ocaml
let () = open_graph " 300x200"
```

This statement opens a window of size 300 × 200, that is, 300 pixels wide and 200 pixels high. (Note that the space at the start of the string is mandatory.) We then draw within this window using integer coordinates, the origin being located at the bottom left of the window, the *x*-coordinates taking values from 0 to 299 and the *y*-coordinates from 0 to 199 (see figure 2.3).

The rest of the program plots the cardioid. Since this part of the code does not return a value, we place it within a declaration of the form:

```ocaml
let () = ...
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_9.png" /><figcaption>Figure 2.3: Coordinate system of the library Graphics.</figcaption></figure>

The functions we will use to draw the cardioid rely on a notion of *current point*. This point can be positioned using `moveto`. A call to `lineto x y` traces a line segment from the current point to the point with coordinates `(x,y)`, which then becomes the new current point.

We begin by placing the current point at (200, 150), by calling the function `moveto`, with a view to drawing a cardioid beginning at this point:

```
moveto 200 150;
```

We use a `for` loop to vary the angle $\theta$ between 0 and $2\pi$. For this, we make use of an integer index $i$ varying from 0 to 200, and we use the fact that $\arctan(1) = \pi/4$ to calculate $\theta$ as $\arctan(1) \times i/25$.

```ocaml
for i = 0 to 200 do
  let th = atan 1. * float i / 25. in
  ...
done
```

In OCaml, the arctangent of an angle, expressed in radians, is calculated using the function `atan` of the standard library `Stdlib`.

The following line defines a local variable `r` with the value of the intermediate subexpression $a(1 - \sin(\theta))$, where the radius $a$ of the cardioid is fixed at 50

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
pixels:

let r = 50. *. (1. -. sin th) in

This variable is used to factor out one part of the calculation of the coordinates of the point $(x(\theta), y(\theta))$.

Finally, using the function `lineto`, we trace a segment between the current point and the point with coordinates $(x(\theta), y(\theta))$. Since graphical coordinates are integers, we use the function `truncate` to extract the integer part of the expressions used to calculate the coordinates.

lineto (150 + truncate (r *. cos th))
(150 + truncate (r *. sin th))

After the `for` loop, the last line of the code pauses the program, waiting for a key to be pressed. This is in order to keep the graphical window from closing immediately after the drawing finishes.

ignore (read_key())

Since we are only waiting for a key to be pressed, we ignore the actual character returned by the function `read_key` using the predefined function `ignore`.

## Compilation

In order to compile the program `cardioid.ml`, we must explicitly tell the compiler that we wish to use the library `Graphics`. This is not needed in case of the modules we saw earlier, such as `Sys`, `Arg` or ``, which belong to the OCaml standard library. The `Graphics` library is contained in the file `graphics.cmxa`, which must be added to the command line. Furthermore, we must tell the compiler the location of this file, which was installed by `opam`. This can be done using the following command:

> ocamlopt -I 'ocamlfind query graphics' graphics.cmxa cardioid.ml -o cardioid

The tool `ocamlfind` allows you to find the location of the library `graphics`, which is then passed to the OCaml compiler using the `-I` option. (Note that the

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
command `ocamlfind query graphics` has to be placed between backquotes.)
If you wish to use the `ocamlc` compiler, you should replace the suffix `.cmxa` by `.cma`. As we will see in section 2.10 *Breakout without Bricks*, the order of the files on the command line of the compiler is important: Here, `graphics.cmxa` must appear before `cardioid.ml` since the latter uses the library `Graphics`.

Another way of compiling our program consists in using `dune`. To do this, we write a configuration file, which must be named `dune`, in the directory containing `cardioid.ml`. This file should contain the following:

```
(executable
(name cardioid)
(libraries graphics))
```

This specifies that we wish to construct an executable that is named `cardioid`, and that uses the library `graphics`. Assuming that our two files `cardioid.ml` and `dune` are in the directory `my-first-project/`, we must first perform an initialization step with the following command:

```
> dune init project my-first-project/
```

We can then shift to the directory `my-first-project/` and build the executable there:

```
> cd my-first-project/
```

```
> dune build
```

Finally, we can execute the program with the following command:

```
> dune exec ./cardioid.exe
```

The executable is named `cardioid.exe`, where the extension `.exe` is added by `dune`. It is stored in a subdirectory `_build/default/`, and the command `dune exec` allows us to launch it directly.

To use the library `Graphics` from within the toplevel `ocaml`, it suffices to type the following command in the terminal:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
> ocaml -I 'ocamlfind query graphics' graphics.cma
OCaml version 4.14.0
#

Note that the library *Graphics* can also be used directly from within TryOCaml.

## The Library Graphics

In addition to the functions `moveto` and `lineto` used in our program `cardioid.ml`, the library *Graphics* offers various other functions: `plot`, to plot a point; `set_color`, to modify the display color; `draw_circle`, to draw a circle; `set_line_width`, to change the line thickness; `fill_rect`, to shade a rectangle; `draw_string`, to display a string, etc. The reader is referred to the OCaml manual's web page for a complete description of this library. It is important to note that, although the features of *Graphics* are limited, this library has the advantage of being available on many architectures. If you wish to use a more sophisticated library, you can use (depending on your operating system):

* OCaml-Canvas: a portable Canvas framework for OCaml, with an interface similar to HTML5 Canvas.

* LablTk: a Tcl/Tk library that allows you to create graphical user interfaces (GUI) with drop-down menus, buttons, etc.

* Lablgtk: similar to LablTk but based on the graphical library Gtk.

* OCamlsdl: an SDL library mainly used to create video games.

This list is not exhaustive.
## 2.4 The Mandelbrot Set

<figure><img src="image_10.png" /></figure>

### Ideas introduced

* function declarations

* recursive functions

* type `unit` and the value `()`

Program 2.4 (see page 35) draws the Mandelbrot set (see figure 2.4). It is defined as the set of points $(a, b)$ of the plane for which neither of the following two recursive sequences tends to infinity in absolute value.

$$x_0 = 0$$

$$y_0 = 0$$

$$x_{n+1} = x_n^2 - y_n^2 + a$$

$$y_{n+1} = 2x_ny_n + b$$

<figure><img src="image_11.png" /><figcaption>Figure 2.4: Mandelbrot set.</figcaption></figure>

Although there is no exact method to determine whether this condition holds, it can be proven that one of these sequences must tend to infinity as soon as $x_n^2 + y_n^2 > 4$. This result allows us, firstly, to deduce that the points of the Mandelbrot set belong to a disc of radius 2 and center (0,0). Secondly, it enables us to draw an approximation of the Mandelbrot set, defined by the set

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
of points $(a, b)$ such that $x_n^2 + y_n^2 \le 4$ for the first $k$ terms of these sequences. Note that the precision of this approximation depends solely on the number of terms $k$.

The program begins with an `open Graphics` directive to simplify the use of the functions of the graphical library. It continues with the definition of two global variables `width` and `height`, containing respectively the width and height of the graphical window we wish to open (here, $800 \times 800$):

```ocaml
let width = 800
```

```ocaml
let height = 800
```

Next, we fix $k$, the maximum number of terms to be calculated (100 terms sufficing for a good approximation):

```ocaml
let k = 100
```

The following declaration defines a function `norm2` that takes two arguments $x$ and $y$ and returns the value of the expression $x^2 + y^2$.

```ocaml
let norm2 x y = x *. x +. y *. y
```

We discuss this syntactic construction in greater detail at the end of this section. For now, note that, as in the case of a function call, the names of the arguments are only separated by spaces. Note also that the *body* of the function, the expression to the right of the symbol `=`, may be arbitrary.

The following function, `mandelbrot`, determines whether a point with coordinates $(a, b)$ belongs to the Mandelbrot set by calculating the first $k$ terms of the recursive sequences $(x_n)$ and $(y_n)$. In a manner similar to the declaration of `norm2`, we declare the function `mandelbrot` with two arguments $a$ and $b$ as follows:

```ocaml
let mandelbrot a b = ...
```

To calculate the terms of the two recursive sequences, we define a local *recursive* function `mandel_rec` with three arguments $x$, $y$, and $i$.

```ocaml
let rec mandel_rec x y i =
  ...
in
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 4 [mandelbrot.ml] — Drawing the Mandelbrot Fractal

``` Ocaml
open Graphics

let width = 800
let height = 800
let k = 100

let norm2 x y = x *. x +. y *. y

let mandelbrot a b =
  let rec mandel_rec x y i =
    if i = k || norm2 x y > 4. then i = k
    else
      let x' = x *. x -. y *. y +. a in
      let y' = 2. *. x *. y +. b in
      mandel_rec x' y' (i + 1)
  in
  mandel_rec 0. 0. 0

let draw () =
  for w = 0 to width - 1 do
    for h = 0 to height - 1 do
      let a = 4. *. float w /-. float width -. 2. in
      let b = 4. *. float h /-. float height -. 2. in
      if mandelbrot a b then plot w h
    done
  done

let () =
  let dim = Printf.sprintf " %dx%d" width height in
  open_graph dim;
  draw ();
  ignore (read_key())
```

— openly licensed via CC BY SA 4.0 —
The first two arguments `x` and `y` of `mandel_rec` contain the `i`-th values `x_i` and `y_i` of the recursive sequences, and the third argument contains the index `i`.

Before we discuss the body of this function let us note that, syntactically speaking, a declaration of the form `let rec` is used to define a recursive function. This is a function in which you can use its own name within its body. Furthermore, as with local variable declarations, the scope of a *local* function, whether it is introduced by `let-rec-in` or simply `let-in`, is limited to the expression that follows the keyword `in`.

The body of the function `mandel_rec` begins with a test to determine whether we have reached the calculation of the `k`-th term of the sequence, or if the stopping condition `x_i^2 + y_i^2 > 4` holds:

```ocaml
if i = k || norm2 x y > 4. then i = k
else
```

In both cases, the `mandel_rec` function ends and returns a boolean indicating whether or not the point is in the set. If neither of these conditions holds, we calculate `x_{i+1}` and `y_{i+1}` by applying the equations of the recursive sequences, and store them in the local variables `x`' and `y`':

```ocaml
let x' = x *. x -. y *. y +. a in
let y' = 2. *. x *. y +. b in
```

We then call the function `mandel_rec` again to calculate the following terms:

```ocaml
mandel_rec x' y' (i + 1)
in
```

Finally, the `mandelbrot` function starts the calculation by calling the local function `mandel_rec` with the initial values `x_0` and `y_0` as arguments:

```ocaml
in
mandel_rec 0. 0. 0
```

To draw the Mandelbrot set, it suffices to traverse each row and each column of the graphical window and to display the pixels (a, b) for which `mandelbrot a b` returns the value `true`.

The drawing code is contained in a function `draw` that is declared as follows:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
let draw () = ...

A declaration of this form is used to define functions without arguments. To be precise, this declaration defines a function with a *single argument*, denoted by `()`. This is the unique value of a particular type, `unit`. As we will see in section 2.6 *Drawing a Curve*, this is an example of a function defined by *pattern matching*.

The function `draw` traverses the rows and columns of the graphical window using two nested `for` loops:

for w = 0 to width - 1 do
    for h = 0 to height - 1 do
        ...
    done

    done

To draw the Mandelbrot set in a window of size `width` × `height`, we scale the window coordinates to points `(a, b)` in `[-2, 2] × [-2, 2]`, where `a` and `b` are variables defined as follows:

let a = 4. *.* float w / float width -. 2. in
let b = 4. *.* float h / float height -. 2. in

All that remains is to determine whether the point `(a, b)` belongs to the set, by calling the function `mandelbrot` and plotting the point using the function `plot`:

if mandelbrot a b then plot w h
done

done

To complete the program, we open a graphical window of size `width` × `height` by building a string of the form `"wxh"` where `w` and `h` are replaced by the values contained in the variables `width` and `height`.

let () =
    let dim = Printf.sprintf "%dx%d" width height in
    open_graph dim;

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
The string is constructed by calling the function `Format.sprintf` with a formatting string `" %dx%d "`, and the two arguments `width` and `height`. The function `Format.sprintf` is similar to the function `printf`, except that it returns the string as result instead of displaying it.

Finally, we draw the Mandelbrot set by calling the function `draw`. We then wait until a key is pressed to end the program:

```ocaml
draw ();
ignore (read_key())
```

Note that the same syntax is used to call the function `draw`, as is used in its declaration.

## Function Declarations

Let us return to the notion of function in OCaml. A function is declared with the keyword `let`. Thus, a global function `f` that associates `x` with `x + 1` is written simply as:

```hml
# let f x = x + 1;;
val f : int -> int = <fun>
```

As with variables, its type is inferred. More precisely, the type of its argument (here `int`) and that of its result (also `int`) are both inferred. The type of `f` has the form `int -> int`, where the type to the left of the arrow `->` is that of the argument and the type to the right is that of the result. However, the value of `f` is not displayed. Only `<fun>` is displayed, indicating that it is a function.

Functions may be local and follow the same scoping rules as variables.

```hml
# let sqr x = x * x in sqr 3 + sqr 4;;
- : int = 25
# (let sqr x = x * x in sqr 3) + sqr 4;;
Error: Unbound value sqr
```

By default, functions are not recursive.

```hml
# let fact x = if x = 0 then 1 else x * fact (x-1);
Error: Unbound value fact
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The construction `let rec` must be explicitly used to introduce a recursive function.

```hml
# let rec fact x = if x = 0 then 1 else x * fact (x-1);
val fact : int -> int = <fun>
# fact 10;
- : int = 3628800
```

Notice that in the previous example, we wrote `fact (x-1)` and not `fact x-1`. The second expression is understood as `(fact x) - 1` because function application is the operation with the highest precedence.

Mutually recursive functions must be defined simultaneously using the keyword `and`. For example, we can define two mutually recursive functions `f` and `g` as follows:

```hml
let rec f x = ... g ...
and g x = ... f ...
```

A function may take several arguments. These are simply juxtaposed both in the definition and when it is called. For example, the following declaration defines a function `plus` with two arguments:

```hml
# let plus x y = x + y ;;
val plus : int -> int -> int = <fun>
# plus 3 4;
- : int = 7
```

The type inferred by OCaml for this function is `int -> int -> int`. Adding parentheses yields the type `int -> (int -> int)` (the operator `->` is right associative), which is read as: "a function that takes a value of type `int` and returns a function of type `int` to `int`". The function `plus` is therefore seen as a function with one argument that returns a function that awaits the second argument. Thus, strictly speaking, OCaml does not have functions that take multiple arguments. There are only *higher-order* functions with one argument, that is, functions that take a *single* argument and return another function. We will discuss such functions later on (section 2.6 *Drawing a curve*).

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
## 2.5 Sieve of Eratosthenes

<figure><img src="image_12.png" /></figure>

### Ideas introduced

* arrays

* `while` loop

* `begin-end` block

Our next program (see page 41) determines the primality of integers $n \le N$ for a given integer $N$. To do this, it uses an algorithm called the sieve of Eratosthenes. Let us illustrate how it works for $N = 23$. We write down all the integers from 0 to $N$ and progressively eliminate all the integers that are not prime. Hence the name sieve. We begin by noting that 0 and 1 are not prime.

<figure><img src="image_13.png" /></figure>

Next, we determine the first integer that has not yet been eliminated, namely, 2. We eliminate all its multiples, that is, all even integers greater than 2. These are shaded below.

<figure><img src="image_14.png" /></figure>

Then, we repeat the process. The next integer that has not yet been eliminated is 3. We eliminate all the multiples of 3, shown shaded below.

<figure><img src="image_15.png" /></figure>

Note that certain integers have already been eliminated (the multiples of 6 in this case).

The next integer to be considered is 5. Since $5 \times 5 > 23$, the sieve is finished: All multiples of 5, that is, $k \times 5$, have either been eliminated (if $k < 5$) or are greater than 23 (if $k \ge 5$). The integers that remain are the prime numbers less than or equal to $N$: 2, 3, 5, 7, 11, 13, 17, 19 and 23.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
### Program 5 [sieve.ml] — Sieve of Eratosthenes

```ml
let max = read_int ()

let prime = Array.make (max + 1) true

let () =
  prime.(0) <- false;
  prime.(1) <- false;
  let limit = truncate (sqrt (float max)) in
  for n = 2 to limit do
    if prime.(n) then begin
      let m = ref (n * n) in
      while !m <= max do
        prime.(!m) <- false;
        m := !m + n
    done
    end
    done

let () =
  for n = 2 to max do
    if prime.(n) then Printfprintf "%d\n" n
    done
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The program `sieve.ml` implements the sieve of Eratosthenes for a value of $N$ entered on standard input. We store this value in a variable `max`.

``` Ocaml
let max = read_int ()
```

We then create an array of booleans `prime` of size `max+1`. To this end, we use the library function `Array.make`. It takes as arguments the size of the array and a default value for its elements, here `true`.

``` Ocaml
let prime = Array.make (max + 1) true
```

Recall that arrays are indexed starting from 0. The indices of the array `prime` are therefore the integers from 0 to `max`, both included. We begin by indicating that the integers 0 and 1 are not primes, by assigning the value `false` to the two corresponding elements of the array `prime`.

``` Ocaml
let () =
    prime.(0) <- false;
    prime.(1) <- false;
```

For this, we have used the construction `t.(i) <- v`, which assigns the value `v` to the cell with index `i` in the array `t`. This is a special syntax for the library function `Array.set`. We could also have written `Array.set prime 0 false`.

We continue the program by specifying the largest number to be considered. This is $\lfloor\sqrt{max}\rfloor$, which can be calculated thus:

``` Ocaml
let limit = truncate (sqrt (float max)) in
```

The main loop of the sieve then iterates over the integers from 2 to `limit`, testing whether each is prime. The loop therefore has the following structure:

``` Ocaml
for n = 2 to limit do
  if prime.(n) then begin
    ...
  end
```

The construction `begin-end` introduces a *block*, that is, a piece of program that is delimited, indicated here by the ellipses. In OCaml, there is no distinction between expressions and instructions; there are only expressions. The delimited

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
piece of code is thus nothing but an expression; it could have been delimited by parentheses. Nevertheless, the use of `begin-end` highlights the imperative character of this expression.

Let us now discuss this block. It consists of a second loop that eliminates all multiples of *n* in the array *prime*. The same reasoning that allows us to stop the sieve as soon as *n* × *n* > *N* also allows us to begin the elimination from *n* × *n* (rather than 2*n*), the smaller multiples having already been eliminated. To iterate over all the integer multiples of *n* from *n*² onwards, we initialize a reference *m* to the starting value:

```pascal
let m = ref (n * n) in
```

Then, we use a loop that assigns `false` to `prime.(!m)` and increases *m* by *n*, as long as the expression `!m <= max` holds. Such a loop is written using a `while` construct, as follows:

```pascal
while !m <= max do
  prime.(!m) <- false;
  m := !m + n
done
```

Note that, as in case of the `for` loop, the body of the `while` loop is delimited by the keywords `do` and `done`.

This completes the sieve. The values of the array *prime* now indicate which numbers less than or equal to *max* are prime. We can display these prime numbers using another loop.

```pascal
let () =
  for n = 2 to max do
    if prime.(n) then Printfprintf "%d\n" n
  done
```

We could instead have displayed the prime numbers upon finding them, that is, while executing the sieve. However, the sieve's loop stops when $n = \lfloor\sqrt{max}\rfloor$, so that another loop would have been necessary anyway to display the prime numbers between $\lfloor\sqrt{max}\rfloor + 1$ and $max$.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
**Additional Information**

We return here to the constructions `while` and `begin-end` introduced in this section, and then discuss arrays.

**The while Loop**

In general, the syntax of the `while` loop is:

```
while e_1 do
  e_2
  done
```

The expression `e_1` must be of type `bool` and the expression `e_2` of type `unit`.

**The begin-end Block**

The construction `begin-end` is equivalent to a pair of parentheses. Thus, you can write:

```
# 2 * begin 1 + 2 end;;
- : int = 6
```

Nevertheless, the convention is to limit its use to expressions that perform side effects, by analogy with the notion of block in languages such as C or Java.

**Arrays**

An array can be constructed explicitly by specifying the values that make it up.

```
# let t = [| 12; 32; 3; 8 |];
val t : int array = [|12; 32; 3; 8|]
```

To allocate an array of an arbitrary size, in particular, statically unknown size, we use the library function `Array.make`. It takes as arguments the size of the array and a value used to initialize all its cells. (As with any OCaml value, an array must be initialized.)

```
# let u = Array.make 1024 'a';
val u : char array = [|'a'; 'a'; 'a'; ... |]
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The size of an array can be obtained using the library function `Array.length`.

```pascal
# Array.length u;;
- : int = 1024
```

Note finally that accessing an array with an index that lies outside the range of valid indices produces a runtime error, signaled by an exception:

```pascal
# u.(4012);;
Exception: Invalid_argument "index out of bounds".
```

Exceptions will be discussed in detail later on.

### Matrices

There is no predefined type for matrices nor, more generally, for multidimensional arrays. We simply use arrays of arrays. Consider, for instance, the matrix:

$$M = \begin{pmatrix} 1 & 0 \\ 2 & 3 \end{pmatrix}$$

It is represented by the expression:

```pascal
# let m = [[1; 0];
           [2; 3]];;;
val m : int array array = [[1; 0]; [2; 3]];
```

The element $M_{i,j}$ is accessed with `m.(i).(j)`, which is nothing more than two successive accesses: First, we access row `i` with `m.(i.)`, and then, its element at index `j`.

```pascal
# m.(1).(0);;
- : int = 2
```

All operations on matrices are implemented using those of arrays. The module `Array` nonetheless offers an operation to create a matrix, `make_matrix`, which takes as arguments the dimensions of the matrix and the initial value of its elements. We will return to matrices in the section *10.4 Matrix Calculus* of chapter 10.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
## Aliasing

Imperative structures must be handled with caution. In particular, whenever it is possible to reference an imperative structure in multiple ways, you may think you are modifying different data even though this need not be the case.

A typical example of aliasing is obtained by allocating an array with all its elements initialized to the same array. Consider the following expression:

````
Array.make 3 (Array.make 4 v)
````

You may think you are constructing a 3 × 4 matrix, each of whose elements is v. In reality, this expression constructs a *single* array of size 4—let us call it *a*—whose elements have the value v, and an array of size 3, whose three elements are the *same* array *a*. In other words, the result is as follows:

<figure><img src="image_16.png" /></figure>

Of course, this is not what we want, as it has only four elements instead of twelve. To construct an array of arrays correctly, you can use the function `Array.make_matrix` of the standard library, by writing `Array.make_matrix 3 4 v`, which has the effect of constructing the desired matrix, that is:

<figure><img src="image_17.png" /></figure>

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
## 2.6 Drawing a Curve

<figure><img src="image_18.png" /></figure>

### Ideas introduced

* pairs, *n*-tuples

* evaluation order

* first-class, higher order, anonymous functions

* definition by pattern matching, wildcard pattern

Our sixth program (see page 50), `plot.ml`, draws a curve specified by a set of points in the plane. The algorithm consists in joining these points with line segments, proceeding in increasing order of their x-coordinates. For example, the curve drawn for the set of points `{(20, 15), (2, 2), (30, 10), (10, 15)}` is shown in figure 2.5.

<figure><img src="image_19.png" /><figcaption>Figure 2.5: Drawing a curve.</figcaption></figure>

To draw this curve, we begin by reading from standard input an integer that indicates the number of points in the set.

```hml
let n = read_int ()
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Next, we define a function that reads the coordinates of a point from standard input:

```ocaml
let read_pair () =
  let x = read_int () in
  let y = read_int () in
  (x, y)
```

After reading the first integer, `x`, and the second, `y`, from standard input using two calls to `read_int`, the function `read_pair` returns the pair of integers `(x,y)`, constructed very naturally using the syntax `(x,y)`. The type of this pair is written as `int * int` in OCaml. We will discuss pairs and, more generally, *n*-tuples in greater detail at the end of this section.

We then create an array `data` of size `n` that we initialize with the pairs of integers read from standard input. To do this, we use the library function `Array.init` that takes as arguments the size of the array and a function used to initialize the array's cells:

```ocaml
let data = Array.init n (fun i -> read_pair())
```

The function call `Array.init` illustrates two new notions. First, the expression `fun i -> ...` passed as an argument to `Array.init` is an *anonymous function*. The symbol `i` to the left of the arrow `->` represents the argument of the function, the expression to the right, its body. Second, this call shows that functions in OCaml are values like any other. We also say they are *first-class values*. They can be passed as arguments and, as we will see later, returned as the results of other functions. A function like `Array.init`, which takes a function as an argument, is called a *higher-order function*.

The function `Array.init` returns an array obtained by initializing the cell at index `k` (ranging from 0 to `n` - 1) with the value obtained by applying the function `(fun i -> read_pair())` to `k`.

Thus, if the integers entered on standard input consist of the sequence `4 20 15 2 2 30 10 10 15`, the preceding declarations define a variable `n` containing the integer 4 and an array `data` whose contents are graphically represented as follows:

<table><tr><td>(20,15)</td><td>(2,2)</td><td>(30,10)</td><td>(10,15)</td></tr></table>

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
To draw the curve, we must begin by sorting the cells of this array in increasing order of x-coordinates. To this end, we begin by defining a function that compares two pairs by their first component:

```h
let compare (x1, y1) (x2, y2) = x1 - x2
```

This function returns an integer. Its sign is interpreted by the sorting algorithm as follows:

* if $x1 - x2 = 0$, the two pairs are considered to be equal;

* if $x1 - x2 > 0$, the first pair is considered to be greater;

* if $x1 - x2 < 0$, the first pair is considered to be smaller.

Before continuing with the description of our program, let us stop an instant and consider the form of this declaration.

The arguments of the function `compare` are not simple identifiers, but rather *patterns*. They each have the form of a pair $(x_i, y_i)$. The use of patterns allows us here to easily retrieve the components $x_i$ and $y_i$ of the pairs passed as arguments of the function. This is a declaration by *pattern matching*. This form of declaration is very frequently used in OCaml programs, and we will use it on numerous occasions in this book.

To sort the array, we use the higher-order function `Array.sort` which, in addition to the array to be sorted, takes as its first argument a function to compare the elements of the array. This sorting is done in-place, that is, directly within the array `data`. The call to `Array.sort` only performs side effects.

```h
let () = Array.sort compare data
```

At the end of this call, the contents of `data` are as follows:

<table><tr><td>(2,2)</td><td>(10,15)</td><td>(20,15)</td><td>(30,10)</td></tr></table>

All that remains is to draw the curve by joining the points thus ordered, with line segments. We begin with a directive `open Graphics`. Then, we open a graphical window of size 200 × 200. The call `set_line_width 3` fixes the thickness of the line segments.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
## Program 6 [plot.ml] — Drawing a Curve

```ml
let n = read_int ()

let read_pair () =
  let x = read_int () in
  let y = read_int () in
  (x, y)

let data = Array.init n (fun i -> read_pair())

let compare (x1, y1) (x2, y2) = x1 - x2
let () = Array.sort compare data

open Graphics
let () =
  open_graph " 200x200";
  set_line_width 3;
  let (x0,y0) = data.(0) in moveto x0 y0;
  for i = 1 to n-1 do
    let (x,y) = data.(i) in
    lineto x y
  done;
  ignore (read_key())
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```pascal
open Graphics
let () =
    open_graph " 200x200";
    set_line_width 3;
```

We then retrieve the first pair (x0, y0) from the 0-th cell of the array data, and use it to fix the coordinates of the current point using the function `moveto`:

```pascal
let (x0,y0) = data.(0) in moveto x0 y0;
```

Here again, we use a declaration by pattern matching to extract the components of a pair stored in the array. The value contained in `data.(0)` is matched by means of the pattern `(x0, y0)`, which defines two local variables `x0` and `y0`.

We then iterate over all the elements of the array `data` with the help of a `for` loop to join the points:

```pascal
for i = 1 to n-1 do
    let (x,y) = data.(i) in
    lineto x y
done;
```

The body of the loop retrieves the coordinates `(x,y)` of each point using a local declaration by pattern matching (identical to the one above) and draws a line from the current point to the point with coordinates `(x,y)`.

### Additional Information

#### Pairs and *n*-Tuples

A pair of two values `v1` and `v2` can be constructed using the traditional notation `(v1, v2)`. The type of pairs uses the mathematical notation of the Cartesian product.

```pascal
# (1, true);;
- : int * bool = (1, true)
```

You will note that the comma is used to construct *the pair* while the symbol `*` is used to construct *the type* of the pair. The two projections are written `fst` and `snd` respectively.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```ocaml
# fst (1 + 2, true);;
- : int = 3
# snd (1, not true);;
- : bool = false
```

Pairs may be arbitrarily nested.

```ocaml
# ((1, true), (3.14, false));
- : (int * bool) * (float * bool) = ((1, true), (3.14, false))
```

Pairs are a special case of *n*-tuples, and use the same syntax for both values and types.

```ocaml
# (1, true, 3.14);;
- : int * bool * float = (1, true, 3.14)
```

It should be noted that the type `(int * int) * int`, the type `int * (int * int)`, and the type `int * int * int` are not the same:

* the first is that of a pair whose first component is a pair;

* the second is that of a pair whose second component is a pair;

* the third is that of a triple.

## Projections by Pattern Matching and Wildcard Pattern

There are no projection functions for *n*-tuples. A declaration by pattern matching must be used to retrieve each component. For example:

```ocaml
# let (x, (y, z), t) = (1, (true, "hello"), 3.4);;
val x : int = 1
val y : bool = true
val z : string = "hello"
val t : float = 3.4
```

If you only wish to access certain components of an *n*-tuple, you may use a wildcard pattern, which is written as `_,` to avoid having to introduce unnecessary variable names. For example, if you wish only to access the components `x` and `z` of the above triple, you can write the following pattern matching:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```pascal
# let (x, (_, z),_) = (1, (true, "hello"), 3.4);;
val x : int = 1
val z : string = "hello"
```

Wildcard patterns also allow you to represent arbitrary values. Thus, if you only wish to access components x and t, you may use a wildcard pattern to represent the second component of the above triple:

```pascal
# let (x,_, t) = (1, (true, "hello"), 3.4);;
val x : int = 1
val t : float = 3.4
```

### Functions with Several Arguments and n-Tuples

It is equally important to differentiate clearly between a function with several arguments and a function that takes a single argument which is an n-tuple. Consider, for instance, the following function `pyth`:

```pascal
# let pyth (x, y, z) = x*x + y*y = z*z;;
val pyth : int * int * int -> bool = <fun>
```

It takes a triple of integers as argument. You therefore call it using a single argument of the form `(e₁, e₂, e₃)`, as in the following call:

```pascal
# pyth (3, 4, 5);;
- : bool = true
```

On the other hand, the same function may be written as a function of several arguments, as follows:

```pascal
# let pyth x y z = x*x + y*y = z*z;;
val pyth : int -> int -> int -> bool = <fun>
```

This function must be called by juxtaposing its name with three arguments, as in the following call:

```pascal
# pyth 3 4 5;;
- : bool = true
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
The types `int * int * int -> bool` and `int -> int -> int -> bool` illustrate clearly the difference between these two variants. In this text, we adopt the *Curry style*, wherein functions take *n* arguments rather than an *n*-tuple. In particular, this enables the *partial* application of functions: You can pass the function fewer arguments than it expects and obtain another function in return. For example, by applying the function `pyth` to an integer, you obtain a function that takes two arguments:

```ocaml
# let f = pyth 3;;
val f : int -> int -> bool = <fun>
```

You can then apply it several times:

```ocaml
# f 4 5;;
- : bool = true
# f 6 7;;
- : bool = false
```

## Records

Tuples serve to group several values together. However, it is easy to confuse the different components of an *n*-tuple when they have the same type. Thus, a date represented by a triple of integers, of type `int * int * int`, does not indicate clearly which integer designates the day, the month, and the year. To correct this defect, the OCaml language provides the notion of *record*, that is, an *n*-tuple whose fields are named. To create a record, you must declare a new type beforehand, describing the names and the types of the different fields.

```ocaml
# type date = { day : int; month : int; year : int };;
type date = { day : int; month : int; year : int; }
```

We can then construct a value of the type `date` with the following syntax.

```ocaml
# let valentine's_day = { day = 14; month = 2; year = 2014 };;
val valentine's_day : date = { day = 14; month = 2; year = 2014 }
```

We access a field `f` of a record `e` using the notation `e.f`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```c
# valentine's day month;
- : int = 2
```

A new record can be constructed based on another record of the same type, preserving the values of certain fields and giving new values to others. We use the construction `with` for this.

```c
# let d = { valentine's day with day = 15 };
val d : date = {day = 15; month = 2; year = 2014}
```

This is identical to the following declaration:

```c
# let d = { day = 15;
    month = valentine's day.month;
    year = valentine's day.year };
val d : date = {day = 15; month = 2; year = 2014}
```

Another advantage of records over n-tuples is that the order of fields is not significant. We can therefore write:

```c
# let us_valentine's day = { month = 2; day = 14; year = 2014; };
val us_valentine's day : date = {day = 14; month = 2; year = 2014}
# us_valentine's day = valentine's day;
- : bool = true
```

It is also possible to use a pattern to retrieve the values of each field, once again in any order.

```c
# let { day; month; year } = valentine's day;
val day : int = 14
val month : int = 2
val year : int = 2014
```

We can omit certain fields by using the wildcard pattern `_` to indicate the fields to be ignored.

```c
# let { day; month; _ } = valentine's day;
```

Tuples are nevertheless useful, particularly because they do not require us to declare a type.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Records with Mutable Fields

The keyword `mutable` declares a record field that can be modified.

```ocaml
# type student = { number : int; mutable age : int };;
type student = { number : int; mutable age : int; }
```

A record field is modified using the construction `<-`.

```ocaml
# let birthday e = e.age <- e.age + 1;;
val birthday : student -> unit = <fun>
```

This modification does not return a value. Hence its type is `unit`. We observe this side effect in the following example:

```ocaml
# let e = { number = 123456; age = 21 };;
val e : student = {number = 123456; age = 21}
# birthday e;;
- : unit = ()
# e;;
- : student = {number = 123456; age = 22}
```

We can use a record with a `mutable` field to simulate the traditional notion of a mutable variable. For example, in case of a variable of type `int`, it suffices to declare a type with a single mutable field `value`.

```ocaml
# type variable = { mutable value : int };;
type variable = { mutable value : int; }
```

We then use `x.value` to access the contents of the variable `x` and the assignment `x.value <- e` to modify it.

```ocaml
# let x = { value = 41 };;
val x : variable = {value = 41}
# x.value <- x.value + 1;;
- : unit = ()
# x.value;;
- : int = 42
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Strictly speaking, we are not modifying the variable `x`. We modify only the value contained in the record that `x` points to. So, more precisely, it is the notion of pointer that is being used here.

To avoid having to define such a type each time we need a mutable variable, OCaml offers the predefined type of *references*, that we have already used (see section 2.2 *Approximation of π*). A reference is created using the keyword `ref`.

```ocaml
# let x = ref 41;;
val x : int ref = {contents = 41}
```

As is clear, the type of a reference, written as `int ref`, is that of a record, with a single field `contents`. We access this field using the notation `!` and modify its contents using the notation `:=`.

```ocaml
# x := !x + 1;;
- : unit = ()
# !x;;
- : int = 42
```

### Evaluation Order

The OCaml language does not specify the evaluation order of the components of *n*-tuples and records. Thus, in the pair `(e1, e2)`, it is not possible to know a *priori* if the expression `e1` will be evaluated before `e2` or the other way around.

Of course, we can easily figure out the evaluation order of a specific implementation of OCaml using an expression that creates a pair, as follows:

```ocaml
# (read_int (), read_int ());
4
5
- : int * int = (5, 4)
```

We can see here that it is the expression `e2` that is evaluated first, since the first integer typed in, here `4`, is stored in the second component of the pair.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
In general, it is not a good idea to write a program that relies on the evaluation order implemented by a specific compiler. It is better to use local declarations to specify the evaluation order. Thus, what we ought to write is:

```ocaml
# let x = read_int () in let y = read_int () in (x, y);;
4
5
- : int * int = (4, 5)
```

## Anonymous Functions

The definitions of anonymous functions are not limited to one argument. Functions that take several arguments may be defined as follows:

```ocaml
# fun x y -> x + y;;
- : int -> int -> int = <fun>
```

It is interesting to note that the following two declarations are strictly equivalent:

```ocaml
# let f = fun x -> x + 1;;
val f : int -> int = <fun>
# let f x = x + 1;;
val f : int -> int = <fun>
```

## 2.7 Copying a File

<figure><img src="image_20.png" /></figure>

### Ideas introduced

* input/output

* exceptions

Our next program, `copy_file.ml`, copies the contents of one file into another, with the names of the two files passed on the command line.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
For this, we write a function `copy_file` that takes as arguments the names of the files, as strings `f1` and `f2`. We begin by opening channels `c1` and `c2` on the files `f1` and `f2`, respectively.

```python
let copy_file f1 f2 =
    let c1 = open_in f1 in
    let c2 = open_out f2 in
```

The first, `c1`, is opened for reading and the second, `c2`, for writing.

Then, we execute an infinite loop, (`while true`), which reads characters from `c1` and writes them to `c2`.

```python
while true do output_char c2 (input_char c1) done
```

When there are no more characters left to read, the function `input_char` raises a predefined *exception*, namely, `End_of_file`. This interrupts the execution of the `while` loop and, more generally, of the program being executed, until the exception is *caught*. Here, we catch this exception just outside the `while` loop. We do this with the construction `try-with`.

```python
let () =
    try
        while true do ... done
        with End_of_file ->
            close_in c1; close_out c2
```

The meaning of the construction `try e₁ with E -> e₂` is as follows: We begin by evaluating the expression `e₁`. If a value is obtained, it is the value of the entire `try-with` expression. If, however, the evaluation of `e₁` raises the exception `E`, then we evaluate the expression `e₂`, and that is the result of the expression as a whole. Finally, if `e₁` raises an exception other than `E`, then the exception is not caught, and it is the expression `try-with` as a whole that raises it.

In our case, the expression `e₁` is an infinite loop, whose evaluation will never end. However, it ends by raising the exception `End_of_file`, which is then caught, and the two files `c1` and `c2` are closed.

All that remains then is to call the function `copy_file` with the first two arguments of the command line, namely, `Sys.argv.(1)` and `Sys.argv.(2)`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 7 [copy_file.ml] — Copying a file

```ocaml
let copy_file f1 f2 =
  let c1 = open_in f1 in
  let c2 = open_out f2 in
  try
    while true do output_char c2 (input_char c1) done
  with End_of_file ->
    close_in c1; close_out c2

let () = copy_file Sys.argv.(1) Sys.argv.(2)
```

## Additional Information

### Input/Output Channels

Input/output devices are represented by *channels*. Input channels are of the pre-defined type `in_channel`, and output channels of the type `out_channel`. Three predefined values represent, respectively, standard input, standard output, and standard error of the program being executed: `stdin` of type `in_channel`, and `stdout` and `stderr` of type `out_channel`.

Functions are available for reading and writing on channels. The function `input_char`, of type `in_channel -> char`, reads a single character from the channel passed as argument. We can thus read a character from standard input, `stdin`, in the following manner:

```ocaml
# let c = input_char stdin;

a
val c : char = 'a'
```

A more general function, `input`, can be used to read `n` characters from an input channel and store them at a certain position within a string.

Similarly, the `output_char` function, of type `out_channel -> char -> unit`, writes a character to an output channel. A more general function, `output`, writes

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
a given substring. There is also a function `Format.fprintf` that writes to an output channel, in a manner analogous to the function `Formatprintf` that we used earlier.

Files can also be manipulated as channels. Thus, a file is opened for reading with the function `open_in`, of type `string -> in_channel`, and for writing with the function `open_out`, of type `string -> out_channel`. The string designates the file name. Symmetrically, we close a channel with the functions `close_in` and `close_out`. Input/output operations on channels can fail (reading or writing on a closed channel, invalid permissions, etc.). This is systematically signalled by raising an exception. For instance, reading beyond the end of a file raises the predefined exception `End_of_file`.

## Marshalling

Besides characters, it is possible to use channels to read and write OCaml values of arbitrary types. This is known as *marshalling*. The function `output_value` writes a value of an arbitrary type to an output channel.

```hml
# let c = open_out "foo" in
  output_value c (1, 3.14, true);
  close_out c;
- : unit = ()
```

The format used is specific to OCaml (and even to its version). The function that performs the inverse operation is `input_value`. When you read a marshalled value with the function `input_value`, its type is *inferred* according to how it is used. It is good practice to indicate the type of the value that is read with a type annotation. Below, we read back the value written to the file `"foo"`, specifying that its type is `int * float * bool`:

```hml
# let c = open_in "foo";;
  val c : in_channel = <abstr>
# let v : int * float * bool = input_value c;
  val v : int * float * bool = (1, 3.14, true)
```

There is no type information in the marshalled value itself. In particular, runtime type safety is not guaranteed if we use a marshalled value in a way that

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
is incompatible with the type of the value that was actually marshalled. In
the above example, we could pretend that the value read is a pair whose first
component is also a pair. This leads to a fatal program error.

```ocaml
# let c = open_in "foo";;
val c : in_channel = <abstr>
# let v = input_value c in fst (fst v);;

Process caml-t LEVEL segmentation fault
```

This error is not an exception that we could have caught. It is, rather, a
lower-level error corresponding to an unrecoverable illegal memory access.

## Exceptions

Certain operations are partial, that is, they are not defined for all possible values
of their arguments. For instance, integer division by zero is not defined. If you
try, nevertheless, to perform this operation, an *exception is raised*.

```ocaml
# 1/0;;
Exception: Division_by_zero.
```

The evaluation of the expression does not result in a value; it fails when the
exception is raised, as the message beginning with *Exception* indicates. Here,
*Division_by_zero* is a predefined exception. Another predefined exception in
OCaml, *Invalid_argument*, is often used to signal the use of a function outside
its domain of definition.

```ocaml
# Random.int (-4);;
Exception: Invalid_argument "Random.int".
# Char.chr 257;;
Exception: Invalid_argument "Char.chr".
```

As is clear from these examples, a string is associated with the exception
*Invalid_argument*, which specifies the name of the function that raised the
exception.

Raising an exception *interrupts* the calculation, as we can see by evaluating
the following expression.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```pascal
# print_endline "before"; print_int (1/0); print_endline "after";;
before
Exception: Division_by_zero.
```

It is, nonetheless, possible to catch an exception, so as to continue the evaluation with another expression. You use the construction `try with` for this, as follows:

```pascal
# let test x y =
  try let q = x / y in Printfprintf "quotient = %d\n" q
  with Division_by_zero -> Printfprintf "error\n";;
val test : int -> int -> unit = <fun>
# test 4 0;
error
- : unit = ()
```

Here, we attempt to calculate `x / y` and display its value. In case of failure, that is, when the division triggers the exception `Division_by_zero`, we catch the exception and display an error message. The evaluation of the function `test` therefore always ends with a value of type `unit`.

In general, the expression `try e₁ with E -> e₂` is evaluated as follows:

* The expression `e₁` is evaluated first. If it does not raise an exception, the calculation is complete, and its value is that of `e₁`.

* If, however, the expression raises an exception, then there are two possibilities:

- if the exception is `E`, then evaluation continues with `e₂`;

- if the exception is something other than `E`, then it is *propagated*, without evaluating `e₂`.

In the expression `try e₁ with E -> e₂`, the two sub-expressions `e₁` and `e₂` must have the same type, which is also the type of the expression as a whole.

Users may define their own exceptions with the declaration `exception` followed by the exception's name, which must begin with a capital letter. The exception need not take any arguments, for example, `Division_by_zero`:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```ocaml
# exception Stop;;
exception Stop
```

Alternatively, the exception may have one or more arguments, for example, `Invalid_argument`:

```ocaml
# exception Error of string;;
exception Error of string
```

To raise an exception, you use the construction `raise`. This construction takes an exception as argument.

```ocaml
# let f x =
    if x < 0 then raise (Error "negative argument");
    123 mod x;;
val f : int -> int = <fun>
```

Here, the exception is constructed by applying the constructor `Error` to the string `"negative argument"`. You can observe the exception being raised by calling `f` with a negative argument.

```ocaml
# f (-1);;
Exception: Error "negative argument".
```

Exceptions are, in fact, values like any other and belong to the predefined type `exn`. This type can be seen as a concrete type with an unbounded number of constructors. Predefined exceptions are merely predefined constructors of this type. Each `exception` declaration adds a new constructor. You can construct a value of type `exn` and pass it as an argument to `raise`:

```ocaml
# let e = Error "invalid argument";;
val e : exn = Error "invalid argument"
# raise e;;
Exception: Error "invalid argument".
```

The construction `raise` is simply a function that takes an argument of type `exn`. The expression `raise e` can take any type. In the previous example, the expression `raise (Error "invalid argument")` takes the type `unit`, but can equally take the type `int` if we wish to write the function `f` with an `else`:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```h
# let f x =
    if x < 0 then raise (Error "invalid argument") else 123 mod x;;
val f : int -> int = <fun>
```

Exceptions can be used to signal exceptional behaviors (as in the preceding examples), as well as to change the program's control flow. A typical example is that of an infinite loop that you exit using an exception. For example, this is the case of interactive programs that you exit by pressing a key. With the library `Graphics`, such a loop can be written as follows:

```h
try
  while true do
    let st = wait_next_event [Key pressed] in
    if st.keypressed && st.key = 'q' then raise Exit;
    ...
done
with Exit ->
  close_graph ();
  ...
```

Raising the exception `Exit` interrupts the infinite loop `while true`. We catch the exception, close the graphical window with `close_graph`, and then continue the program. Other examples of the use of exceptions to change the flow of control are given in exercises 2.15 and 5.7.

Finally, note that the OCaml standard library provides two functions, `failwith` and `invalid_arg`. When called with a string `s`, these raise the exceptions `Failure s` and `Invalid_argument s`, respectively. OCaml also provides a specific construction `assert e`, which evaluates an expression `e` of type `bool` and raises the exception `Assert_failure` if `e` is `false`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
## 2.8 Reversing the Order of Lines in a Text

<figure><img src="image_21.png" /></figure>

### Ideas introduced

* lists

* pattern matching

* call stack, tail call

Our next program, `tac.ml`, reads lines of text from standard input and then displays them in reverse order. It is easy to use. Having compiled the program, we execute it and enter, for example, the following three lines on standard input:

```
first line
second line
third line
```

Once we signal the end of input (for example, by pressing the keys `ctrl` and `D`), the program displays the lines in reverse order:

```
third line
second line
first line
```

To achieve this, the program must store all the lines read before it is able to display them, since the first line to be displayed is the last one to be read. We therefore need a data structure to store the lines that have been read. An array is not suitable since we do not know the total number of lines<fnref n="2" />. We will therefore use a *list*.

OCaml provides a built-in type for lists. These are constructed from the empty list, represented by `[]`, and by adding an element `x` at the front of an existing list `l`, represented as `x :: l`. Lists in OCaml are *immutable*: once a list is constructed, it is no longer possible to modify it.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —

<footnote n="2">²A resizeable array could also be used here. This notion will be presented in chapter 4.</footnote>
Program 8 [tac.m1] — Reversing the Order of Lines in a Text

```perl
let lines = ref []

let () =
    try
        while true do lines := read_line () :: !lines done
        with End_of_file ->
        ()

let rec print l =
    match l with
    | []      -> ()
    | s :: r  -> print_endline s; print r

let () = print !lines
```
Our program begins by introducing a reference, `lines`, that will contain the list of lines that have been read. Initially, this list is empty.

```ocaml
let lines = ref []
```

We then proceed to read the lines, using the library function `read_line`, which reads a line of text from standard input and returns it as a string. To read all the lines, we write an infinite loop:

```ocaml
while true do lines := read_line () :: !lines done
```

Each line read using `read_line` is added to the list contained in the reference `lines`. More precisely, we construct a new list whose first element is the most recently read line, followed by the elements already present in `lines`, that is, `!lines`. Next, we set the value of the reference `lines` to this new list. When there are no more lines to be read, the function `read_line` raises the exception `End_of_file`.

We catch this exception just outside the loop:

```ocaml
try while true do ... done
with End_of_file -> ()
```

With this, we are done with the reading. The reference `lines` now contains the list of all the lines read. By construction, this list is in reverse order, the most recently read line having been added at the head of the list. This is convenient since this is precisely the order in which we wish to display the lines. To display the lines, we begin by writing a recursive function `print`, which displays a list of strings, one per line.

```ocaml
let rec print 1 =
```

This function examines the list `1`, treating the case of an empty list and that of a list containing at least one element separately. We discriminate between the two cases using the OCaml construct `match-with`, as follows:

```ocaml
match 1 with
| []    -> ...case 1...
| s :: r -> ...case 2...
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
This pattern matching construct is read as follows: If the list `l` is of the form `[]`, that is, if it is the empty list, then we evaluate the code denoted above by `...case 1...`. If, however, the list `l` is of the form `s :: r`, that is, if it contains a first element `s` and is followed by other elements forming a list `r`, then we evaluate the code denoted above by `...case 2...`. Here, the variables `s` and `r` take the value of the first element and the rest of the elements of `l`. In the function `print`, we do nothing in the first case. In the second case, we display the string `s` and then call `print` recursively on the list `r`. Therefore, the body of the function `print` is:

```hml
match l with
| [] -> ()
| s :: r -> print_endline s; print r
```

All that remains to complete our program is to apply this function to the list contained in the reference `lines`, that is:

```hml
let () = print !lines
```

## Additional Information

### Lists

The type of lists is predefined in OCaml; it is `list`. This type is "generic," in the sense that we can construct lists of values of any type at all, provided that all the elements of a given list are of the same type.

```hml
# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]
```

```hml
# 1 :: 'a' :: 3 :: [];;
Error: This expression has type char but an expression
       was expected of type int
```

As we see in the first example, the toplevel displays a list in the form `[1; 2; 3]`. This notation can also be used to construct a list given its elements.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```ocaml
# ['a'; 'b'; 'c'];;
- : char list = ['a'; 'b'; 'c']
```

## Pattern Matching

When we presented *n*-tuples, we explained that pairs can be destructured using the construction `let (x,y) = e₁ in e₂`. In fact, that pattern matching is identical in every way to the one we discussed above in relation to lists. The construction `let` is merely a shorthand for the expression `match e₁ with (x,y) -> e₂`. In general, the construct `let` may be used with an arbitrary pattern as its first argument, even if the latter is often reduced to a variable.

The function `print` proceeds by pattern matching on its argument `l`. Such functions are so common in OCaml that there is a keyword, `function`, which introduces a function that proceeds by pattern matching on its argument. Thus, we may write:

```ocaml
let rec print = function
| []      -> ()
| s :: r  -> print_endline s; print r
```

In other words, the keyword `function` is a shorthand for `fun x -> match x with`. Note also that `function` introduces a function with only *one* argument, where the pattern matching may have one or more patterns. By contrast, `fun` defines a function with several arguments, where each argument is matched by a *single* pattern. Thus, we may write:

```fun
fun x (y, z) -> x + y * z
```

## List Traversals

The function `print` that we wrote to display all the elements of the list `!lines` is an example of a list *traversal*, where all the elements of the list are treated the same way, in the order in which they appear. Such traversals are so frequent that a library function exists for them, namely, `List.iter`. This is a higher-order function, like `Array.init` or `Array.sort`, which we presented earlier.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
`List.iter` takes as argument the function to be applied to each element. Thus, we can rewrite `print` quite simply as:

```python
let print 1 = List.iter print_endline 1
```

We can even replace the last five lines by:

```python
let () = List.iter print_endline !lines
```

### Call Stack

Suppose we want our program to display the total number of lines that have been read and reversed, in a message of the form:

113 lines read

For this, we write a function `length` that calculates the length of a list. As with `print`, we write it in the form of a recursive function that proceeds by pattern matching:

```python
let rec length = function
  | []      -> 0
  | _:: r   -> 1 + length r
```

Note the wildcard pattern `_` used in place of the first element of the list in the second pattern. This value does not need to be named because it is not used in the calculation of the length of the list. All that remains now is to display the length thus calculated:

```python
let () = Printfprintf "%d lines read\n" (length !lines)
```

If we run the program several times, we would observe that it does indeed give the expected result. However, if we were to attempt feeding the program a very large number of lines—say, 700,000 lines—we would be in for a nasty surprise: The program would give us an error<fnref n="3" /> even though everything worked just fine up until the point where we tried to display the number of lines:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —

<footnote n="3">³The program `seq` is a Unix tool that displays all the integers from 1 to `n`, one integer per line. It is the simplest way to obtain exactly `n` lines of text.</footnote>
```
seq 700000 | ./tac
Fatal error: exception Stack_overflow
```

To explain this phenomenon, it is necessary to understand the principle behind the execution of a recursive function like `length`.

Consider as an example the execution of the call `length [1; 2; 3]`. We can “symbolically” unroll this call as follows:

```
length [1; 2; 3] = 1 + length [2; 3]
               = 1 + (1 + length [3])
               = 1 + (1 + (1 + length []))
               = 1 + (1 + (1 + 0))
               = 1 + (1 + 1)
               = 1 + 2
               = 3
```

Each call to `length` allocates a memory cell to store the function's argument. In general, a function call, whether recursive or not, allocates the memory space necessary for its arguments and its local variables. This memory space is freed once the function call ends. In case of the recursive function `length`, the call does not end until the recursive call completes and the addition `1 + ...` is performed. In particular, the call `length [1; 2; 3]` will require up to four nested function calls to reach the final call `length []`. Thus, four memory cells will be needed to store the arguments of each of the four calls, as represented in figure 2.6.

<figure><img src="image_22.png" /><figcaption>Figure 2.6: Representation of a call stack.</figcaption></figure>

As is clear in the diagram, the nesting of function calls allows us to organize the memory required for them as a *stack*. Hence the term *call stack*. Each call

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
to a function pushes the memory space required for its variables (here, the single variable `1`) onto the call stack, and removes this space when the call ends.

The error `Stack_overflow` triggered earlier when calculating the length of a list of 700,000 elements is due to a limit on the size of the call stack. This limit depends on the operating system and the compiler. It is generally fairly low, of the order of several MB. When the stack reaches this limit, we call it a *stack overflow*. The program is then interrupted. This is signaled either by the exception `Stack_overflow` in OCaml or by a fatal crash of the program. If, on the other hand, the size of the stack is large (or even unlimited), the program will not trigger a stack overflow, but will consume more and more memory, which could eventually cause the machine to crash.

## Tail Calls

You may wonder why the call `print !lines` does not provoke a stack overflow, unlike `length !lines`. The difference between the two functions is that, in the function `print`, the recursive call is the very last expression evaluated in the body of the function. This is not the case in the function `length`, where an addition remains to be performed after the recursive call. In the case of `print`, the compiler performs an *optimization*, which consists in removing the current call from the call stack, before performing the recursive call. Thus, the call stack only ever contains the final call to `print` and, therefore, does not increase in size.

In general, when a function call is the last expression to be evaluated in the body of a function, we say it is a *tail call*. Note that this notion applies to both recursive and non-recursive functions. In the former case, if every recursive call is a tail call, the function is said to be *tail recursive*. Thus, `print` is tail recursive and `length` is not. Note that a recursive function can contain both tail calls and non-tail calls. This is the case of McCarthy's famous 91 function.

```
let rec f91 n =
    if n > 100 then n - 10 else f91 (f91 (n + 11))
```

We can avoid the stack overflow in the function `length` by writing it differently, using an additional argument that represents the number of elements

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
already traversed. Thus, we can write:

```ocaml
let rec length_term acc = function
| []      -> acc
| _ :: r -> length_term (1 + acc) r
```

In this version, the recursive call to `length_term` is a tail call. To calculate the length of a list, it suffices to call `length_term` with 0 as the first argument.

```ocaml
let length l = length_term 0 l
```

We can even define the function `length` as the result of the partial application of `length_term` to 0.

```ocaml
let length = length_term 0
```

## 2.9 Converting Integers from an Arbitrary Base

<figure><img src="image_23.png" /></figure>

### Ideas introduced

* iterators

* polymorphism

* function `exit`

Our next program (see page 76), `radix.ml`, takes numbers written in some base $B$, where $2 \le B \le 36$, and converts them to base 10. The base is passed on the command line. The program then reads numbers from standard input and displays them in base 10.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Here is a first example in base 16:

```
> radix 16
7FFF
-> 32767
A0
-> 160
```

After launching the program with the given base, we enter the number `7FFF` on standard input, and the program displays the result of the conversion, namely `32767`. Next, we enter the number `A0` and obtain `160`.

Here is a second example, with numbers written in base 36:

```
> radix 36
ZORRO
-> 59942292
```

As you see in these examples, the numbers are written using the characters `0` to `9`, and `A` (for 10) to `Z` (for 35).

Let us now pass to the implementation of the program. To begin, we retrieve the base from the command line and store it in a variable `base`.

```
let base = int_of_string Sys.argv.(1)
```

It is good practice to verify that the integer does indeed lie between 2 and 36, and to fail otherwise.

We continue by defining a function, `list_of_string`, which converts a string (of type `string`) to a list of characters (of type `char list`).

```
let list_of_string s =
    let digits = ref [] in
    for i = 0 to String.length s - 1 do
        digits := s.[i] :: !digits
    done;
    !digits
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 9 [radix.ml] — Converting Integers from an Arbitrary Base

``` Ocaml
let base = int_of_string Sys.argv.(1)

let list_of_string s =
  let digits = ref [] in
  for i = 0 to String.length s - 1 do
    digits := s.[i] :: !digits
  done;
  !digits

let digit_of_char c =
  match c with
  | '0'..'9' -> Char.code c - Char.code '0'
  | 'A'..'Z' -> 10 + Char.code c - Char.code 'A'
  | c -> Printf.eprintf "invalid character %c\n" c; exit 1

let checkgli d =
  if d < 0 || d >= base then begin
    Printf.eprintf "invalid digit %d\n" d; exit 1
  end

let () =
  while true do
    let s = read_line () in
    let cl = list_of_string s in
    let dl = List.map digit_of_char cl in
    List.iter checkgli dl;
    let v = List.fold_right (fun d acc -> d + base * acc) dl 0 in
    Printfprintf " -> %d\n" v
  done
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
We traverse the string `s`, beginning with its first character, so as to construct a list in which the last character of `s`—that is, the least significant digit of the number—is found at the head of the list.

Next, we write a function `digit_of_char` to convert a character representing a digit into the corresponding integer.

```python
let digit_of_char c =
    match c with
        | '0'..'9' -> Char.code c - Char.code '0'
        | 'A'..'Z' -> 10 + Char.code c - Char.code 'A'
        | c -> Printf.eprintf "invalid character %c\n" c; exit 1
```

The first pattern matching case `| '0'..'9' ->` treats the case of a character `c` between '0' and '9'. Its numeric value is obtained simply as the difference between the ASCII code of `c` and that of the character '0'. The second case proceeds in the same manner, for the characters between 'A' and 'Z'. For all other characters, the last case displays a message on standard error using `Printf.eprintf` and terminates the program using the predefined function `exit`.

We then write a function `checkambig` that verifies that `d` is a valid digit for the given base, that is, that it lies between 0 and `base - 1`.

```python
let checkambig d =
    if d < 0 || d >= base then begin
        Printf.eprintf "invalid digit %d\n" d; exit 1
    end
```

This function does not return a result. It interrupts the program if the digit `d` is not valid.

The main part of the program is an infinite loop that reads a string `s` from standard input and converts the corresponding number to base 10.

```python
let () =
    while true do
        let s = read_line () in
        ...
    done
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We begin by converting the string `s` into a list of characters `cl` using the function `list_of_string`.

```ocaml
let cl = list_of_string s in
```

In order to convert the list `cl` into a list of digits, we apply the function `digit_of_char` to each element of `cl`. For this, we use the library function `List.map`, which constructs a new list by applying a given function to all the elements of a list.

```ocaml
let dl = List.map digit_of_char cl in
```

For example, if `cl` is the list `['A'; '0']`, then `dl` is the list `[10; 0]`. More generally, given a function `f` and a list `l` `[e₁; e₂; ... ; eₙ]`, we have:

```hl
List.map f l = [f e₁; f e₂; ... ; f eₙ]
```

We then verify that each digit of the list `dl` is valid by applying the function `checkظه` successively to each element of `dl`.

```hl
List.iter check instability dl;
```

In this case we do not wish to construct a new list but rather to apply `check instability`. The whole program will be interrupted if `check instability` detects an invalid digit. In general, given a function `f` and a list `l` equal to `[e₁; e₂; ... ; eₙ]`, the application `List.iter f l` is equivalent to the following sequence:

```hl
List.iter f l = f e₁; f e₂; ... ; f eₙ
```

Finally, we will calculate the base 10 notation and display it. The list `dl` is of the form `[d₀; d₁; ... ; dₙ₋₁]`, where `d₀` is the digit corresponding to the last character in the string, that is, the least significant digit. It is therefore necessary to calculate the following value:

$$ \sum_{i=0}^{n-1} d_i \times \text{base}^i $$

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
The most efficient method to minimize the number of multiplications (in particular to avoid the expensive calculation of `base`<sup>i</sup>) is Horner's rule, which rewrites the preceding sum as follows:

$$d_0 + \mathbf{base} \times (d_1 + \mathbf{base} \times (\dots (d_{n-2} + \mathbf{base} \times (d_{n-1} + \mathbf{base} \times 0))\dots))$$

We can easily program the above using the library function `List.fold_right`, which allows us to traverse the list `dl` from the last element `d<sub>n-1</sub>` to the first element `d<sub>0</sub>`, applying a function `f` to each element as follows:

$$\text{List.fold\_right } f \text{ l acc} = f d_0 (\dots (f d_{n-2} (f d_{n-1} acc)\dots))$$

The value computed for each element of the list is systematically passed to the function `f` as the second argument, called the *accumulator*. Its initial value, used when calling `f` on the last element `d<sub>n-1</sub>` of the list, is the third argument of `List.fold_right`, here called `acc`. To obtain Horner's formula, it suffices to let `f` be the function `fun d acc -> d + base * acc`. Thus, the end of the program is simply:

```hkl
let v = List.fold_right (fun d acc -> d + base * acc) dl 0 in
    Printf printf " -> %d\n" v
```

### Additional Information

#### Polymorphism

To be useful, the functions of the library `List`, such as `iter`, `map`, or `fold_right`, must be generic with respect to both the type of the elements of the list to which they are applied, and the operation performed on them. This genericity is called *polymorphism*. The notion may be illustrated using the function `length` to calculate the length of a list:

```hkl
let rec length l =
    match l with
    | []         -> 0
    | _ :: r    -> 1 + length r
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
This function may, of course, be applied to a list of integers. For example:

```ocaml
# length [1; 6; 2; 8; 3] ;;
- : int = 5
```

However, this function does not directly use the elements of the list `1` passed as argument (as indicated by the pattern matching `_ :: r`). Therefore, this function may in fact be applied to any list, be it a list of strings or one of floating-point numbers. For example:

```ocaml
# length ["hello"; "world"; "!"] ;;
- : int = 3
# length [ [3.4; .2]; []; [1.2]; [5.]] ;;
- : int = 4
```

For the above to be possible, the function `length` must accept arguments of type `int list`, `string list`, and even `float list list`. This function is, in fact, applicable to lists of any type. In OCaml, it is given the type:

```hkl
'a list -> int
```

where the type variable `'a` represents any type. A type such as that of `length`, which contains at least one type variable, is said to be *polymorphic*.

Apart from representing any type, type variables are also useful in establishing relations between the generic parts of a polymorphic type. For example, in the function `f`, defined by `let f g x = (g x) + 1`, the types of the arguments `g` and `x` must be related because the function `g` is applied to `x`. Nevertheless, `x` (and hence `g`) remains polymorphic, because there is no other type constraint involving this value in the body of `f`. Thus, in the type of `f`, that is, (`'a -> int` ) -> ` 'a -> int`, the variable `'a` relates the type of the argument of `g` with the type of `x`, without adding any extra constraints. Similarly, the function `iter` of the library `List` has a polymorphic type:

```hkl
iter : ('a -> unit) -> 'a list -> unit
```

This relates the type of the function passed as argument to that of the elements of the list that the function iterates over.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
A polymorphic type can contain several type variables, to represent unrelated generic types. Thus, consider the function `make_pair`, defined by:

```h
let make_pair x y = (x, y)
```

Here, the arguments `x` and `y` may be of any type, and they need not be related. Hence this function has a polymorphic type with two variables, that is, `'a -> 'b -> 'a * 'b`.

In the same way, the functions `map` and `fold_right` of the library `List` have the following polymorphic types:

```h
map : ('a -> 'b) -> 'a list -> 'b list
fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
```

These types are the most general possible.

### Right-to-Left and Left-to-Right Iterators on Lists

Combining higher-order functions and polymorphic types allows us to define *iterators*, that is, functions that traverse generic data structures, such as lists.

For example, the iterator `fold_right` used in the program `radix.ml` can be defined as follows:

```h
# let rec fold_right f l e =
match l with
| [] -> e
| x :: r -> f x (fold_right f r e);;
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
```

As we have seen in the program `radix.ml`, the use of such an iterator allows us to avoid writing recursive functions. Suppose, for example, that we wish to multiply all the elements of a list of floats. We can simply write a function `mult` as follows:

```h
# let sum l = fold_right (fun x y -> x *. y) l 1. ;;
val mult : float list -> float = <fun>
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
The reason for calling this iterator `fold_right` is that it treats the elements of the list from right to left. The list is, in fact, traversed from left to right, but the recursive call is performed *before* applying the function passed as argument. This means that the rest of the list is treated before its first element. We can confirm this behaviour by applying `fold_right` to a function that prints its first argument:

```ocaml
# fold_right (fun x () -> print_int x) [1;2;3;4] ();;
4321- : unit = ()
```

It is natural at this point to consider the other iterator, which traverses and treats elements from left to right. It is naturally called `fold_left` and is written as follows:

```ocaml
# let rec fold_left f e = function
| [] -> e
| x :: r -> fold_left f (f e x) r;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
```

It is clear that the elements are effectively treated from left to right:

```ocaml
# fold_left (fun () x -> print_int x) () [1;2;3;4];;
1234- : unit = ()
```

We can write the function `mult` with `fold_left` as we did with `fold_right`:

```ocaml
# let mult l = fold_left (fun x y -> x *. y) 1. l ;;
val mult : float list -> float
```

There is, nevertheless, a slight difference. On a list containing hundreds of thousands of elements, the function `mult` written with `fold_right` may trigger a stack overflow, which results either in an exception `Stack_overflow` or in the sudden halt of the program. This is because the recursive call to `fold_right` is not a tail call. (Since the call must be carried out before performing the operation, it is necessary to save the value of the first element of the list.) By contrast, in the case of `fold_left`, the recursive call is a tail call. (The stack is not needed since the value `x` is used before the recursive call to `fold_left`).

It is important to note that an iterator like `fold_left` or `fold_right` traverses *all* the elements of the list passed as argument. If we wish to stop the

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
calculation at a specific element, we have at least two possibilities<fnref n="4" />: Either we write a recursive function that traverses the list and stops when we want it to. Alternatively, we can use an iterator and raise an exception to interrupt the list traversal. Consider again the example of the function `mult`. We may wish to stop the calculation when the value 0 is encountered. The version with the exception may be written as follows:

```python
let mult l =
    try
        List.fold_left
        (fun x y -> if y = 0. then raise Exit else x *. y) 1. l
    with Exit -> 0.
```

However, in this case, writing a recursive function that terminates when it encounters 0 is simpler and more elegant.

## 2.10 Breakout without Bricks

<figure><img src="image_24.png" /></figure>

### Ideas introduced

* compilation unit, separate compilation

* module, interface

Our tenth program (see page 86) is a simplified version of the game Breakout, without the bricks. The game consists in making a ball bounce within a frame, by means of a paddle that is controlled using the mouse.

Graphically, the game window is as shown in figure 2.7, represented by a gray frame, with a black circle representing the ball, and a black rectangle at the base of the game window representing the paddle.

Programming such a game involves three main ingredients. First, we must define the *constants* of the game, that is, the dimensions of the window (its height and width, in pixels), the dimensions of the ball (that is, the radius of the circle), and the paddle (the height and width of the rectangle). Next, we

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —

<footnote n="4">⁴Chapter 9 will present another type of iterator which can solve this problem.</footnote>
<figure><img src="image_25.png" /><figcaption>Figure 2.7: Breakout without bricks.</figcaption></figure>

must determine the *state* of the game, that is, the set of values that characterize it at any instant. Here, these are the coordinates of the center of the ball, its velocity, and the position of the paddle, which can be specified by the coordinates of its bottom-left corner. To simplify matters, we may use the same coordinate system as that of the library *Graphics*. That is, the point with coordinates (0,0) is located at the bottom left of the window, and the *x*- and *y*-axes are respectively the window's bottom and left edges. Finally, the game is played using an algorithm that executes the following steps:

1. Initialize the state of the game (the position and velocity of the ball, the position of the paddle).

2. Erase the graphical window.

3. Calculate the position of the paddle as a function of the *x*-coordinate of the mouse.

4. Display the ball and the paddle.

5. Calculate the new state of the game, that is:

* the new position of the ball, as a function of its current position and velocity vector;

* the new velocity vector of the ball, as a function of its bouncing off the sides of the window and the position of the paddle.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
6. Return to step 2.

As you can see, the actions performed in these steps are of two types: those that are purely graphical (steps 2, 3, 4) and those that manipulate the state of the game (steps 1, 5, 6). We choose to divide the OCaml code into two files: `draw.ml` and `breakout.ml`. The first contains all the constants and graphical functions of the game; the second maintains the current state and implements the algorithm. In general, to clarify the structure of larger programs, it is a good idea to divide them into several files, called compilation units.

To compile this program, which is divided into two files, we use the following command line:

```
> ocamlc -I 'ocamlfind query graphics' -o breakout graphics.cma draw.ml breakout.
```

As we will see shortly, the order of file names on the command line matters.

The graphical part (file `draw.ml`, program 2.10), begins by defining the dimensions of the game window, with the declaration of four constants: `left`, `right`, `down`, and `up`.

``` Ocaml
let left = 0.
let right = 300.
let down = 0.
let up = 200.
```

These constants are values of type `float`, as we will later be using floating-point numbers in trajectory calculations so as to guarantee a high degree of precision.

The following three constants define respectively the radius of the ball, the length of the paddle, and its width (in pixels).

``` Ocaml
let ball = 5
let paddle = 50
let thick = 8
```

Finally, we declare a color `gray`, obtained by specifying the values of its three components—red, green, and blue—using the function `rgb`.

``` Ocaml
let gray = rgb 240 240 240
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Program 10 [draw.ml] — Breakout without Bricks (1/2)

```ocaml
open Graphics

let left = 0.
let right = 300.
let down = 0.
let up = 200.

let ball = 5
let paddle = 50
let thick = 8

let gray = rgb 220 220 220

let init () =
  let s = Printf.sprintf "%dx%d" (truncate right) (truncate up) in
  open_graph s;
  auto_synchronize false

let clear () =
  set_color gray;
  fill_rect 0 0 (truncate right) (truncate up)

let get_paddle_pos () =
  let x = fst (mouse_pos()) in
  max 0 (min x (truncate right - paddle))

let game x y =
  clear ();
  set_color black;
  fill_circle (truncate x) (truncate y) ball;
  let x = get_paddle_pos () in
  fillRect x 0 paddle thick;
  synchronize ();
  x
  -- openly licensed via CC BY SA 4.0 --
```
The function `init` initializes the game window by opening a graphical canvas of dimensions `right` × `up`.

```python
let init () =
    let s = Printf.sprintf "%dx%d" (truncate right) (truncate up) in
    open_graph s;
    auto_synchronize false
```

Since the constants `right` and `up` are values of type `float`, we use the predefined function `truncate` from the standard library to truncate their values and convert them into integers. The call `auto_synchronize false` activates the *double buffering* mode of the graphical device. When this mode is activated, all display operations (drawing a circle, a rectangle, etc.) are performed in a memory zone called the *backing store*, and not directly on the screen. The function `synchronize` must then be used explicitly to copy the contents of the backing store to the screen. As this copy is instantaneous, it eliminates any “flickering” effects during the animation.

We now write a function for each graphical step of the algorithm. Step 2 is implemented by a function `clear` that erases the canvas by drawing a gray rectangle of the same dimensions as the graphical window.

```python
let clear () =
    set_color gray;
    fill_rect 0 0 (truncate right) (truncate up)
```

Step 3 of the algorithm is implemented by a function `get_paddle_pos`. It begins by retrieving the x-coordinate of the current position of the mouse (with the function `mouse_pos`). To ensure that the paddle does not go outside the game window on the right side, we take the minimum between the value obtained and `truncate right - paddle`.

```python
let get_paddle_pos () =
    let x = fst (mouse_pos()) in
    max 0 (min x (truncate right - paddle))
```

The main graphical function, `game`, takes as arguments the x- and y-coordinates of the ball and implements steps 2, 3, and 4 of the algorithm.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```ocaml
let game x y =
    clear ();
    set_color black;
    fill_circle (truncate x) (truncate y) ball;
    let x = get_paddle_pos () in
    fillRect x 0 paddle thick;
    synchronize ();
    x
```

The second file, `breakout.ml` (see page 90), implements steps 1, 5, and 6 of the algorithm. The state of the game is encoded as two pairs of floating-point numbers: `(x, y)` and `(vx, vy)`, which represent respectively the coordinates of the ball and its velocity.

The first function of this file, `bounce`, calculates the new velocity of the ball, taking into account that the ball may bounce off the sides of the window or the paddle. The function `bounce` therefore also takes the position `xp` of the paddle as an argument.

```ocaml
let bounce (x, y) (vx, vy) xp =
...
```

To calculate the new component `vx`, the `x`-coordinate of the ball must be compared with the left and right edges of the game window. The constants `left` and `right` having been defined in the file `draw.ml`, the dot notation `Draw.left` and `Draw.right` must be used to refer to them. Each compilation unit effectively defines a module bearing the same name as the file, but with the first letter in upper case.

```ocaml
let vx =
    if x <= Draw.left || x >= Draw.right then -. vx else vx in
```

In the same way, to calculate the new component `vy`, we must compare the `y`-coordinate of the ball with the top of the window `Draw.up`. The direction of the ball's velocity also changes if the ball hits the paddle, that is, if the `x`-coordinate lies between `xp` and `xp + . float Draw.paddle`, and if the `y`-coordinate is less than the paddle thickness `Draw.thick`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```pascal
let vy =
  if y <= float Draw.thick && x >= xp &&
     x <= xp +. float Draw.paddle || y >= Draw.up
  then -. vy else vy
in
(vx, vy)
```

The following function returns the ball's new position by adding the x- and y-coordinates, respectively, to the velocity's coordinates vx and vy.

```pascal
let new_position (x, y) (vx, vy) = x +. vx, y +. vy
```

The function `play` implements the loop between steps 2 and 6. Starting from the current state of the game, passed as argument, we begin by verifying that the ball does not go beyond the bottom of the game window, by comparing the y-coordinate to the constant `Draw.down`. If the ball does so, the game ends with a call to the function `failwith` of the standard library:

```pascal
let rec play (x, y) (vx, vy) =
  if y <= Draw.down then failwith "game over";
```

If the game has not ended, we display the ball and the paddle using the function `Draw game`, which returns the x-coordinate of the paddle.

```pascal
let xp = Draw game x y in
```

Next, we calculate the new coordinates of the velocity vector, and then those of the ball.

```pascal
let vx, vy = bounce (x, y) (vx, vy) (float xp) in
let x', y' = new_position (x, y) (vx, vy) in
```

We return to step 2 by a recursive call to the function `play` with the new state of the game as argument.

```pascal
play (x', y') (vx, vy)
```

The main part of the program opens the game window by a call to `Draw.init`.

```pascal
let () =
  Draw.init();
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 11 [breakout.ml] — Breakout without Bricks (2/2)

```ocaml
let bounce (x, y) (vx, vy) xp =
    let vx =
        if x <= Draw.left || x >= Draw.right then -. vx else vx in
    let vy =
        if y <= float Draw.thick && x >= xp &&
           x <= xp +. float Draw.paddle || y >= Draw.up
        then -. vy else vy
    in
    (vx, vy)

let new_position (x, y) (vx, vy) = x +. vx, y +. vy

let rec play (x, y) (vx, vy) =
    if y <= Draw.down then begin Printf.eprintf "Game over!\n"; exit 0 end;
    let xp = Draw game x y in
    let vx, vy = bounce (x, y) (vx, vy) (float xp) in
    let x', y' = new_position (x, y) (vx, vy) in
    play (x', y') (vx, vy)

let () =
    Draw.init();
    let speed = 0.1 in
    let vx = speed *. Random.float 1. in
    let vy = speed *. Random.float 1. in
    play (Draw.right / 2., float Draw.thick) (vx, vy)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
It then creates a random velocity vector (vx, vy):

let speed = 0.1 in

let vx = speed *. Random.float 1. in

let vy = speed *. Random.float 1. in

Finally, the game begins with a call to the function `play`, placing the ball on top of the paddle and at the center of the window:

play (Draw.right / 2., float Draw.thick) (vx, vy)

## Additional Information

### Separate Compilation and Linking

The command line given above to compile Breakout can be decomposed into several commands. We can begin by compiling the file `draw.ml` alone, with the command:

> ocamlc -I 'ocamlfind query graphics' -c draw.ml

The compiler option `-c` specifies that we do not wish to construct an executable, but only to compile the code. The result consists of two files, `draw.cmi` and `draw.cmo`. The first contains typing information, and the second contains code. This code is not self-contained. In particular, it references functions from the module `Graphics`, which are not included in this file.

We can then compile the second file, with a similar command.

> ocamlc -c breakout.ml

Since this file references the module `Draw`, we had to compile the file `draw.ml` first. The information needed for the type-checking of `breakout.ml` is contained in the file `draw.cmi`. Here, too, the code obtained is not self-contained; the file `breakout.cmo` references values and functions of the module `Draw` that are contained in `draw.cmo`.

To obtain an executable, we must perform a *linking* operation, which consists in putting together several pieces of code while verifying that every reference

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
can be resolved. Here, the three pieces involved are those of the OCaml li-
brary graphics.cma (which groups a set of cmo files together) and the two files,
draw.cmo and breakout.cmo.

> ocamlc -I 'ocamlfind query graphics' -o breakout graphics.cma draw.cmo br

As we explained above, the order of file names on this command line is sig-
nificant. In particular, it must be compatible with the dependencies between
compilation units. Here, breakout.cmo depends on draw.cmo, which itself de-
pends on graphics.cma. Furthermore, it must be understood that an OCaml
program does not have a specific entry point. The code obtained after linking
simply executes the code of the different files passed on the command line, in
the order in which they appear.

Interfaces

The file draw.cmi produced by compilation contains the typing information of
all the values defined in the file draw.ml. This same information can be obtained
using the compiler option -i.

> ocamlc -I 'ocamlfind query graphics' -i draw.ml
val left : float
val right : float
...
val game : float -> float -> int

We may, however, wish to make some of these values inaccessible to the rest of
the program. For example, we may wish to hide the function *clear*. To this end,
we can define an *interface* for *draw.ml*, in the form of a file *draw.mli*. Such a
file is given in program 2.10. We write it using the same syntax as that used by
the compiler option -i. We compile *draw.mli* before compiling *draw.ml*.

> ocamlc -c draw.mli
> ocamlc -I 'ocamlfind query graphics' -c draw.ml

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 12 [draw.mli] — Interface for Module Draw

```hml
val left : float
val right : float
val down : float
val up : float

val paddle : int
val thick : int

val init : unit -> unit
val game : float -> float -> int
```

The first command produces the file `draw.cmi`. The second produces `draw.cmo` and verifies that it is compatible with `draw.cmi`, that is, that it defines values having the names and types specified in the file `draw.cmi`. When there is a file `draw.mli`, the compiler refuses to compile `draw.ml` until `draw.mli` has been compiled. If we then try to use a value in `breakout.ml` that is not mentioned in `draw.mli`, for example `clear`, an error is triggered.

```
> ocamlc -c breakout.ml
Error: Unbound value Draw.clear
```

Interfaces are not only a means of limiting the visibility of values defined in a compilation unit. They also enable *separate compilation*. This means that the code of each compilation unit may be compiled independently of the code of other units, because it depends only on their interfaces. Once `draw.mli` is compiled, we can compile either `draw.ml` or `breakout.ml`, in any order. Notably, this makes it possible to divide the work amongst several developers once the interfaces are in place. Furthermore, separate compilation helps avoid unnecessary recompilation of code. For example, a change in the code of the function `Draw.clear` would only call for recompiling `draw.ml`, and then redoing the linking operation. No other unit using `Draw` needs to be recompiled (for example,

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
breakout.ml).

## Separate Compilation with dune

To compile our program with `dune`, we write the following configuration file:

```
(executable
(name breakout)
(modules draw breakout)
(libraries graphics))
```

The line (`modules draw breakout`) lists the modules necessary for the compilation of the program. The tool `dune` will successively compile the modules `Draw` and `Breakout`, as we did manually above. In particular, if an `.mli` file exists, it is compiled before the corresponding `.ml` file. Furthermore, the line (`libraries graphics`) indicates that the files must be compiled with the library `Graphics`.

## Modules

We have used various modules thus far, including those of the standard library, like `Array` and `List`, and the modules `Draw` and `Breakout` of the preceding example. These modules always corresponded to compilation units, that is, to pairs of `.ml` and `.mli` files. The notions of module and interface are, in fact, more precise than the notion of file; they correspond to constructs of the language. Thus, we can define an interface `I` that contains a constant `a` and a function `f` with the following syntax:

```
module type I = sig
  val a: int
  val f: int -> int
end
```

We can then define a module `M` having this interface, with the following syntax:

```
module M : I = struct
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```pascal
let a = 42
let b = 3
let f x = a * x + b
end
```

The compiler then performs the same operations as if we had written the interface I in a file `m.mli` and the module M in a file `m.ml`. In particular, we access the constant `a` with the notation `M.a`, while the constant `b` is not accessible outside the module M.

## 2.11 Logo Turtle

<figure><img src="image_26.png" /></figure>

### Ideas introduced

* abstract types

* private types

* encapsulation

* functors

Our next program, `turtle.ml`, is a simplified version of the Logo turtle. Although the programming language Logo has fallen into disuse today, conceptually, it remains as interesting as ever. Its most salient feature is a turtle that can be displaced using instructions of the form "forward 3 units" or "turn right 30 degrees," and whose path is then displayed on the screen.

<figure><img src="image_27.png" /><figcaption>Figure 2.8: Example of a drawing using the Logo turtle.</figcaption></figure>

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We can thus easily trace a square by repeating the sequence “forward, then turn left 90 degrees,” or even draw figure 2.8 through several repetitions of the sequence “trace a square, then turn by 20 degrees.”

Our aim here is to implement some of the basic turtle operations, such as
moving forward, turning, and lifting the pen.

The following question arises naturally when writing the code of the turtle:
how do we represent the angle that determines the turtle’s direction?

We may choose to represent the angle in degrees or in radians, as an integer or a floating-point number, and so forth. Here, we decided not to choose amongst these options, and instead to parametrize the code by a module `A` that provides the type of angles.

We begin accordingly by creating a signature for such a module, namely:

```module type ANGLE = sig
type t
val of_degree: float -> t
val add: t -> t -> t
val cos: t -> float
val sin: t -> float
end
```

The type `t` is that of angles. It has no definition; we say it is an *abstract type*. We can, nevertheless, use it in the implementation of our turtle because we are provided with the following: a function `of_degree`, to convert an angle expressed in degrees to a value of type `t`; a function `add`, to add two angles; and, finally, `sin` and `cos` functions, to calculate the sine and cosine of an angle.

We can therefore write the Logo turtle as a module `Turtle`, parametrized by a module `A` with signature `ANGLE`. Such a module is called a *functor* and is defined thus:

```module Turtle(A: ANGLE) = struct
```

Inside the module `Turtle`, the module `A` of signature `ANGLE` is visible and may be used like any other module. For example, we can introduce a reference `angle`, containing the current direction of the turtle, using:

```let angle = ref (A.of_degree 0.)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
We can also write a function `rotate_left` to make the turtle turn `d` degrees to the left:

```python
let rotate_left d = angle := A.add !angle (A.of_degree d)
```

The complete code of the parametrized turtle is given in program 2.11 (see below). There, we find references `tx` and `ty` which keep track of the current position of the turtle, and a function `advance` to make the turtle move forward. The boolean reference `draw` indicates whether the turtle's pen is up or down, and is modified using the functions `pen_up` and `pen_down`.

To use the functor `Turtle`, we must begin by providing a specific module with interface `ANGLE`. If we choose to represent angles in radians and floating-point numbers, one such module `Angle` may be defined as follows:

```python
module Angle: ANGLE = struct
    type t = float
    let add = (+.)
    let pi_over_180 = atan 1. / . 45.
    let of_degree d = d * . pi_over_180
    let cos = Stdlib.cos
    let sin = Stdlib.sin
end
```

We then obtain a module `T` by applying the functor `Turtle` to the module `Angle`, which is written thus:

```python
module T = Turtle(Angle)
```

Finally, we can use the module `T` to trace the figure 2.8 by writing, for example:

```python
let square d =
    for k = 1 to 4 do T.Advance d; T Rotate_left 90. done
let squares d a =
    for k = 1 to truncate (360. / . a) do
        square d; T Rotate_left a
    done
let () = squares 100. 20.
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 13 [turtle.ml] — A Logo turtle

``` OCaml
module type ANGLE = sig
    type t
    val of_degree: float -> t
    val add: t -> t -> t
    val cos: t -> float
    val sin: t -> float
end

module Turtle(A: ANGLE) = struct
    let draw = ref true
    let pen_down () = draw := true
    let pen_up () = draw := false
    let angle = ref (A.of_degree 0.)
    let rotate_left d = angle := A.add !angle (A.of_degree d)
    let rotate_right d = rotate_left (-. d)

open Graphics
let tx = ref 400.
let ty = ref 300.
let () = open_graph " 800x600"; set_line_width 2;
    moveto (truncate !tx) (truncate !ty)

let advance d =
    tx := !tx +. d * . A.cos !angle;
    ty := !ty +. d * . A.sin !angle;
    if !draw then lineto (truncate !tx) (truncate !ty)
        else moveto (truncate !tx) (truncate !ty)
end
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Here, `square d` traces a square of side `d` and `squares d a`, a set of squares of side `d`, with a rotation of `a` degrees between any two successive squares.

The reason for writing the module `Turtle` as a functor, parametrized by the representation of angles, is that we can then apply it to other modules of signature `ANGLE`, and thus obtain other turtles where the angles are represented differently.

## Additional Information

### Abstract Types

In the above example, the type of angles `A.t` is an abstract type, because we do not yet know how it will be implemented. We may equally use the notion of abstract types to *hide* a concrete implementation, even when it is already known. This is what we call *encapsulation*. Suppose, for example, that we wish to define a module to manipulate integers between 0 and 30, and ensure that all the integers we use lie within this interval. We begin by defining a signature `INT31` for such a module:

```python
module type INT31 = sig
type t
val create : int -> t
val value : t -> int
end
```

This signature declares an abstract type `t`, and two functions `create` and `value`. We note that, by virtue of the abstract nature of the type `t`, a value of this type can only be constructed using the function `create`. Next, we can construct a module `Int31` with this signature.

```python
module Int31 : INT31 = struct
type t = int
let check x = if x < 0 || x > 30 then invalid_arg "Int31.create"
let create x = check x; x
let value x = x
end
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Inside this module, we give a definition to the type `t`, namely, `int`. Outside the module `Int31`, by contrast, the type `t` remains abstract, that is, we do not know that the values of type `Int31.t` are integers. In particular, we can enforce the invariant that any value of type `Int31.t` lies between 0 and 30. We would not have been able to do this if we had written `type t = int` in the interface `INT31`.

The abstract nature of type `t` is illustrated by the way in which the values are displayed by the OCaml interpreter:

```ocaml
# let x = Int31.create 7;;
x : Int31.t = <abstr>
```

Here, the value displayed for `x` is `<abstr>`, which denotes the value of an abstract type. Thus, `x` cannot be used like an integer:

```ocaml
# x + 10;;
Error: This expression has type Int31.t
but an expression was expected of type int
```

The type system therefore distinguishes the two types `Int31.t` and `int`. Nevertheless, the value of `x` (namely, the integer 7) is exactly the same as if `x` had type `int`. Using an abstract type does not introduce any extra cost at runtime. If we wish to add the value of `x` to 10, it is necessary to apply the function `Int31.value` to `x` in order to get back a value of type `int`.

```ocaml
# Int31.value x + 10;;
- : int = 17
```

## Private Types

As we have seen with the type `Int31.t`, an abstract type can be used to enforce an invariant. Let us consider the example of a module `Polar`, used to represent complex numbers in polar coordinates, with the type:

``` Ocaml
type t = { rho : float; theta : float; }
```

If we wish to enforce the invariant $0 \le \rho$ on this type, or to ensure that $0 \le \theta < 2\pi$, one solution is to define an abstract type. However, in that

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
case, we would no longer be able to access the fields `rho` and `theta` from outside
the module `Polar`, and would therefore have to provide two accessor functions:

```hsl
val rho : t -> float
val theta : t -> float
```

A more elegant solution consists in making the type `t` a *private type*. We give the module a signature in which the definition of the type `t` is qualified with *private*.

```hsl
type t = private { rho : float; theta : float; }
```

The definition of the type `t` inside the module remains unchanged. The private nature of the type `t` entails that it is no longer possible to construct a record of type `Polar.t` outside the module. Thus, if we write the expression `{ Polar.rho = 1.; Polar theta = 0. }`, the following error is triggered:

```
Error: Cannot create values of the private type Polar.t
```

However, it remains possible to construct values of this type inside the module `Polar`. We may therefore provide one—or several—functions to create values of type `t`, for example:

```hsl
val create : float -> float -> t
```

We may implement this function inside the module in a way that enforces the invariant: We may either choose to fail if the values of `rho` and `theta` do not satisfy the invariant, or normalize the values so that they do. Private types are useful because their definition is not hidden, so that the structure of their values is accessible, but the construction of these values is still disallowed. In our example, we can access the fields `rho` and `theta` with the usual notation in an expression or a pattern matching. Furthermore, it would not be possible to modify a *mutable* field of a private record. The notion of privacy is not limited to record types.

## Iterators and Abstract Types

Iterators allow the traversal of a data structure (see section 2.9 *Converting Integers from an Arbitrary Base*). In case of concrete types, such as lists, we

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
always have the option of directly defining a recursive function. By contrast,
in case of *abstract types*, this is no longer possible. It is therefore a good idea
to provide an iterator as well, in the form of a function *iter* or *fold*. If, for
example, a module *S* provides an abstract type for sets of integers—let us call
it *set*—it could also provide a function:

fold: (int -> 'a -> 'a) -> set -> 'a -> 'a

We can use this function to calculate the sum of the elements of a given set,
even though we do not know its representation.

Functors

Functors allow us to construct data structures parametrized by other data struc-
tures. The OCaml standard library contains four examples of data structures
defined as functors: **Hashtbl.Make**, **Set.Make**, **Map.Make**, and **Weak.Make**. Part
II of this book also contains numerous such examples. Functors can also help us
write algorithms parametrized by data structures or even by other algorithms
(see the various examples in Part III). In general, functors are an elegant way of
reusing code, by writing it in the most generic way possible. Despite numerous
differences, they are comparable to C++ *templates*.

2.12 Playing a Musical Score

<figure><img src="image_28.png" /></figure>

Ideas introduced

• algebraic types

• pattern matching

Our next program (see page 105), *music.ml*, plays a musical score. The
simple scores that we are going to play are represented graphically as in figure 2.9.
There are several types of *signs* here:

* Notes are determined by their pitch (or position) on the score and their duration. We are only interested in notes of two specific durations: half

— openly licensed via [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_29.png" /><figcaption>Figure 2.9: Musical score.</figcaption></figure>

notes and quarter notes. Half notes are twice as long as quarter notes.

* *Silences*, for which we similarly consider only those that have the durations of half and quarter notes.

To these signs, we add the *tempo*, which determines the number of quarter notes per minute. In the example above, the tempo is 60 quarter notes per minute.

To play the notes, we need to know their respective frequencies (in Hz). To facilitate this calculation, we represent the pitch of a note not by its position on the score, but rather by using the following two pieces of information:

* a main *note*—*do*, *re*, *mi*, *fa*, *sol*, *la*, or *si*;

* an octave 0, 1, 2, 3, etc.

This representation allows us to determine the frequency of a note easily, using the following formula:

$$f = f_0 \times 2^o$$

Here, $f_0$ is the frequency of its main note in the octave 0 and $o$ is its octave. Table 2.10 gives the frequencies in octave 0 for the main notes.

In order to represent all the elements of a score, our program begins by defining several types. The main notes are represented by the type **note** as follows<fnref n="5" />:

type note = Do | Re | Mi | Fa | Sol | La | Si

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —

<footnote n="5">⁵Here, we use the French naming system of musical notes, which is used in many other countries as well.</footnote>
<table><caption>Figure 2.10: Frequencies for octave 0 of the main musical notes.</caption><thead><tr><th>Note</th><th>Frequency (Hz)<br>for octave 0</th></tr></thead><tbody><tr><td>do</td><td>33</td></tr><tr><td>re</td><td>37</td></tr><tr><td>mi</td><td>41</td></tr><tr><td>fa</td><td>44</td></tr><tr><td>sol</td><td>49</td></tr><tr><td>la</td><td>55</td></tr><tr><td>si</td><td>62</td></tr></tbody></table>

This is an *enumerated* type, which defines a finite domain made up of seven elements (Do, Re, etc.), called *constructors*. Syntactically, OCaml requires that the name of a constructor begin with an uppercase letter.

Once we have defined this type, we may manipulate values of type `note` by simply using the names of their constructors:

```ocaml
# Re;;
- : note = Re
```

The pitch of the notes is represented using records of type `pitch` with two fields, `note` and `octave`, which must contain non-negative integers.

```ocaml
type pitch = { note : note; octave : int }
```

The durations, which are of type `duration`, are represented by the two constructors `Half` (half notes) and `Quarter` (quarter notes).

```ocaml
type duration = Half | Quarter
```

To represent the two kinds of signs that may appear on musical scores, we define the type `symbol` as follows:

```ocaml
type symbol = Note of pitch * duration | Rest of duration
```

This is an *algebraic type*, which allows us to distinguish between notes and silences by means of two constructors, `Note` and `Rest`. Unlike the constructors

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 14 [music.m1] — Playing a Musical Score

```python
type note = Do | Re | Mi | Fa | Sol | La | Si

type pitch = { note : note; octave : int }

type duration = Half | Quarter

type symbol = Note of pitch * duration | Rest of duration

type score = { symbols : symbol list; metronome : int }
```

```python
let frequency { note = n; octave = o} =

let f0 =
  match n with
    | Do -> 33
    | Re -> 37
    | Mi -> 41
    | Fa -> 44
    | Sol -> 49
    | La -> 55
    | Si -> 62

in

f0 * truncate (2. ** float o)
```

```python
let millisecondes d t =

let quarter = 60000 / t in

match d with
  | Half -> quarter * 2
  | Quarter -> quarter
```

```python
let sound t s =
  match s with
    | Note (p, d) ->
      let f = frequency p in
      Graphics..sound f (millisecondes d t)
    | Rest r ->
      Graphics.soun d 0 (millisecondes r t)
```

```python
let play_score = { 
  'symbolic': metronome = t, 
  'metronome': 
    List.iter (sound t) 1
```
of enumerated types `note` and `duration`, the constructors `Note` and `Rest` have arguments. In case of `Note`, the arguments are of type `pitch` and `duration`. `Rest` has an argument of type `duration`. For example, to create a silence of quarter-note duration, we write:

``` OCaml
# Rest Quarter;;
- : symbol = Rest Quarter
```

Similarly, to create a note `re` in octave 1 of half-note duration, we write:

``` OCaml
# Note ({ note = Re; octave = 1 }, Half);;
- : signe = Note ({note = Re; octave = 1}, Half)
```

Finally, scores are represented by the record type `score`, composed of a list of signs and a tempo that gives the number of quarter notes per minute.

``` OCaml
type score = { symbols : symbol list; metronome : int }
```

The first function of the program calculates the frequency associated with the pitch of a note based on the formula and the table of frequencies given above.

``` OCaml
let frequency { note = n; octave = o } =
```

Given a note `n` of type `note` and an octave `o`, the function `frequency` begins by determining the frequency `f0` of the main note `n` using the pattern matching construct `match n with` as follows:

``` OCaml
let f0 =
  match n with
    | Do -> 33
    | Re -> 37
    | Mi -> 41
    | Fa -> 44
    | Sol -> 49
    | La -> 55
    | Si -> 62
  in
...
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
This construct returns different values depending on the constructor used to create `n`. Thus, if `n` is the constructor `Do`, the construct `match n with` returns the integer `33`. Else, if `n` is the constructor `Re`, it is the integer `37` that is returned, and so forth. The main frequency `f0` is then used to calculate the frequency of the note:

`f0 * truncate (2. ** float o)`

The second function calculates the time (in milliseconds) corresponding to a duration `d` (a half or quarter note), for a given tempo `t`.

`let milliseconds d t = ...`

We begin by calculating the time of a quarter note, (`quarter`), for the given tempo:

`let quarter = 60000 / t in`

Next, depending on the duration `d`, we return `quarter * 2` milliseconds for a quarter note, and `quarter` milliseconds for a half note:

```haskell
match d with
| Half -> quarter * 2
| Quarter -> quarter
```

The following function, `sound`, either plays a musical note or a silence:

`let sound t s = ...`

Given a tempo `t` and a symbol `s`, `sound` pattern matches on `s` to determine if it is a musical note or a silence:

```haskell
match s with
| Note (p, d) ->
| ...
| Rest r ->
| ...
```

This pattern matching construct allows us not only to discern the constructor used to create `s`, but also to retrieve the arguments of this constructor. Thus, if `s` corresponds to the first *pattern Note* `(p,d)`, the two variables `p` and `d`

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
represent, respectively, the pitch and duration associated with this constructor. In the second pattern, the variable *r* represents the silence associated with the constructor *Rest*. In both cases, the variables introduced by the patterns have a scope limited to the expression on the right-hand side of the arrow ->.

When *s* is of the form *Note* (*p*, *d*), we calculate the frequency *f* associated with the pitch *p* of the note using the function *frequency*. Then, we use the function *Graphics.snd* to emit a sound of frequency *f* for a duration of (milliseconds *d* *t*):

| Note (p, d) ->
  let f = frequency p in
  Graphics.snd f (milliseconds d t)

When *s* is a silence of the form *Rest* *r*, we emit a sound of zero frequency
during (milliseconds *r* *t*) milliseconds.

| Rest r ->
  Graphics.snd 0 (milliseconds r t)

Finally, the last function plays the notes of a score one by one, using the function
*sound*:

let play_score { symbols = 1; metronome = t } =
List.iter (sound t) 1

**Additional Information**

Pattern Matching

In general, the pattern matching construct *match v with* generalizes what we
saw earlier in case of lists (section 2.8 *Reversing the Order of Lines in a Text*).
It contains *k* branches, each branch associating a pattern with an expression:

match v with
| pattern_1 -> e_1
| pattern_2 -> e_2
| ...
| pattern_k -> e_k

— openly licensed via [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
The value `v` is first evaluated and is then compared, from top to bottom, with each pattern. The only expression evaluated by this construct is the `e_i` corresponding to the first pattern *compatible* with the shape of `v`.

The syntax of patterns is very expressive. It allows us to decompose complex values with ease, for example values defined using the following types `t` and `u`:

```hml
type t = A of int * float | B of string
type u = { a : t; b : int * t }
```

Thus, the pattern `{ b = (_, A (x, _)) }` allows us to retrieve the integer 1 passed as argument to the constructor `A` in the following value:

```hml
{ a = B "foo"; b = (10, A(1, 4.5)) }
```

Informally, the pattern `{ b = (_, A (x, _)) }` is read as “a record whose field `b` contains a pair, the second component of which is a value constructed using `A` with two arguments, the first of which is named `x`.”

OCaml can also verify the exhaustivity of pattern matching, ensuring that all possible cases are indeed covered. Thus, for any value `v` of type `u`, the compiler detects that the following pattern matching is not exhaustive:

```hml
match v with
| { a = A(_ , x); b = ( _ , B y) } -> ...
| { a = A(_ , x); b = ( _ , A (y, _)) } -> ...
| { a = B x; b = ( _ , B y) } -> ...
```

It even indicates that values of the form `{ a=B _; b=(_, A (_, _)) }` are not handled by this pattern matching, which could lead to a runtime error. By contrast, the compiler verifies that the following construct *is* exhaustive, although this is not obvious *a priori*:

```hml
match v with
| { a = A(_ , x); b = ( _ , B y) } -> ...
| { a = A(_ , x); b = ( _ , A (y, _)) } -> ...
| { a = B x; b = ( _ , B y) } -> ...
| { a = _; b = ( _ , A(_ , y)) } -> ...
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The pattern matching construct also allows us to associate the same expres-
sion with several patterns. These patterns, called *or* patterns, take the following
form:

`match v with`

| pattern_1 | pattern_2 | ... | pattern_k -> e
| ...

The only syntactic constraint is that each pattern must introduce the same
variable names, and these must have the same type. For example, we may write
the following or pattern on values of type u:

`match v with`

| { a = A(x, _)} | { b = (x, _)} -> ...
| ...

It is equally possible to associate variable names to the sub-parts of a pattern
using the `as` notation, as in the following example:

`match v with`

| { a = B _ ; b = ( , (A (y, _ ) as z)) } -> (y, z)
| ...

Here, the variable *z* references the value that is matched by the (sub-)pattern
*A* (*y*, _). Thus, the application of this pattern matching to { *a* = *B* "foo";
*b* = (10, *A*(1, 4.5)) } will construct the pair (1, *A*(1, 4.5)).

Finally, pattern matching may be extended with arbitrary boolean condi-
tions, using the `when` notation as follows:

`match v with`

| pattern_1 when e -> e_1
| ...

For example, we can match values of type *u* having a field *a* of the form *A(x, _)*,
with *x* greater than 10, as follows:

`match v with`

| { a = A(x, _)} when x > 10 -> ...
| ...

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
It is important to note that the exhaustivity analysis does not take into account these boolean conditions and that all patterns constrained by such expressions are simply ignored.

## Algebraic Types

It is also possible to define polymorphic algebraic types. To do so, we must indicate the list of type variables (or parameters) that appear in the definition. Consider the following example:

```hml
type ('a, 'b) t = C of 'a * int | D of 'b | E of int
```

Here, the type `t` is parametrized by two variables `'a` and `'b`. The constructors `C` and `D` are polymorphic. Thus, as in the case of a polymorphic function, these constructors may be applied to arguments of any type:

```hml
# let v = C(3, "foo");
val v : (int, string) t = C(3, "foo")
```

The type `'a list` of polymorphic lists predefined in the OCaml standard library is an example of a polymorphic algebraic type. If the syntax allowed it, it could be defined by:

```hml
type 'a list = [] | :: of 'a * 'a list
```

Another example of a polymorphic algebraic type is the type `option` of the standard library defined by:

```hml
type 'a option = None | Some of 'a
```

It serves in particular to represent a value not yet initialized, or an optional result. For example, the following function returns either `None`, when it is not possible to divide `x` by `y`, or else `Some (x/y)`:

```hml
let division x y = if y = 0 then None else Some (x / y)
```

```hml
# division 2 0;
- : int option = None
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
## 2.13 Quadtrees

<figure><img src="image_30.png" /></figure>

### Ideas introduced

* trees, binary trees

* sharing

Our next program (page 114), `quad.ml`, manipulates black-and-white square images of size $2^n \times 2^n$. If the image is completely black or white, it is represented using a constant denoting its color. Otherwise, it is decomposed into four sub-images, each of size $2^{n-1} \times 2^{n-1}$, following the order indicated in figure 2.11.

<figure><img src="image_31.png" /><figcaption>Figure 2.11: Breaking up an image.</figcaption></figure>

The image is the union of the four sub-images. In our program, the type `quad` corresponds to this representation.

```hml
type quad = White | Black | Node of quad * quad * quad * quad
```

The constants `White` and `Black` respectively denote an image that is either completely white or completely black. The constructor `Node` corresponds to an image decomposed into four sub-images, which are the four arguments of this constructor.

Consider the image in figure 2.12. It is represented by the following value of type `quad`:

```hml
Node (Node (Black, Black, Black, White),
       Black,
       Node (Black, Black, Black, White),
       White)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_32.png" /><figcaption>Figure 2.12: An image of size 4 × 4.</figcaption></figure>

Graphically, we may also represent this value as follows:

<figure><img src="image_33.png" /></figure>

This is why we speak of *trees* in relation to such values.

Let us now write a function `checkerBoard`, which constructs a quadtree corresponding to a $2^n \times 2^n$ checkerboard. Thus, `checkerBoard 3` corresponds to the image in figure 2.13.

<figure><img src="image_34.png" /><figcaption>Figure 2.13: An 8 × 8 checkerboard.</figcaption></figure>

We proceed by recursion on $n$. If $n$ is 0, we make an arbitrary choice and return a black square.

```hml
let rec checkerBoard = function
  | 0 -> Black
```

If $n = 1$, we return a checkerboard of size $2 \times 2$:

```hml
| 1 -> Node (White, Black, White, Black)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Program 15 [quad.ml] — Quadtrees

```ocaml
type quad = White | Black | Node of quad * quad * quad * quad

let rec checkerBoard = function
| 0 -> Black
| 1 -> Node (White, Black, White, Black)
| n -> let q = checkerBoard (n - 1) in Node (q, q, q, q)

let rec draw x y w = function
| White ->
| ()
| Black ->
    Graphics.fillRect x y w w
| Node (q1, q2, q3, q4) ->
    let w = w / 2 in
    draw x         y         w q1;
    draw (x + w) y   w q2;
    draw (x + w) (y + w) w q3;
    draw x         (y + w) w q4

let () = draw 0 0 256 (checkerBoard 3)
```

Finally, if $n > 1$, we construct a $2^{n-1} \times 2^{n-1}$ checkerboard that we use four times over to construct a checkerboard of size $2^n \times 2^n$.

```ocaml
| n -> let q = checkerBoard (n - 1) in Node (q, q, q, q)
```

Let us now write a function `draw` that draws the image represented by a quadtree. This function takes as arguments the coordinates of the square in which we wish to draw the image: the position $(x, y)$ of the bottom-left point of the image, and the side length $w$ of the square. We proceed recursively on the structure of the quadtree.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
let rec draw x y w = function

If the tree consists of only one leaf, we distinguish between two cases: For a white leaf, we do nothing; for a black leaf, we shade the square defined by x, y, and w.

| White -> ()

| Black -> Graphics.fill_rect x y w w

If, however, we are in the case of the constructor `Node`, we begin by calculating the side length of the four sub-images, namely, `w/2`.

| Node (q1, q2, q3, q4) ->

let w = w / 2 in

Then, we draw the sub-images with four recursive calls to `draw`. In each case, we pass the coordinates of the bottom-left corner of the corresponding sub-image.

draw x         y         w q1;
draw (x + w) y  w q2;
draw (x + w) (y + w) w q3;
draw x         (y + w) w q4

In this way, we can draw an 8 × 8 checkerboard in a square of side 256 by calling `draw 0 0 256 (checkerBoard 3)`.

## Additional Information

### Constructors with Records

With the type `quad` of quadtrees, it is easy to make a mistake in the order of the sub-trees of the constructor `Node`. We have to be very careful and constantly keep in mind the figure 2.11. An alternative consists in naming the four sub-trees, as we do with record types:

type quad =

| White

| Black

| Node of { sw: quad; se: quad; ne: quad; nw: quad }

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Both within a pattern and when constructing a value, we use the syntax of
records to manipulate the arguments of the constructor `Node`. Thus, we con-
struct a node as follows:

Node { nw = a; sw = b; se = c; ne = d }

As we see here, the declaration order of the fields is not important. As in case
of records, we can use pattern matching to retrieve their values:

match q with
| ...
| Node { sw; se; ne; nw } -> ...

However, we cannot write the following:

match q with
| ...
| Node r -> ...

This is because there is no record as such, only a syntax to name the four
arguments of the constructor `Node`.

To understand the difference, let us compare the constructor `Node` above
with the constructor `C` of the type `t` below:

type r = { a: int; b: bool; c: int }
type t = C of r | ...

Here, the constructor `C` has a single argument of type `r`, which is a record. This value can be retrieved and, for example, passed to a function which takes a value of type `r`:

match ... with
| C r -> f r

This, however, has a cost. The constructor `C` contains a pointer to a record al-
located previously, which means two allocations are needed instead of one. And
accessing the components of the constructor `C` requires two memory accesses,
the first to access the record and the second to access the field.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
## Invariants

We may wish to guarantee the property that a quadtree is never made up of four leaves of the same color, since that would be an unnecessarily complicated representation. To enforce this invariant, we must make `quad` either an abstract or a private type. As alternatives to the constructors `Black`, `White`, and `Node`, we must then provide two constants `black` and `white`, and a function `node`, defined so as to guarantee the invariant.

```pascal
let node = function
  | White, White, White, White -> White
  | Black, Black, Black, Black -> Black
  | q1, q2, q3, q4 -> Node (q1, q2, q3, q4)
```

We is known as a *smart constructor*.

## Sharing

The attentive reader will have noticed that the function `checkerBoard` makes a single recursive call, reusing its result four times. What we have constructed is thus not a tree, but rather a DAG. A depiction of the result of `checkerBoard 3` that more accurately reflects its memory representation is therefore:

<figure><img src="image_35.png" /></figure>

In particular, `checkerBoard n` executes in $O(n)$ time and space. By contrast, *drawing* its result takes $O(4^n)$ time because the function `draw` traverses

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
the four sub-images successively. In other words, the function `draw` traverses a tree without taking into account the sharing that exists in memory. Section 11.4 *Hash-consing* explains how to exploit such sharing.

## Binary Trees

In a binary tree, each internal node contains exactly two sub-trees. The leaves, like the nodes, can be labeled. For example, binary trees with internal nodes labeled by integers correspond to the type:

```hml
type tree = Leaf | Node of tree * int * tree
```

Similarly, trees with leaves labeled by strings correspond to the type:

```hml
type tree = Leaf of string | Node of tree * tree
```

The reader will find numerous examples of such trees in the pages that follow.

## n-ary Trees

The number of sub-trees of an internal node is not necessarily fixed. It may vary and can even be unbounded. In this case, we may represent the sub-trees of a node by a list of trees. Thus we write:

```hml
type tree = Node of tree list
```

It is interesting to note that we no longer need a specific constructor to represent leaves because the value `Node []` fulfills this role. Of course, we may label the nodes of such a tree if we wish. An example may be found in section 5.4 *Prefix Trees*.

## 2.14 Solving the N-Queens Problem

<figure><img src="image_36.png" /></figure>

### Ideas introduced

* backtracking

* persistence

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We are interested here in the classic *N*-queens problem: *N* queens are to be placed on an *N* × *N* chessboard such that none of them are threatened by the others. Figure 2.14 shows one of the 92 solutions when *N* = 8.

<figure><img src="image_37.png" /><figcaption>Figure 2.14: One solution of the 8-queens problem.</figcaption></figure>

More precisely, we are interested in the problem of enumerating all solutions, without taking into consideration the symmetries of the problem. We proceed in a relatively brute fashion by exploring all possibilities, noting nevertheless that a solution must necessarily have one and only one queen on each line of the chessboard. In light of this, we try to fill the chessboard line by line, placing a queen each time in such a way that it is not threatened by the queens already placed. Thus, if we have placed three queens on the first three lines of the chessboard, we then search for a valid placement on the fourth line as follows:

<figure><img src="image_38.png" /></figure>

If we find one, we place a queen there and continue the search on the following line. Otherwise, we go back one step and begin again. A solution is obtained each time we manage to place a queen on the last line. By proceeding in such

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
a systematic manner, we are sure to find all solutions. This technique is called *backtracking*.

For each line of the chessboard, our program will keep track of the columns in which a queen may be placed. Thus, instead of trying all the *N* columns of the current line, we would be able to examine far fewer than *N* and would therefore backtrack sooner. We illustrate this idea for *N* = 8.

Let us suppose that we have already placed queens on the first three lines. Only five columns need be considered in the fourth line (at the bottom of the chessboard).

<figure><img src="image_39.png" /></figure>

Furthermore, three positions in the fourth line are threatened by queens already placed along a left diagonal. These three positions need not be considered.

<figure><img src="image_40.png" /></figure>

Similarly, two positions in the fourth line are threatened by queens already placed along a right diagonal. These two positions need not be considered.

<figure><img src="image_41.png" /></figure>

There are thus six positions on the fourth line that cannot be used, leaving only two to be considered, rather than eight.

<figure><img src="image_42.png" /></figure>

Our program will proceed recursively, keeping track at each instant of three sets of columns: the set `cols` of columns that remain to be considered; the set `d1` of columns that should be avoided since queens placed there would be threatened along a left diagonal; and the set `d2` of columns that should be avoided since queens placed there would be threatened along a right diagonal. In our example,

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Program 16 [queens.m1] — The N-Queens Problem

```python
module S = Set.Make(struct type t = int let compare = compare end)

let map f s = S-fold (fun x s -> S.add (f x) s) s S.empty

let rec upto n = if n < 0 then S.empty else S.add n (upto (n-1))

let rec count cols d1 d2 =
    if S.is_empty cols then
        1
    else
        S-fold
            (fun c res ->
                let d1 = map succ (S.add c d1) in
                let d2 = map pred (S.add c d2) in
                res + count (S.remove c cols) d1 d2)
            (S.diff (S.diff cols d1) d2)
        0

let () =
    let n = int_of_string Sys.argv.(1) in
    Format printf "%d@." (count (upto (n - 1)) S.empty S.empty)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
numbering the columns starting from the right, we have `cols = {0, 2, 5, 6, 7}`, `d1 = {3, 5, 6}`, and `d2 = {0, 3}`, as shown in the figures above (respectively in (1), (2), and (3)). The set of columns where queens can be placed is obtained by calculating the set-theoretic difference `cols \ d1 \ d2`, which gives the set `{2, 7}`, as shown in figure (4).

To manipulate such sets of integers, we use the module `Set.Make` of the OCaml standard library. This is a functor that we instantiate with a type equipped with a total order. (The code of such a functor will be explained later in this book, in the section *AVL* of chapter 5.)

We choose here the usual order on the integers, provided by the function `compare` of the library `Stdlib`.

```ocaml
module S = Set.Make(struct type t = int let compare = compare end)
```

The resulting module `S` provides a data structure `S.t` that represents a set of integers, a constant `S.empty` corresponding to the empty set, and operations such as `S.add` (adding an element), `S.remove` (removing an element), `S.diff` (set-theoretic difference), etc. An important property of this data structure is its *persistence*. This means that the operations applied to this data structure do not modify it, but instead return *new* data structures. Thus, if we have a set `s` of type `S.t`, then the expression `S.add 4 s` denotes a new set (containing 4 and all the elements of `s`), while the set `s` remains unmodified.

Let us now write our program using a recursive function `count` that takes as arguments the three sets `cols`, `d1`, and `d2` described above:

```ocaml
let rec count cols d1 d2 =
```

This function returns the number of solutions that are compatible with these arguments. The search ends when `cols` is empty. We then indicate that a solution has been found.

```ocaml
if S.is_empty cols then 1 else
```

Otherwise, we calculate the set of columns in which queens can be placed using the expression `S.diff (S.diff cols d1) d2`, as explained above. Then, we traverse the elements of this set using the iterator `S-fold`, where the accumulator is the current number of solutions found.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```h
S-fold
    (fun c res -> ...)
    (S.diff (S.diff cols d1) d2)
    0
```

For each column `c` where a queen can be placed, it suffices to call `count` recursively with the three sets adjusted accordingly. To adjust `cols`, it suffices to remove the element `c`, using `S.remove`. To adjust `d1` and `d2`, we use `S.add` to add the column `c` to each of them, and then shift their elements by one unit as appropriate. To do this, we define a function `map` that applies a function `f` to all the elements of a set `s`, that is, it constructs the set `{f(x) | x ∈ s}`. We may write it, for instance, using `S Fold`.

```h
let map f s = S Fold (fun x s -> S.add (f x) s) s S empty
```

Given this function, the set `d1` may be adjusted using `map succ`, where `succ` is the predefined function `fun x -> x + 1`. Likewise, the set `d2` is adjusted with `map pred`, where `pred` is the predefined function `fun x -> x - 1`. The function passed as argument to `S Fold` therefore has the following form:

```h
 fun c res ->
    let d1 = map succ (S.add c d1) in
    let d2 = map pred (S.add c d2) in
    res + count (S.remove c cols) d1 d2
```

With this, the function `count` is complete. It is important to note here the key role played by the persistence of the sets `cols`, `d1`, and `d2`. Indeed, these sets are reused for each value of `c`, and must therefore not be modified by the operations `S.add` and `S.remove`.

To solve the N-queens problem, it suffices to call `count` with `cols` equal to the set `{0, 1, ..., N - 1}`, and `d1` and `d2` each equal to the empty set. To this end, we define a function `upto` that constructs the set `{0, 1, ..., n}`.

```h
let rec upto n = if n < 0 then S empty else S.add n (upto (n-1))
```

The main part of the program retrieves the value of `N` from the command line and then displays the result obtained by `count`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
let () =
let n = int_of_string Sys.argv.(1) in
Formateer printf "%d@." (count (upto (n - 1)) S.empty S.empty)

We can thus enumerate the 365,596 solutions of the 14-queens problem in less
than a minute.

**Additional Information**

The data structures that you find in the literature on algorithms are, for the most
part, *imperative* in nature: They are modified in-place by the operations they
provide. Arrays and linked lists are the first examples that come to mind. Thus,
writing to an array's cell replaces the previous value by a new one. Something
similar occurs when we add an element to a linked list such as:

<figure><img src="image_43.png" /></figure>

The operation consists in modifying two of the pointers, as follows:

<figure><img src="image_44.png" /></figure>

As in case of the array, we have modified the structure of the list *in-place*. In
both cases, it is possible to return to the previous state, but it requires another
*in-place* modification.

A *persistent* data structure, by contrast, is a data structure whose operations
never modify their arguments; *new* values are returned instead. Of course, we
could render a data structure persistent by making a copy of it systematically,
but this would be grossly inefficient. There are other, more efficient means of
rendering an imperative data structure persistent. See, for instance, section 4.4
*Persistent Arrays*.

There is an entire class of data structures for which persistence is both possi-
ble and efficient, namely, *immutable* data structures, which cannot be modified
once constructed. For such data structures, it is possible to avoid unnecessary copies through sharing. This is easiest to illustrate in case of lists.

If we define a list `1` by `let 1 = [1; 2; 3]`, then, in terms of its memory representation, `1` is a pointer. It points to a first block that contains `1` and a pointer to a second block, and so on and so forth:

<figure><img src="image_45.png" /></figure>

If we now define a list `1'` by adding another element to the list `1`, with the declaration `let 1' = 0 :: 1`, we have the following situation:

<figure><img src="image_46.png" /></figure>

The application of the constructor `::` has the effect of allocating a new block, whose first element is `0` and whose second element is a pointer having the same value as `1`. The variable `1` continues to point to the same blocks as before. In general, any function that we may write on lists has the property of not modifying the lists passed as arguments.

It is very important to understand that the above involves *sharing*. The declaration of `1'` allocates a single block (because only one constructor is applied), and the blocks forming `1` are reused without modification. We have two lists of three and four elements respectively, namely `[1;2;3]` and `[0;1;2;3]`, but only four memory blocks. In particular, *no copy* is made. In general, OCaml never makes copies of values, unless you explicitly write a function to do so. Such a function would be useless in case of lists because a list cannot be modified in-place. Functions that make copies of values are not useful unless the data structures involved are mutable.

It is now clear why it is harder to add an element to the end of a list rather than to its head. This is because an in-place modification of the list `1` would be required:

<figure><img src="image_47.png" /></figure>

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
To add an element to the end of a list, we must make a copy of every block of the list. This is in fact what is done by the following function `append`, which concatenates two lists (see exercise 2.24):

```ocaml
let rec append l1 l2 = match l1 with
| [] -> l2
| x :: l -> x :: append l1 l2
```

We observe that this function creates as many blocks as there are in `l1` and shares only those of `l2`. Thus, if we declare `let l' = [4; 5]` and concatenate `l` and `l'` with `let l'' = append l l'`, we will have the following situation:

<figure><img src="image_48.png" /></figure>

Copies of the blocks of `l` have been made and those of `l'` have been shared.

Accordingly, lists must be used whenever the relevant operations are addition and removal from the front (*stack* structure). When we need to access and/or make modifications at arbitrary positions, it is preferable to use another data structure.

Crucially, the *elements* of the list are not themselves copied by the function `append`. In fact, the variable `x` in the code of `append` denotes an element of an arbitrary type and is not itself copied. This does make a difference when dealing with lists of integers. However, if we have a list `l` with three elements of a more complex type, for example the list `[((1,2,3); (4,5,6); (7,8,9))], then these will be shared between `l` and `append l [(10,11,12)]`:

<figure><img src="image_49.png" /></figure>

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
All this may appear unnecessarily expensive if we are used to lists that are
modified in-place, which is the traditional approach in the context of imperative
languages. However, this would be to underestimate the practical advantages of
persistence. Besides, it is important to note that the concept of persistence can
be easily implemented in an imperative language. We only have to manipulate
linked lists exactly as the OCaml compiler does. Conversely, we can certainly
manipulate lists that are modifiable in-place in OCaml, for example by defining
the following type:

```hml
type 'a mlist = Nil | Cons of 'a * 'a mlist ref
```

Here, the second argument of the constructor `Cons` is a reference. Unlike imperative languages, OCaml provides the possibility of defining immutable data structures in a natural manner that is also safe. (Even if we code a persistent data structure in C, the type system cannot prevent in-place modification, since all data in C is mutable).

Finally, we must not forget that unused memory is automatically recovered.
Consider for instance an expression such as:

```hml
let l = [1;2;3] in append l [4;5;6]
```

The three blocks of `l` are effectively copied during the construction of the list `[1;2;3;4;5;6]` but may be recovered immediately as they are no longer referenced anywhere. (Chapter 3 offers more details on memory management.)

## The Practical Advantages of Persistence

Persistence has many practical advantages. To begin with, it aids reasoning about the code and its correctness: Since the values manipulated by the program are immutable, we can reason mathematically about them. We can use equational reasoning without even worrying about the evaluation order. It is thus easy to verify the correctness of the function `append` once we have stated what it is supposed to do (namely, that `append 11 12` constructs the list formed from the elements of `11`, followed by the elements of `12`). A simple recursion on the structure of `11` suffices. If, however, we are dealing with lists that are modifiable in-place and a function `append` that modifies the last pointer of `11`

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
to make it point to 12, then the correctness argument is clearly more difficult. The contrast is even more flagrant when a list is to be reversed. The correctness of a program is important and must always take precedence over its efficiency. After all, nobody would want a program that is fast but incorrect.

Persistence is not only useful for correctness, it is also a powerful tool in contexts where *backtracking* is necessary. Suppose, for example, we write a program to find the way out of a maze using a function `find` that takes as argument a persistent state and returns a boolean indicating a successful search. A function `possible_move`s returns the possible moves from a particular state as a list. As the datatype is persistent, another function, `move`, returns the state resulting from a move and the current state. We also assume that a boolean function `is_exit` returns whether a particular state corresponds to the exit. We can then write the function `find` in the following way:

```ocaml
let rec find e =
    is_exit e || try_move e (possible_move e)
and try_move e = function
  | [] -> false
  | d :: r -> find (move d e) || try_move e r
```

Here, `try_move` is a function that tries the possible moves in a list, one by one. It is the persistence of the data structure encoding the state that allows us to write such concise code. If the state was a global data structure modified in-place, we would have to perform the move before calling `find` recursively in `try_move`. We would also have to *undo* this move in case of failure before trying other possible moves. The code would then look something like this:

```ocaml
let rec find () =
    is_exit () || try_move (possible_move())
and try_move = function
  | [] -> false
  | d :: r -> (move d; find()) || (undo_move d; try_move r)
```

This is indubitably less clear and more error-prone. Note that this is not an artificial example; *backtracking* is a programming technique regularly used when implementing graph traversals, coloring, enumeration of solutions, etc.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —