Consider a second example of the usefulness of persistence. Imagine a program that manipulates a database. At any moment, there is only one instance of this database. A priori, there is therefore no need to use a persistent data structure for it. Let us assume that the modifications performed on the database are complex, that is, involving a large number of operations, some of which can fail. We then find ourselves in a difficult situation if we need to *undo* the effects already performed before the failure. Schematically, the code could look like this:

```python
try
    ... perform modifications ...
with e ->
    ... restore the database to a coherent state,
    then handle the error ...
```

If we use a persistent data structure for the database, it may be stored in a
reference. Let us call it *db*. The operation that modifies the database sets the
value of this reference:

```python
let db = ref( ... initial database ... )
...
try
    db := ... operation that modifies the database !db ...
with e ->
    ... handle the error ...
```

From then on, there is no need to undo anything. The modification, however
complex it may be, constructs a brand new database. Only once this construc-
tion is complete is the reference *db* modified so that it points to the new database.
This final modification is atomic and cannot fail. If any exception is raised dur-
ing the modification itself, the reference *db* remains unchanged. The automatic
memory manager will then recover the memory that was unnecessarily allocated
during the modification.

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

The datatype of lists is obviously persistent because it is a type with a known definition, that is, it is concrete and immutable. When an OCaml module implements a data structure, declared as an *abstract type*, its persistent or imperative nature is not evident. Of course, the programmer can be informed of this fact by means of an appropriate comment in the interface. In practice, however, it is the types of the operations that provide this information. Consider the example of a persistent data structure that represents finite sets of integers. The interface of such a module looks like this:

```type set
val empty : set
val add : int -> set -> set
val remove : int -> set -> set
...
```

The persistent nature of sets is implicit in the interface: The operations `add` and `remove` return a value of type `set`, that is, a new set. The fact that the empty set `empty` is a constant and not a function makes the persistence even clearer. All occurrences of `empty` will be shared irrespective of its representation. This would not be possible with a mutable data structure.

A data structure for sets of integers that are modified in-place would instead have an interface of the form:

```type set
val create : unit -> set
val add : int -> set -> unit
val remove : int -> set -> unit
...
```

Here, the function for addition, `add`, does not return anything because it adds an element in-place to the data structure, and it is the same for the other operations. The value `empty` is replaced by a *function create* that takes an argument of type `unit`. Each call to `create` must construct a new instance of the data structure so that the in-place modifications of one do not affect the others.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Unfortunately, the type system of OCaml does not prevent the mixing of both kinds of data structures. Thus, you can give the type `int -> set -> set` to a function that adds an element to a set through side effects, for example by returning the set passed as argument. Conversely, you can give the type `unit -> set` to a function `empty` that returns a persistent empty set. In both cases, it is useless and potentially dangerous.

This does not mean, however, that a persistent data structure must necessarily be coded without any side effects. The good definition of persistent is:

$$ persistent = observationally immutable $$

In other words, it is not *purely applicative*, in the sense of an absence of side effects. We only have an implication in one direction:

$$ purely applicative \Rightarrow persistent $$

The opposite is false: There are persistent data structures that make use of side effects. This book contains several examples of such data structures. The situation is illustrated in figure 2.15.

<figure><img src="image_50.png" /><figcaption>Figure 2.15: Different classes of data structures.</figcaption></figure>

## 2.15 Exercises

### Drawing a Cardioid

2.1 Modify program 2.2 to plot the set of points in figure 2.1.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
**2.2** Write a program that draws the figure below.

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

## The Mandelbrot Set

**2.3** Modify the drawing of the Mandelbrot set by coloring points that are not in the set based on the first value of *i* for which $x_i^2 + y_i^2 > 4$. The color may be chosen, for example, by linearly interpolating between two predefined colors, and then using the function *Graphics rgb* (see section 2.10 *Breakout without Bricks*) and a simple rule of three.

**2.4** Modify the code of the preceding exercise as follows: Once the drawing is done, choose a point in the set using the mouse. Redo the drawing centered around this point and at one-tenth the scale.

**2.5** Write a program that draws a Koch snowflake. The snowflake is obtained by tracing three Koch curves along the three sides of an equilateral triangle. A Koch curve of depth *n* between two points *A* and *B* is defined as follows: For *n* = 0, it is the segment linking *A* and *B*.

$$A \xrightarrow{B}$$

For *n* > 0, the segment [*A*, *B*] is divided into three segments of equal length, [*A*, *C*], [*C*, *E*], and [*E*, *B*]. A point *D* is defined as the third vertex of an equilateral triangle *CED*:

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

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
We then draw four Koch curves of depth $n-1$ along the four segments $[A, C]$, $[C, D]$, $[D, E]$, and $[E, B]$.

By choosing an initial depth that is sufficiently large, we get a drawing of the following shape:

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

**2.6** Let $u_0$ be an integer greater than 1 and ($u_n$) the sequence defined by:

$$ u_{n+1} = \begin{cases} u_n/2 & \text{if } u_n \text{ is even} \\ 3u_n + 1 & \text{otherwise} \end{cases} $$

Write a program that reads the value of $u_0$ using `read_int` and displays the successive values of the sequence ($u_n$) as long as $u_n > 1$. (The Collatz conjecture states that for any value of $u_0$, we always reach the cycle $1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \dots$. Stated in 1928, this conjecture continues to defy the best efforts of mathematicians.)

**2.7** The problem of the tower of Hanoi consists in shifting $n$ discs of decreasing diameter, stacked one on top of the other, from one location to another, by using a third location temporarily. Only one disc may be moved at a time, by taking it off the top of a stack, and it may only be placed over a larger disc.

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

Write a program `hanoi` that reads the value of $n$ and then displays a valid sequence of moves to solve the problem, for example as follows:

```
> ./hanoi
4
moving disk from 1 to 3
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
moving disk from 1 to 2

moving disk from 3 to 2

moving disk from 1 to 3

...

## Sieve of Eratosthenes

**2.8** Write a function `sum`: `int array -> int` that calculates the sum of the elements of an array, first with a `for` loop, then with a recursive function.

**2.9** Write a function `occurs`: `int array -> int -> bool` that, for an array of integers `a` and an integer value `v`, determines if `v` appears in `a`. Write two variants of the program, one with a `while` loop and the other with a recursive function.

**2.10** Write a function `binary_search`: `int array -> int -> bool` that, for an array of integers `a` sorted in increasing order, and an integer value `v`, determines if `v` appears in `a`. Use binary search so as to have complexity $O(\log n)$, where `n` is the length of the array `a`.

**2.11** Write a function `shuffle`: `int array -> unit` that randomly shuffles the elements of an array using the following algorithm, called the “Knuth shuffle,” where `n` is the size of the array:

for `i` from 1 to `n` - 1

let `j` be a random integer between 0 and `i` (inclusive)

exchange the elements at indices `i` and `j`

You may use `Random.int k` to obtain a random integer between 0 and `k` - 1. Of course, this algorithm may be used for arrays of any type.

## Drawing a Curve

**2.12** Write a function `sum`: `(int -> int) -> int -> int -> int` that takes a function `f`, and two integers `i` and `j` as arguments, and calculates the following sum:

$$ \sum_{k=i}^{k=j} f(k). $$

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
2.13 Write a function dicho of type:

dicho : (float -> float) -> float -> float -> float

that searches for the zero of a monotonic function *f* on an interval [*a*, *b*] by
dichotomic search. The idea is as follows: Calculate the midpoint *x* of [*a*, *b*],
and compare the signs of *f*(*a*) and *f*(*x*). Depending on the result, repeat the
calculation on the interval [*a*, *x*] or [*x*, *b*]. Stop when *a* and *b* are sufficiently close
to each other. You can assume that [*a*, *b*] contains a zero of *f*.

Copying a File

2.14 Modify program 2.7 so that it correctly handles the case in which one of the two files cannot be opened. This triggers an exception of the form Sys_error s, where s is a string explaining the nature of the error (file does not exist, permission denied, etc.). This message should be displayed before terminating the program using exit 1.

2.15 In languages like C and Java, the statement break exits the nearest enclosing loop, and the statement continue jumps to the next iteration of the loop. Thus, the following C code displays 124567:

for (int i = 0; i < 10; i++) {
    if (i == 3) continue;
    if (i == 8) break;
    printf("%d", i);
}

Explain how to translate these two statements into OCaml. You may use two
exceptions, *Break* and *Continue*, to this end.

Inverting the Lines of a Text

2.16 Write a function mult : int list -> int that calculates the product of all the elements of a list of integers. Make sure to return 0 at the first occurrence of the integer 0.

— openly licensed via [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
**2.17** Redo the previous exercise, this time raising an exception if 0 is encountered, so as to avoid unnecessarily multiplying the first elements of the list.

**2.18** Redo exercise 2.16 by writing the function `mult` as a tail-recursive function.

**2.19** Write a function `insert : int -> int list -> int list` that inserts an integer into a list of integers sorted in increasing order. Avoid making an unnecessary copy of the part of the initial list that lies beyond the point of insertion.

**2.20** Using the above function `insert`, write a function `insertion_sort : int list -> int list` that sorts a list of integers in increasing order using the following algorithm, known as *insertion sort*: Beginning with the empty list, insert each element successively, using the function `insert`. Insertion sort is described in detail in chapter 12.

## Converting Integers from an Arbitrary Base

**2.21** Write a function `mem : 'a -> 'a list -> bool` that determines whether an element is present in a list, using the equality operator `=`. This function exists in the standard library, under the name `List.mem`.

**2.22** Write a function `count : 'a -> 'a list -> int` that counts the number of occurrences of an element in a list, using the equality operator `=`.

**2.23** Rewrite the function `count` of the last exercise using an iterator.

**2.24** Write a function `append : 'a list -> 'a list -> 'a list` that concatenates two lists. If $l_1 = [x_1; ... ; x_n]$ and $l_2 = [y_1; ... ; y_m]$, then the result of `append l_1 l_2` must be the list $[x_1; ... ; x_n; y_1; ... ; y_m]$ of length $n + m$. Proceed by recursion on the first list, thus performing $n$ recursive calls. The OCaml standard library provides this function both under the name `List.append` and as the `infix` operator `@`.

**2.25** Using the above function `append`, write a function `rev` of type `'a list -> 'a list` that reverses the order of elements of a list, that is, such that `rev [x_1; ... ; x_n] = [x_n; ... ; x_1]`. In the next section, we will discuss a more efficient method of implementing this function.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
2.26 Write a function subseq: 'a list -> 'a list -> bool that determines if a list $w_1$ is a sub-sequence of another list $w_2$, that is, if $w_1$ can be obtained by removing zero or more elements of $w_2$. For example, [1; 5; 4; 1] is a sub-sequence of [3; 1; 1; 5; 0; 4; 1].

2.27 Write a function exists: ('a -> bool) -> 'a list -> bool that takes a boolean function $p$ and a list $l$ as arguments and determines if $l$ contains at least one element $x$ such that $p(x)$ is true.

2.28 Using List.fold_left, write a function **forall**: ('a -> bool) -> 'a list -> bool that determines whether all the elements of a list of type 'a list satisfy a condition given by a function of type 'a -> bool. What is the problem with this solution? Propose a more efficient version.

2.29 Write a function filter: ('a -> bool) -> 'a list -> 'a list that takes a boolean function $p$ and a list $l$ as arguments, and returns the list of all the elements $x$ of $l$ for which $p(x)$ is true. Preserve the order of the elements. This function exists in the standard library under the name List.filter.

2.30 Using an iterator, write a function max_seq: bool list -> int that returns the length of the longest sequence of consecutive true values in a given list.

2.31 Write a function first: ('a -> bool) -> 'a list -> 'a that returns the first element of the list passed as argument satisfying the given condition. If such an element does not exist, the function should raise the exception **Not_found**.

2.32 Write an iterator fold.pairs of type:

fold.pairs: ('a -> 'b -> 'b -> 'a) -> 'a -> 'b list -> 'a

The iterator takes as argument a function $f$, a value $v$, and a list $[x_1; \dots; x_n]$, and returns:

$f(f(\dots f(f(v, x_1, x_2), x_2, x_3), \dots, x_{n-1}, x_n), x_n, x_1)$

In other words, the function traverses all pairs of consecutive elements $(x_i, x_{i+1})$, where the list is considered to be circular.

2.33 Propose a function to create a matrix init_matrix, analogous to Array.init, of type:

— openly licensed via CC BY SA 4.0 —
init_matrix: (int -> int -> 'a) -> int -> int -> 'a array array

2.34 Write a traversal function:

iter_matrix: (int -> int -> 'a -> unit) -> 'a array array -> unit

that applies a given function to all the elements of a matrix. The first two arguments of the function are the indices of the corresponding element. Explain why it is more efficient to traverse the matrix row-wise rather than column-wise.

Breakout without Bricks

2.35 Given a file a.m1 that contains `let () = Printf printf "A\n"` and a file b.m1 that contains `let () = Printf printf "B\n"`, compile these two files separately and verify that different results are obtained depending on the order in which the files are passed to the linker.

2.36 Given six files `a.m1i`, `a.m1`, `b.m1`, `c.m1`, `d.m1i`, and `d.m1`, and knowing that `A` and `B` depend on `C`, and that `C` depends on `D`, give all possible ways of compiling and linking a program containing the four compilation units `A`, `B`, `C`, and `D`.

2.37 Rewrite the code of Breakout in a single file with two submodules `Draw` and `Breakout`. Give the module `Draw` the same interface as that defined in `draw.mli`.

Logo Turtle

2.38 Redo exercise 2.5 that draws a Koch snowflake using the Logo turtle.

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

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Hint: Write a recursive function `von_koch: int -> float -> unit` whose first parameter is the number of recursive steps and the second the length of the segment `[A, B]`.

2.39 Rewrite the functor `Turtle` so that it is also parametrized by a module of signature:

```h
val open_graph: int -> int -> unit
val draw_line: int -> int -> int -> int -> unit
```

Here, `open_graph w h` opens a window of dimensions `w × h` and `draw_line x₁ y₁ x₂ y₂` draws a segment between the points `(x₁, y₁)` and `(x₂, y₂)`. Then, implement a module with such an interface using `Graphics`.

2.40 We would like to define a module to represent files endowed with reading and writing permissions. To this end, we introduce a type `permission`.

```h
type permission = Read | Write
```

Define a module `Access` to manipulate access rights. This module will provide an abstract type `t`, a value of type `t`, `default`, representing read and write access, and two functions `get` and `set` that allow, respectively, to get and set a permission.

```h
val get : t -> permission -> bool
val set : t -> permission -> bool -> t
```

Next, define another module `File` to represent a file endowed with access rights. This module will export a private record type `t`, containing the file name in a field of type `string` and the access rights in a `mutable` field of type `Access.t`. You will provide a function `create : string -> t` taking the file name as argument, a function `chmod` to modify the access rights, a function `open_in : t -> in_channel` to open a file for reading, and a function `open_out : t -> out_channel` to open a file for writing. The last two functions will raise an exception `PermissionDenied` in case of insufficient permissions.

2.41 Write multiple modules to manipulate monetary values in different currencies. All the modules should have the same signature:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
``` OCaml
module type MONEY = sig
    type t = private { i : int; f : int }
    val create : int -> int -> t
    val add : t -> t -> t
end
```

A monetary value is represented by an integer *i* and a fraction *f*, between 0 and 99, representing the number of cents. The integer *i* is signed. Write a module `Money` implementing the signature `MONEY`. Derive from it two modules `Euro` and `Dollar`, both having the signature `MONEY` and the structure `Money`, but with distinct types `Euro.t` and `Dollar.t`. Finally, write a function `euros_to_dollars`: `float -> Euro.t -> Dollar.t` that, given an exchange rate, converts euros to dollars.

2.42 Write a module to represent sets of integers by lists sorted in increasing order, with the following signature:

``` OCaml
module type ISET = sig
    type t
    val empty : t
    val add : int -> t -> t
    val union : t -> t -> t
    val mem : int -> t -> bool
end
```

What is the advantage of making the type `t` an abstract type?

2.43 Rewrite the code of the previous exercise in the form of a functor parametrized by the type of elements and a function defining a total order on them, that is:

``` OCaml
module type ELT = sig type t val compare: t -> t -> int end
module Set(E: ELT) : ... = struct ... end
```

Here, the value of `compare x y` is strictly negative if `x < y`, zero if `x = y`, and strictly positive if `x > y`.

2.44 Apply the functor of the previous exercise to obtain sets of even integers, giving these an arbitrary total order.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
**2.45** Write a data structure for polynomials of one variable. The idea is to represent a polynomial using the sorted list of its monomials, each monomial being represented by a pair of a coefficient and an exponent. Thus, the polynomial $X^7 - 3X^4 + 2$ is represented by the list [(1, 7); (-3, 4); (2, 0)]. In order to be generic with respect to the ring of coefficients, write the structure of polynomials as a functor `Poly` parametrized by a module of signature:

```python
module type Ring = sig
type t
val zero : t
val one : t
val add : t -> t -> t
val mul : t -> t -> t
val equal : t -> t -> bool
end
```

If `R` designates the argument of the functor `Poly`, the latter must provide the following functions:

```python
type t
val create: (R.t * int) list -> t
val add: t -> t -> t
val eval: t -> R.t -> R.t
```

Here, `t` is the type of polynomials, `create` constructs a polynomial based on a list of monomials, `add` adds two polynomials, and `eval` evaluates a polynomial at a point. Hint: Begin with the function `add` (see exercise 2.42) and then use it to write the function `create`.

**2.46** Continue the previous exercise by adding two constants, `zero` and `one`, and two functions, `mul` and `equal`, to the signature of the functor `Poly`. This yields polynomials endowed with the structure of a ring. In other words, the signature of the functor `Poly` can be written in terms of the signature `Ring`. The construct `include` is a syntactic shortcut to include the definition of one signature in another:

```
sig
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```ocaml
include Ring
val create: (R.t * int) list -> t
val eval: t -> R.t -> R.t
end
```

It is thus possible to obtain polynomials of several variables by applying the functor `Poly` several times in succession. For instance, the structure of polynomials of three variables and integer coefficients is obtained as:

```python
module P = Poly(Poly(Poly(Int)))
```

Here, it is assumed that `Int` implements the signature `Ring` for the integers.

## Quadtrees

**2.47** Write a function `rotate`: `quad -> quad` that turns an image anticlockwise by 90 degrees.

**2.48** Write a function `mirror`: `quad -> quad` that constructs the mirror symmetry along the vertical axis of an image represented by a quadtree. Thus, the function `mirror` allows switching between the following two images:

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

**2.49** Write a function `fractal`: `int -> quad` that constructs a quadtree representing a Sierpiński carpet fractal, by iterating the following process of decomposition:

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

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

**2.50** Modify program 2.14 to return the first solution found, in the form of an array *a* giving the column *a*[i] of the queen located on row *i*. When there is no solution, the exception *Not_found* should be raised.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
# OCaml Concepts: A Closer Look

What do you do if your program is ill-typed or consumes too many resources (memory or time)? To make the right diagnosis, it is necessary to understand the functioning of the compiler and the code it produces.

In this chapter, we address problems related to type-checking, memory use, and execution time.

## 3.1 Type-Checking Algorithm

While the compiler automatically infers the types of all values defined in a program, it may nevertheless be useful for programmers to have at least an intuitive understanding of the typing rules of OCaml. This would help them understand any error messages that may arise.

To compute the type of an expression, it suffices to traverse its definition from left to right, beginning with the most generic type possible, `a`, and accumulating type constraints.

Consider, for example, the following function definition:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
let f x y = if x y then [] else [y + 1]

We begin by rewriting this definition as follows:

let f = fun x -> fun y -> if x y then [] else [y + 1]

Next, we let:

val f : 'a

Since `f` is an expression of the form `fun x -> e1`, we deduce that `'a` must be the type of a function, `'a1 -> 'a2`:

val f : 'a1 -> 'a2

Similarly, `e1` is a function of the form `fun y -> e2`, so that `'a2` is equal to a type `'b1 -> 'b2`:

val f : 'a1 -> 'b1 -> 'b2

We now extract the type constraints on the variables `'a1`, `'b1`, and `'b2` originating from the expression `e2`, which is equal to:

if x y then [] else [y + 1]

From the function application `x y`, we deduce that `x` is a function. In other words, `'a1` is equal to a type `'c1 -> 'c2`. We therefore get:

val f : ('c1 -> 'c2) -> 'b1 -> 'b2

Next, since `y` is passed as argument to `x`, we deduce that the variable `'c1` is equal to `'b1`, so that the type of `f` is:

val f : ('b1 -> 'c2) -> 'b1 -> 'b2

Furthermore, since `x y` is used as the condition in an `if` construct, we deduce that `'c2` is equal to `bool`:

val f : ('b1 -> bool) -> 'b1 -> 'b2

The first branch of the `if` returns the empty list `[]`. Therefore, `'b2` is equal to `'d list`:

val f : ('b1 -> bool) -> 'b1 -> 'd list

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Finally, the second branch `[y + 1]` provides the last two constraints. From the addition `y + 1`, we deduce that `y` is of type `int`. The list `[y + 1]` therefore has the type `int list`, and the variable `d` is equal to `int`. The complete type of the function `f` is therefore:

```h
val f : (int -> bool) -> int -> int list
```

Let us now study the case of an ill-typed function. The function `g` below takes two arguments, `x` and `y`. The type inference algorithm detects the following error:

```h
# let g x y = if x y then [x] else [y] ;;
```

```
Error: This expression has type 'a but an expression was expected
       of type 'a -> bool
       The type variable 'a occurs inside 'a -> bool
```

The initial steps in the typing of `g` are the same as those in case of `f`. Thus, having scrutinized the expression `x y`, we deduce that `g` has the following type:

```h
val g : ('b1 -> bool) -> 'b1 -> 'b2
```

The first branch of the `if` returns the list `[x]`. Therefore, the variable `b2` must be equal to `('b1 -> bool) list`. Similarly, the second branch returns the list `[y]`. So `b2` must be of type `'b1 list`. Therefore, for `g` to be well typed, the types `('b1 -> bool) list` and `'b1 list` must be equal. This would require the equation of types `b1 = 'b1 -> bool` to have a solution, which is not possible in OCaml (unless we enable the option `-rectypes` of the compiler or interpreter). We now understand the above error message: It indicates that the variable `y` is of type `'a`, whereas it should have type `a -> bool`, which is not possible because the variable `a` appears within the type `a -> bool`.

In general, to determine the type of a program, or understand its typing errors, it is necessary to know the type constraints imposed by the constructs of the language. Here we present a (non-exhaustive) list of these constraints.

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

In a conditional `if e1 then e2 else e3`, the expression `e1` must be of type `bool`, and the expressions `e2` and `e3` must be of the same type, whatever that may be. The type of the conditional is that of `e2` (and therefore also that of `e3`).

### If-then

A conditional expression `if e1 then e2` (without the `else` branch) has type `unit`. The expression `e1` must be of type `bool` and `e2` of type `unit`.

### While

In a loop `while e1 do e2 done`, the expression `e1` must be of type `bool` and `e2` of type `unit`. The `while` loop is of type `unit`.

### For

In a loop `for i = e1 to e2 do e3 done`, the expressions `e1` and `e2` must be of type `int` and the expression `e3` of type `unit`. The `for` loop is of type `unit`.

### Sequence

In a sequence `e1; e2`, the expression `e1` must be of type `unit` while `e2` may be of any type. The type of `e2` gives the type of the sequence. If `e1` is not of type `unit`, we may write `let _ = e1 in e2` or `ignore e1; e2`.

### Declaration

In a `local` declaration `let p = e1 in e2`, the pattern `p` and the expression `e1` must be of the same type. The expression `e2` may be of any type. This is also the type of the declaration. In a `global` declaration `let p = e`, the type of `p` must be that of `e`.

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

A function of the form `function p -> e` or `fun p -> e` is of type `t1 -> t2`, where `t1` is the type of the pattern `p` and `t2` is the type of the expression `e`.

## Application

The application `e1 e2` requires that `e1` be of type `t1 -> t2` and that `e2` be of type `t1`. The type of the result of the application is `t2`.

## Pattern Matching

Consider the pattern matching construct:

```hkl
match e with
| p1 when b1 -> e1
| ...
| pk when bk -> ek
```

The associated constraints are that the expressions `e1`, ..., `ek` must all have the same type, and that the expressions `b1`, ..., `bk` must all be of type `bool`. The patterns `p1`, ..., `pk` must all have the same type as `e`. The global type of this construct is that of the expressions `e1`, ..., `ek`.

## Exception

Consider a `try-with` block of the form:

```hkl
try
e
with
| p1 -> e1
| ...
| pk -> ek
```

Here, the expressions `e`, `e1`, ..., `ek` must all be of the same type. The patterns `p1`, ..., `pk` must designate exceptions (of the predefined type `exn`). The type of the `try-with` block is that of the expression `e`.

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

As a rule, to make the best use of a programming language, it helps to understand its runtime model. OCaml is no exception in this regard. By runtime model, we mean the time (see the next section) and space complexity of the different constructs of the language. Even if we can often ignore these complexities by remaining at a higher level of abstraction, it is worthwhile to understand them.

### Value Representation

We begin by explaining the memory representations of OCaml values. An OCaml value occupies exactly one memory word (32 or 64 bits, depending on the architecture). If we consider this word as an integer, we may distinguish two cases, depending on whether the integer is even or odd:

* if it is an odd integer $2n + 1$, we interpret it as the integer value $n$;

* if it is an even integer, we interpret it as a pointer.

In short, an OCaml value is either an integer or a pointer. If it is an integer, it can represent a value of type `int`, a character, a boolean, or even a constant constructor like `[]` or `None`. Note that this explains the limitation of the type `int` to 31 bits (63 in a 64-bit machine), mentioned previously. If the value is a pointer, it points to a *block* allocated in memory. A block occupies $k + 1$ memory words, with $k \ge 1$. The first word of the block, called the *header*, plays a particular role that we will explain later. The following $k$ words contain OCaml values, and we say that $k$ is the size of the block. We will represent a block of size 5 as follows:

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

Thus, the pair `(1,2)` is represented by a pointer to a block containing two values, namely, the integer values 3 and 5 representing respectively the integers 1 and 2:
<figure><img src="image_59.png" /></figure>

More generally, an *n*-tuple is represented by a pointer to a block of size *n*. Arrays and records are also represented in memory by pointers to blocks. Thus, the array `[1; 2]` and the record `{a=1; b=2}` have *exactly* the same representation in memory as the pair `(1,2)`. We explained previously that a reference was nothing but a particular case of records, with a single field *contents* (see the additional information in section 2.6 *Tracing a Curve*). We deduce from this that the value `ref 1` is represented in memory in the form of a block of size 1, that is:

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

The *mutable* nature of the field *contents* means that the value contained in this block, here 3, can be modified in place. The same is true for the values of an array.

Let us now consider the representation of concrete types. The idea is simple: Constant constructors are represented by integers and other constructors by (pointers to) blocks. Consider, for example, the type:

```type t = A | B of t * t | C | D of char```

The two constant constructors *A* and *C* are represented by the integers 1 and 3, respectively. The two non-constant constructors *B* and *D* are represented by pointers to blocks of size 2 and 1, respectively. Thus, the value *B* (*A*, *B* (*D* 'a', *C*)) corresponds to three blocks, as follows:

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

Here, the value 195 corresponds to $2 \times 97 + 1$, where 97 is the code of the character 'a'.

For faster access, a pointer to a block points to its first field rather than its header. The latter contains the tag of the constructor, here *B* or *D*. This information is used particularly when pattern matching.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Consider the type of lists as a second example: The constant constructor `[]` is represented by the integer 1. The constructor `::` is represented by (a pointer to) a block of size 2. The list `1 :: 2 :: 3 :: []` is therefore represented in memory as follows:

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

We observe that OCaml lists are not fundamentally different from the linked lists used in C or Java. When an OCaml program manipulates lists (passing them as arguments of functions, returning them, etc.), it only manipulates the pointers to the blocks, exactly like a C or Java program would. The essential difference is that OCaml only permits the construction of well-formed lists since pointers are not explicit in the language. Where programmers using C or Java have to *think* about checking whether a pointer is `null`, programmers using OCaml would use a pattern matching construct that would *force* them to consider this case, and with a very concise syntax at that.

In general, the header contains the tag of the block. Beyond the cases we have already illustrated, the header can also identify a floating-point number, an array of floats, a string, an object, a function, etc. Note that the tag provides far less information than the type of the value. In general, the memory representation of OCaml values does not include typing information. The OCaml standard library provides a module `Obj` that can be used to explore this representation. We can thus test whether a value is represented as a block and, if so, retrieve its tag, size, fields, etc. This module must be used with caution given its strongly untyped nature.

## Notation

In what follows, we will simplify the graphical representation of OCaml values: Headers will not be drawn, and integer values will not be transformed using $n \mapsto 2n + 1$. Thus, the list `[1;2;3]` will be represented simply as:

<figure><img src="image_63.png" /></figure>
Comparison Operators

The equality operator = that we have already used several times may be applied to any two values, provided that they are of the same type. Thus, we can use it to compare values of the following type:

# type ty = D | A of int | B of bool | C;
type ty = D | A of int | B of bool | C
# A 1 = A 1 ;;
- : bool = true
# D = B true ;;
- : bool = false

This operator compares the structures of two values and therefore corresponds to the usual mathematical notion of equality. It is called the structural equality operator. Its negation is written as < > .

OCaml also provides another equality operator, ==. It is called the *physical equality* operator. Its negation is written as !=. The operator == compares values as integers, even if these integers represent memory addresses. Accordingly, we can observe that two constructor applications allocate two different memory blocks:

# A 1 == A 1 ;;
- : bool = false

Now that we know how OCaml values are represented, we can further de-
duce that = and == coincide on values like integers, characters, and constant
constructors. In case of more complex types, predicting the result of a compar-
ison using physical equality is more difficult. It would be necessary to have a
precise understanding of how the compiler manages memory allocation.

The physical equality operator *always* finishes in constant time, whereas
structural equality can take an arbitrary amount of time and even loop on
cyclic data. Let us illustrate this point with an example. We construct a cyclic
list l using a feature of OCaml that permits us to define a value using let-rec:

# let rec l = 1 :: 1 ;;
l : int list = [1; 1; 1; ... ]

— openly licensed via CC BY SA 4.0 —
The evaluation of `l == l` terminates whereas that of `l = l` does not.

```ocaml
# l == l ;;
- : bool = true
# l = l ;;
```

OCaml provides other structural comparison operators: on the one hand, `<`, `>`, `<=`, and `>=` of type `'a -> 'a -> bool`; and on the other hand, an order relation `Stdlib compare` of type `'a -> 'a -> int`, compatible with the preceding operators.

```ocaml
# C < A 1 ;;
- : bool = true
# A 1 < B true ;;
- : bool = true
# Stdlib compare (A 1) (B true) ;;
- : int = -1
```

The comparison operators are based on the uniform representation of values explained previously. However, their definition remains arbitrary and entirely linked to the internal representation of values in the language. It remains, nevertheless, useful to have a “generic” order relation, even if it is arbitrary.

For example, we can use `Stdlib compare` to construct complex structures that require an order relation, such as sets:

```ocaml
# module S = Set.Make(
  struct type t = ty
    let compare = Stdlib compare
  end) ;;
```

Here, the definition of `Stdlib compare` is not important as long as it is an order relation. However, if a specific notion of comparison is needed, it would have to be defined.

## Other Generic Functions

OCaml provides other generic functions, such as:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
* a hash function `Hashtbl.hash` of type `'a -> int`;

* marshalling functions, mentioned previously (see the additional information in section 2.7 *Copying a File*).

## Automatic Memory Management

As in other languages, like Lisp and Java, memory management in OCaml is automated. This means that the programmer explicitly indicates allocations (by constructing an array or a record, applying a constructor, etc.) but not *deallocations*. Deallocation is performed automatically by the *garbage collector* (GC). The functioning of the GC is intimately linked with the representation of OCaml values. On the one hand, the GC can distinguish between pointers and other values by examining the parity of the value. On the other, in case of a block, the header contains the information needed by the GC: the tag (as was explained above), the size of the block, and a few bits to mark the block as being in use. Thus, in a 32-bit architecture, the header is of the following form:

<table><tr><td>31</td><td>...</td><td>10</td><td>9</td><td>8</td><td>7</td><td>...</td><td>0</td></tr><tr><td>size</td><td></td><td></td><td>GC</td><td></td><td></td><td></td><td>tag</td></tr></table>

As the size of a block is encoded in 22 bits, it is relatively limited (up to $2^{22} - 1$, that is 4194303). This is, for instance, the maximum size of OCaml arrays. It can be obtained using `Sys.max_array_length`. The maximum size of strings is four times larger, because strings have a more compact representation than arrays. Thus, `Sys.max_string_length = 2^{24} - 5 = 16777211`. In a 64-bit machine, by contrast, these limits are well beyond what can be allocated in memory (respectively $2^{54} - 1$ and $2^{57} - 9$).

## Representation of Functions

Whenever a function may be used as a first-class value (see section 2.6 *Tracing a Curve*), it is represented by a pointer to a block. We speak then of *closure*. A closure contains two things:

* a pointer to the code to be executed;

— openly licensed via CC BY SA 4.0 —
* the values of variables susceptible of being used by this code, termed the environment.

The construction of a closure therefore consists in allocating a block whose size is determined by that of the environment, that is, by the number of free variables in the body of the function. Conversely, the application of a closure *f* to a value *v* consists in calling the function indicated by the code pointer of *f* and passing two arguments to the function, namely, the environment (in the form of the closure *f* itself) and the value *v*. Consider the following example:

``` OCaml
let diff_quotient dx f x = (f (x +. dx) -. f x) /. dx
let derivative = diff_quotient 1e-10
let my_cos = derivative sin
```

The value `derivative` is a function obtained by partially applying the function `diff_quotient`. It is represented by a closure whose code pointer corresponds to `fun f -> fun x -> ...`, and whose environment contains the value of `dx`, namely, `1e-10`. Similarly, the value of `my_cos` is a closure whose code pointer corresponds to `fun x -> ...`, and whose environment contains the values of `dx` (namely, `1e-10`) and `f` (namely, `sin`). The value `sin` is another example of a closure, whose environment is empty.

## 3.3 Analyzing the Execution Time of a Program

From the preceding discussion, we may deduce a certain number of facts concerning the time complexity of OCaml operations:

* The application of a non-constant constructor is proportional to the number of fields, since it consists in assigning the constructor arguments to the fields of a block. As the number of arguments of a constructor is known statically, this operation takes constant time and space.

* The application of a function also takes constant time, irrespective of how the function was constructed. Of course, we speak here of the application operation only, and not of the cost of evaluating the arguments or the function itself; these may be arbitrarily expensive.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
In what follows, we offer several practical and theoretical tools to measure and
analyze the execution time of a program.

Measuring Execution Time

It is easy to measure the total execution time of a program using a watch or,
better yet, with a tool provided by the operating system. The execution time
of part of an OCaml program, can be measured just as easily, and with great
precision, using the function Unix.times of the module Unix. This function
returns a record whose field tms utime contains the time that has elapsed since
the start of the program. This is a floating-point number, expressed in seconds,
with precision greater than a millisecond. By calculating the difference between
the two values returned by this function at two different points of the program,
we deduce the precise execution time of that part of the code. We would typically
write something like:

let start = (times()).tms utime in

let stop = (times()).tms utime in

We can then calculate the elapsed time using stop - . start. Exercises 3.3
and 3.4 focus on writing generic code for such measurements.

Informal Notions of Complexity

It is useful to measure the execution time of a program to evaluate its effi-
ciency, for example, to compare it with another program, as well as to determine
whether it can be used to solve a given problem. If we write a program that
sorts an array of *n* entries, we may measure its execution time for small values
of *n* and then try to extrapolate to larger values. If, for example, we are able
to sort *n* = 1 000 entries in a hundredth of a second, and if we observe that the
execution time is multiplied by a factor of 4 each time that *n* is doubled, then
we may estimate that we would need over two and a half hours to sort a million
entries.

The *complexity* of a program, or more generally of an algorithm, is defined as
the number of elementary operations that it must perform as a function of the

— openly licensed via CC BY SA 4.0 —
<table><thead><tr><th rowspan="2">n</th><th colspan="6">f(n) =</th></tr><tr><th>log n</th><th>n</th><th>n log n</th><th>n<sup>2</sup></th><th>n<sup>3</sup></th><th>2<sup>n</sup></th></tr></thead><tbody><tr><td>10<sup>1</sup></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>10<sup>2</sup></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>∞</td></tr><tr><td>10<sup>3</sup></td><td>-</td><td>-</td><td>-</td><td>-</td><td>1 s</td><td>∞</td></tr><tr><td>10<sup>4</sup></td><td>-</td><td>-</td><td>-</td><td>-</td><td>17 m</td><td>∞</td></tr><tr><td>10<sup>5</sup></td><td>-</td><td>-</td><td>-</td><td>10 s</td><td>12 j</td><td>∞</td></tr><tr><td>10<sup>6</sup></td><td>-</td><td>-</td><td>-</td><td>17 m</td><td>∞</td><td>∞</td></tr><tr><td>10<sup>7</sup></td><td>-</td><td>-</td><td>-</td><td>1 j</td><td>∞</td><td>∞</td></tr><tr><td>10<sup>8</sup></td><td>-</td><td>-</td><td>2 s</td><td>116 j</td><td>∞</td><td>∞</td></tr><tr><td>10<sup>9</sup></td><td>-</td><td>1 s</td><td>21 s</td><td>∞</td><td>∞</td><td>∞</td></tr></tbody></table>

Figure 3.1: Execution time of $f(n)$ operations, assuming a billion operations per second. Note that “–” indicates that the time is less than one second and “∞” that it is greater than one year.

size of the input data. In the above example, the complexity may be expressed as a function $f$ of the number $n$ of entries: $f(n)$ is the number of elementary operations performed to sort $n$ inputs. By elementary operations, we mean the operations that are atomic for the machine, for example, addition. If we assume that a machine these days performs a billion operations per second, figure 3.1 gives the execution time of $f(n)$ operations for different functions $f$.

In practice, the precise nature of the elementary operations and their respective cost is not important. We can term any operation whose time cost is constant an elementary operation. This includes arithmetic operations, function and constructor applications, assignments, etc. It suffices to retain the following principle: A million elementary operations can be performed instantaneously, a billion in a few dozen seconds, and a trillion over several hours.

## Complexity Analysis

Rather than experimental evaluations, we can analyze the code of a program to calculate the number of elementary operations that it will perform. Let us

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
suppose, for example, that our sorting program is written as two nested loops, such as:

```
for i = 1 to n - 1 do
    for j = i downto 1 do
        ...
```

Here, we assume that the omitted code (denoted by ... ) contains only a finite number of elementary operations, say C. We can then deduce that the total complexity is exactly:

$$f(n) = \sum_{i=1}^{n-1} C \times i = C \frac{n(n-1)}{2}.$$

This confirms our experimental observation that doubling n causes f(n) to be multiplied by approximately four. In practice, it is rarely this simple to analyze the complexity. Certain operations are only performed in certain cases, depending on checks performed by the program, which in turn depend on the inputs. We generally settle for the calculation of the worst-case complexity, which provides an upper bound on the total number of operations performed. We may also calculate the average complexity over the set of possible inputs of size n, for a given distribution of these inputs.

## Big O Notation

In practice, we use the big O notation to bound the complexity of a program. To express that a function f, defined on the natural numbers, does not grow faster than another function g, also defined on the natural numbers, we write:

$$f(n) = O(g(n))$$

This means that there is a constant C such that $f(n) \le Cg(n)$ for large enough n, or, more formally:

$$\exists C \exists N, \forall n \ge N, f(n) \le Cg(n)$$

— openly licensed via CC BY SA 4.0 —
If $f(n)$ denotes the complexity of an algorithm in terms of a parameter $n$, we say that “the complexity of the algorithm is in $O(g(n))$” if $f(n) = O(g(n))$. In the example involving sorting, the complexity is in $O(n^2)$.

An algorithm whose complexity is in $O(1)$ is executed in constant time, independently of the size of the data. It therefore involves a constant number of elementary operations, for example, two additions and a multiplication. An algorithm is said to be: *logarithmic* if its complexity is in $O(\log n)$; *linear* if it is in $O(n)$; *linearithmic* if it is in $O(n \log n)$; *quadratic* if it is in $O(n^2)$ and, more generally, *polynomial* if there is a constant $k$ such that its complexity is in $O(n^k)$; and *exponential* if it is in $O(2^n)$.

In general, we do not seek to exhibit the constants $C$ and $N$ hidden in the notation $O$. We are only concerned with the asymptotic order of magnitude, for example, when deciding whether one algorithm is better than another. Of course, for a *specific* value of $n$, an algorithm in $O(n^2)$ can certainly take less time to execute than another in $O(\log n)$, by virtue of the constants behind the $O$'s.

## Amortized Complexity

It is often worthwhile to calculate the total complexity of a sequence of $n$ operations and then divide by $n$, in order to obtain the average cost of each operation. This average cost may prove inferior to the worst-case complexity. We call the average complexity thus obtained *amortized complexity*, as opposed to the worst-case complexity. We give examples of amortized complexity in chapters 4 and 6.

## 3.4 Exercises

### Type-checking Algorithm

**3.1** Are the following functions well typed? If so, what is their type? If not, explain why.

let f1 x = let y = !x + 2 in y

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```hml
let f2 n = for i = 1 to n do i + 4 done
let f3 m n = if n = m then 1 else 2
let f4 l = match l with [] -> [] | y :: s -> [s]
let f5 x y = let z = x + 1 in y || z > 10
let f6 x = let z = ref x in z + 1
let f7 x y = for i = x to 10 do y := x :: !y done; !y
let f8 x y z = x y z
```

3.2 Consider the two functions below:

```hml
let foo x = x.a := (snd x.b) + 1
let bar x = x.c <- (fst x.b) :: x.c
```

Define 'a t as a record type so that we have:

```hml
val foo : 'a t -> unit
val bar : 'a t -> unit
```

## Analyzing the Execution Time of a Program

3.3 Write a function `time:` (`unit` -> `unit`) -> `float` that measures the execution time of the function passed as argument. Use the function `Unix.times` as explained above.

3.4 Write a function `time5:` (`unit` -> `unit`) -> `float` that does the following: executes the function passed as argument five times, measuring the execution time each time; eliminates the smallest and largest of the values obtained; and returns the mean of the three remaining values.

3.5 Write a program that produces the table in figure 3.1.
— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
Part II

Data Structures

— openly licensed via CC BY SA 4.0 —
<figure><img src="image_64.png" /></figure>
One of the simplest data structures is the array, represented by the OCaml type `array`. In this chapter, we present several variations on this data structure. We show how to construct resizeable arrays, compact arrays of booleans, arrays with an efficient concatenation operation, and persistent arrays.

## 4.1 Resizeable Arrays

A resizeable array is an array whose size can be increased or decreased at any time by means of an operation `resize`. The signature of such arrays is given in program 17. (We will use resizeable arrays in chapters 5 and 6.)

The idea behind the implementation of resizeable arrays is simple: We use a normal array to store the elements, and if it becomes too small, we allocate a larger array into which we copy the existing elements. To avoid spending too much time allocating and copying, we allow the backing array to be larger than needed, with the elements beyond a certain index left unused.

The type of resizeable arrays is therefore a record containing an ordinary array in a field `data` and the number of elements in use in a field `size`.

```type 'a t = {```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Program 17 — Minimal Signature for Resizeable Arrays

```kotlin
module type ResizeableArray = sig
type 'a t
val length : 'a t -> int
val make : int -> 'a -> 'a t
val resize : 'a t -> int -> unit
val get : 'a t -> int -> 'a
val set : 'a t -> int -> 'a -> unit
end
```

```kotlin
mutable size: int;
mutable data: 'a array;
}
```

Thus, if `v` is such a resizeable array, we may represent the situation as follows:

```
  v.size
 v.data  ... elements ...  ... unused ...
  Array.length v.data
```

Accordingly, we will maintain the following invariant throughout:

$$0 \le v.size \le \text{Array.length } v.\text{data}$$

If we wish to increase the size of the array `v`, there are two possibilities to consider. If the new size does not exceed the capacity of the array `v.data`, it suffices to modify `v.size`. Otherwise, we allocate a new, sufficiently large array and copy the elements of `v.data` into it. We then assign this new array to `v.data`. Whenever we wish to decrease the size of the array `v`, it suffices to modify `v.size`.

There is, however, a slight difficulty regarding this last point. Pointers to elements that are no longer in use should not be retained, so that the GC is able to collect them whenever possible. We therefore need a value of the right type

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
to replace the elements that are no longer in use. To this end, we will require
that a default value be provided when the array is created. We will save it in a
third field of the record. We thus arrive at the following type:

```typescript
type 'a t = {
  default: 'a;
  mutable size: int;
  mutable data: 'a array;
}
```

Let us now write the code for the different operations. The length of the
resizeable array is given by the field `size`.

```typescript
let length a = a.size
```

To create a new resizeable array, it suffices to use `Array.make`, and to store the
size and the default value.

```typescript
let make n d = { default = d; size = n; data = Array.make n d }
```

In general, we will maintain the following invariant on the type `t`: Every element
beyond index `size`, that is, every unused element, contains the value stored in
the field `default`.

To access the `i`-th element of a resizeable array `a`, it is necessary to verify
that the index is valid, as the array `a.data` may contain more than `a.size`
elements.

```typescript
let get a i =
  if i < 0 || i >= a.size then invalid_arg "get";
  a.data.(i)
```

Note that once this verification has been done, we could use `Array.unsafe_get`
to access `a.data` for greater efficiency. The assignment operation is analogous:

```typescript
let set a i v =
  if i < 0 || i >= a.size then invalid_arg "set";
  a.data.(i) <- v
```

All the subtlety lies in the function `resize`, which modifies the size of a
resizeable array `a`. Several scenarios are possible. If the new size `s` is less than

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

```typescript
type 'a t = {
    default: 'a;
    mutable size: int;
    mutable data: 'a array;
}

let length a = a.size

let make n d = { default = d; size = n; data = Array.make n d }

let get a i =
    if i < 0 || i >= a.size then invalid_arg "get";
    a.data.(i)

let set a i v =
    if i < 0 || i >= a.size then invalid_arg "set";
    a.data.(i) <- v

let resize a s =
    if s <= a.size then
        Array.fill a.data s (a.size - s) a.default
    else begin
        let n = Array.length a.data in
        if s > n then begin
            let n' = max (2 * n) s in
            let a' = Array.make n' a.default in
            Array.blit a.data 0 a' 0 a.size;
            a.data <- a'
        end
    end;
    a.size <- s
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
or equal to `a.size`, it suffices to replace the elements between `s` and `a.size-1` by `a.default`.

```pascal
let resize a s =
    if s <= a.size then
        Array.fill a.data s (a.size - s) a.default
```

We could also reallocate the elements into a smaller array (see exercise 4.2). If, however, `s` is larger than `a.size`, it is necessary to check whether the array `a.data` is large enough to contain `s` elements. We therefore compute the size `n` of the array `a.data` and compare it with `s`.

```pascal
else begin
    let n = Array.length a.data in
    if s > n then begin
```

If `s` is greater than `n`, it is necessary to resize the array. Here, we choose the strategy of doubling the size of the array `a.data`. (See exercise 4.1 for another strategy.) Since that may not suffice, we calculate the new size as the maximum of `2 * n` and `s`.

```pascal
    let n' = max (2 * n) s in
```

To be perfectly safe, it would be necessary to limit the new size to the maximum size of arrays, that is, `Sys.max_array_length`, and to fail if the value `s` is too large. This is left as an exercise for the reader.

We then allocate a new array of size `n`' into which we copy the elements of `a.data` that are in use. For this, we use the function `Array.blit`, which copies a portion of one array into another.

```pascal
let a' = Array.make n' a.default in
    Array.blit a.data 0 a' 0 a.size;
```

Then, we replace the array `a.data` by the new array.

```pascal
a.data <- a'
end
end;
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
When `s <= n`, there is nothing more to be done. Finally, in all scenarios, we end by updating the field `size`.

`a.size <- s`

This completes the implementation of resizeable arrays. The code is given in full in program 18 (see page 168).

## Complexity

Resizeable arrays are typically used when the number of elements to be stored is not known beforehand (see exercise 4.3). Let us suppose that we begin with a resizeable array of length 0 and increase its length `n` times by one unit, to end up with an array of length `n`. The naive strategy of giving the array `data` exactly the same length as the resizeable array entails that each `resize` with a length `i` would have cost `i`. The total cost would then be quadratic:

$$1 + 2 + \dots + n = \frac{n(n+1)}{2} = O(n^2).$$

However, the strategy implemented by `resize` here is more subtle, consisting in (at least) doubling the size of the array whenever it needs to be increased. The total cost is then linear, which may be shown as follows: Let us assume, without loss of generality, that $n \ge 2$. Let $k = \lfloor \log_2(n) \rfloor$, that is, $2^k \le n < 2^{k+1}$. Beginning with an empty array, we will have executed a total of $k+2$ resizings to arrive at an array `data` of the final size $2^{k+1}$. After the `i`-th resizing, where $i = 0, \dots, k+1$, the size of the array is $2^i$. The `i`-th resizing therefore has cost $2^i$. The total cost is then:

$$\sum_{i=0}^{k+1} 2^i = 2^{k+2} - 1 < 4n.$$

In other words, some of the `resize` operations have constant cost (when resizing is not actually necessary). Others, by contrast, have non-constant cost, but the total complexity remains linear. Averaging over the `n` operations, it is as if each addition had constant cost. The extension of a resizeable array by one unit therefore has amortized complexity $O(1)$.

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

If a program needs to manipulate a set of integers included within a reasonable interval, and if persistence is not required, then an array of booleans may be used. This is what we did, for instance, in section 2.5 *Sieve of Eratosthenes*. However, given that a boolean is represented by one memory word (32 or 64 bits depending on the architecture), a lot of memory is wasted. While a single bit per element would suffice, an array of booleans occupies 32 or 64 times that amount. The bit vector data structure is useful precisely in this regard: it enables the use of a single bit per element.

The signature of such a data structure is exactly the same as that of arrays, except that elements are of type `bool`. The beginning of such a signature is given in program 19 (see below).

The implementation consists in using an ordinary array of integers and storing several booleans in each of the integers: 31 booleans in a 32-bit architecture and 63 booleans in a 64-bit architecture. (Recall that OCaml reserves one bit of each integer for use by the GC.) We begin by letting `bpi` be the number of booleans stored in each integer.

```ocaml
let bpi = Sys.word_size - 1
```

The maximum size of a bit vector is therefore given by the following value:

```ocaml
let max_length = Sys.max_array_length * bpi
```

To represent a bit vector, we introduce the following type `t`:

```ocaml
type t = {
    length : int;
    bits : int array;
}
```

The field `length` contains the actual number of booleans present in the bit vector, as this is not necessarily a multiple of `bpi`. The field `bits` contains the array of integers. If $b_0, b_1, \dots, b_{bpi-1}$ are the first `bpi` elements of an array of booleans, they are represented in the first cell of the array `bits` by the integer

$$b_0 + 2b_1 + \dots + 2^{bpi-1}b_{bpi-1}$$

— openly licensed via CC BY SA 4.0 —
## Program 19 — Minimal Signature of Bit Vectors

```pascal
module type Bitv = sig
type t
val create : int -> bool -> t
val length : t -> int
val get : t -> int -> bool
val set : t -> int -> bool -> unit
end
```

The following `bpi` elements are represented in the same manner by the second integer of the array `bits`, and so forth. When the number of elements is not a multiple of `bpi`, some of the high-order bits of the last integer of the array are not used. To allow comparing bit vectors structurally, we enforce the following invariant on the representation:

```
unused high-order bits are 0
```

We can thus use the OCaml operations `=` or `<>` on bit vectors, irrespective of how they are constructed.

## Creation

Let us begin with the function `create`, which constructs a bit vector of size `n`, where all the elements have the same value `b`. Except for the last integer, all the elements of the array `bits` will contain the same value: 0 if `b` is `false` or $-1$ if `b` is `true`. This is because in the two's-complement representation, $-1$ is written in binary using only the digit 1, that is, $-1 = (1 \cdots 1)_2$. The function `create` therefore begins by defining this initial value, 0 or $-1$, depending on the value of `b`.

```pascal
let create n b =
    let initv = if b then -1 else 0 in
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The number of elements of the array `bits` is then determined by the Euclidean
division of `n` by `bpi`.

let `q` = `n` / `bpi` and `r` = `n` mod `bpi` in

If the remainder `r` is 0, then all elements of the array are fully used, and it
suffices to construct an array of size `q` initialized with `initv`.

if `r` = 0 then
{ `length` = `n`; `bits` = `Array.make` `q` `initv` }

If the remainder `r` is not 0, we need to construct an array of `q` + 1 integers. All
the elements contain `initv`, except for the last one, whose high-order bits must
be 0 to respect the invariant. More precisely, if `b` is true, then the last element
of the array must have exactly `r` low-order set bits. This is easily obtained using
the expression `(1 lsl r) - 1`. This completes the function `create`:

else begin
  let `a` = `Array.make` (`q` + 1) `initv` in
  if `b` then `a.(q)` <- `(1 lsl r) - 1;`
  { `length` = `n`; `bits` = `a` }
end

The complete code is given in program 20.

Reading

To read the *n*-th element of a bit vector we must first determine the index *i* of
the corresponding integer in the array, and then the index *j* of the corresponding
bit within this integer. The values of *i* and *j* are obtained from the Euclidean
division of *n* by *bpi*. Given the *i*-th element of the array, in order to extract the
*j*-th bit, it suffices to shift this integer *j* positions to the right using `lsr`, and
then test its least significant bit. We end up with the following function:

let `get` `v` `n` =
let `i` = `n` / `bpi` and `j` = `n` mod `bpi` in
(`v`.bits.(i)) `lsr` `j`) land 1 <> 0

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
## Program 20 — Creation of a Bit Vector

```pascal
let create n b =
  let initv = if b then -1 else 0 in
  let q = n / bpi and r = n mod bpi in
  if r = 0 then
    { length = n; bits = Array.make q initv }
  else begin
    let a = Array.make (q + 1) initv in
    if b then a.(q) <- (1 lsl r) - 1;
    { length = n; bits = a }
  end
```

Equivalently, we could also perform a bitwise `and` operation against the integer containing a single set bit in the `j`-th position, which is obtained using the expression `1 lsl j`:

`v.bits.(i) land (1 lsl j) <> 0`

## Writing

To assign a value `b` of type `bool` to the `n`-th element of a bit vector `v`, we begin by determining its position exactly as we did for reading, via the Euclidean division of `n` by `bpi`.

```pascal
let set v n b =
  let i = n / bpi and j = n mod bpi in
```

We then consider the two possible cases separately. If `b` is `true`, that is, if the `j`-th bit of `v.bits.(i)` must be set to `1`, we perform a *logical or* against the integer containing a single set bit in the `j`-th position.

```pascal
if b then
  v.bits.(i) <- v.bits.(i) or (1 lsl j)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Program 21 — Reading and Writing in a Bit Vector

```pascal
let get v n =
  let i = n / bpi and j = n mod bpi in
  (v.bits.(i) lsr j) land 1 <> 0

let set v n b =
  let i = n / bpi and j = n mod bpi in
  if b then
    v.bits.(i) <- v.bits.(i) lor (1 lsl j)
  else
    v.bits.(i) <- v.bits.(i) land lnot (1 lsl j)
```

Otherwise, we must set the *j*-th bit to 0, which can be done using a *logical and* against an integer with all bits set, except the *j*-th.

```pascal
else
  v.bits.(i) <- v.bits.(i) land lnot (1 lsl j)
```

The complete code of the functions `get` and `set` is given in program 21. The two operations clearly have cost $O(1)$.

Set-Theoretic Operations

Bit vectors come into their own when they are used to represent sets. In particular, the union, intersection and complement operations can be implemented efficiently by the corresponding bitwise operations.

Consider, for example, the *logical and* operation of two bit vectors, `inter`, which also computes the intersection of the corresponding sets. This operation is only meaningful when the two bit vectors are of the same size. We begin by verifying this.

```pascal
let inter v1 v2 =
  let l1 = v1.length in
  if l1 <> v2.length then invalid_arg "Bitv.inter";
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 22 — Operations and and not on bit vectors

```h
let inter v1 v2 =
    let l1 = v1.length in
    if l1 <> v2.length then invalid_arg "Bitv.inter";
    let b = Array.mapi (fun i ei -> ei land v2.bits.(i)) v1.bits in
    { length = l1; bits = b }
```

```h
let normalize v =
    let r = v.length mod bpi in
    if r > 0 then
        let s = Array.length v.bits - 1 in
        v.bits.(s) <- v.bits.(s) land (1 lsl r - 1)
```

```h
let compl v =
    let b = Array.map lnot v.bits in
    let r = { length = v.length; bits = b } in
    normalize r;
    r
```

Once we know that both vectors are of the same size, we implement the *logical and* operation itself. For this, we may use the function `Array.mapi`, which constructs an array by applying a function to all the elements of another array.

```h
let b = Array.mapi (fun i ei -> ei land v2.bits.(i)) v1.bits in
{ length = l1; bits = b }
```

This completes the function `inter`. We can similarly write the function `union`, which computes the set-theoretic union, by performing a *logical or*.

Note that the invariant (4.1) is respected, because `and` and `or` preserve the unused high-order `0s`. This is not the case with bitwise operations like `negation` or `exclusive or`. In these cases, it is necessary to re-establish the invariant by zeroing the unused high-order bits a *posteriori*. Let us write a function `normalize` to do this. We begin by letting `r` be the number of bits in use in the last integer

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

```kotlin
let normalize v =
    let r = v.length mod bpi in
```

If this number is not zero, we must zero out all bits of index `r` and higher. This can be implemented using a mask containing exactly `r` low-order set bits, that is, `1 lsl r - 1`.

```kotlin
if r > 0 then
    let s = Array.length v.bits - 1 in
    v.bits.(s) <- v.bits.(s) land (1 lsl r - 1)
```

This completes the function `normalize`.

We can easily derive from this a function `compl` that computes the bitwise negation of a bit vector, that is, the complement of the corresponding set.

```kotlin
let compl v =
    let b = Array.map lnot v.bits in
    let r = { length = v.length; bits = b } in
    normalize r;
    r
```

The functions `inter` and `compl` are summarized in program 22 (see page 176). They have cost $O(n)$ in time and space, where $n$ is the size of the bit vectors concerned.

Among other useful set-theoretic operations, we may also consider iteration over all elements. For a bit vector, this boils down to iterating over the set of indices for which the corresponding boolean is `true`. Such an iteration may be expressed as a function of the form:

```kotlin
val iteri_true : (int -> unit) -> t -> unit
```

To implement this function, we iterate over the elements of the array using `Array.iteri`. For each element, we iterate over the set bits with a loop that successively tests each bit. We obtain the following code:

```kotlin
let iteri_true f v =
    Array.iteri
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 23 — Iteration Over the Set Bits of a Bit Vector

```pascal
let iteri_true f v =
  Array.iteri
    (fun i ei ->
      let index = i * bpi in
      let rec visit x =
        if x <> 0 then begin
          let b = x land -x in
          f (index + ntz b);
          visit (x - b)
        end
      in
      visit ei)
    v.bits
```

```pascal
    (fun i ei ->
      let index = i * bpi in
      for j = 0 to bpi - 1 do
        if ei land (1 lsl j) <> 0 then f (index + j)
      done)
    v.bits
```

It is not necessary to consider the case of the final element of the array separately, because the invariant guarantees precisely that the unused bits are 0.

Although correct, this solution is relatively inefficient, because it successively tests all bits of the array. We would like the cost of the iteration to decrease if there are fewer set bits. In other words, we need an efficient means of iterating over the set bits of an integer.

As it so happens, the two's-complement representation allows extracting the low-order set bit of an integer x easily by performing a *logical and* of x and -x (see exercise 4.5). This gives an efficient means of iterating over the set bits of an integer, by successively extracting and zeroing each set bit in increasing

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

There remains, however, one difficulty: The expression `x land -x` does not return the *index* `i` of the low-order set bit in `x`, but instead returns `2^i`. We therefore need to calculate the base 2 logarithm of this value or, equivalently, the number of low-order 0s. For this, let us suppose that we are given a function `ntz`, for *number of trailing zeros*, that calculates the number of low-order 0s of an integer.

We may then rewrite the part of the code of `iteri_true` that examines the set bits of `ei` with the help of a recursive function `visit` instead of a `for` loop.

```pascal
let rec visit x =
  if x <> 0 then begin
    let b = x land -x in
    f (index + ntz b);
    visit (x - b)
  end
  in
  visit ei
```

The function `visit` ends as soon as its argument is 0, that is, when it does not contain any set bit. Otherwise, we extract the low-order set bit, `b`. We call `f` on the corresponding index `index + ntz b`, and then call `visit` again on `x-b`, which is `x` with the `b-th` bit zeroed out. The complete code of `iteri_true` is given in program 23 (see page 178). The function `ntz` is the focus of exercise 4.6.

Finally, let us write a function `cardinal`: `t -> int`, which calculates the number of set bits in the bit vector, that is, the cardinal of the set. It suffices to calculate the sum of the number of set bits in each element of the array. If we assume we are given a function `pop` of type `int -> int` that calculates the number of set bits of an integer, then the function `cardinal` is easily obtained.

```pascal
let cardinal v =
  Array.fold_left (fun n x -> n + pop x) 0 v.bits
```

The function `pop` (short for *population count*) remains to be written. We can write it by extracting the bits one by one, again thanks to the expression `x land -x`:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```h
let pop x =
  let rec count n x =
      if x = 0 then n else count (n + 1) (x - (x land -x)) in
    count 0 x
```

We can render this function more efficient by tabulating it (see exercise 4.12).

## Other Operations on Bit Vectors

To be complete, a bit vector library should also provide other operations. On the one hand, it should provide the same operations that we use for arrays, like `append`, `sub`, `fill`, and `blit`. On the other hand, it should also offer arithmetic operations that interpret a bit vector as an integer of *n* bits, such as addition, shifts, and conversions to and from the different integer types of OCaml. Some of these operations are proposed in exercises 4.8–4.11.

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

**For Further Information**

Warren's *Hacker's Delight* [24] details numerous techniques to manipulate the bits of an integer, such as the ones we have used to implement Patricia trees and bit vectors. In particular, the book gives several variations of the functions `ntz` and `pop`.

## 4.3 Ropes

This section presents the *rope* data structure. This data structure was originally introduced as an alternative to strings, to address the following issues:

* Strings are not persistent; they are immutable in OCaml, but this is not necessarily the case in other languages, like C for instance.

* Strings are limited in size, especially when OCaml is used on a 32-bit machine, where the limit is $2^{24} - 5$ characters.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
* Concatenation and substring extraction have a significant cost, particularly in space, as they involve copying the contents of the underlying string.

To address these issues, the rope data structure draws on a simple idea: A rope is nothing but a binary tree whose leaves are (ordinary) strings and whose inner nodes should be interpreted as concatenations. A rope therefore corresponds to the following type:

```type t =
| Str of string
| App of t * t
```

For example, one possible value by which the string "a very long string" may be represented is the following:

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

Two considerations lead us to refine the proposed type `t`. On the one hand, numerous algorithms require efficient access to the length of a rope, particularly to decide whether to descend along the left or the right subtree of an `App` node. It is therefore advisable to decorate each internal node with the length of the rope. On the other hand, it is important to share substrings between ropes themselves as well as with the ordinary strings used to construct the ropes. Hence, rather than having the `Str` node point to a complete OCaml string, we prefer to have it designate a substring of an OCaml string. A substring of a string `s` is represented by a triple `(s, o, n)`, denoting `s[o..o + n - 1]`, that is, the portion of `s` of length `n` starting at offset `o`. We thus obtain the following type:

```type t =
| Str of string * int * int
| App of t * t * int
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
A node `App(r₁, r₂, n)` represents the concatenation of the two ropes `r₁` and `r₂`, whose total length is `n`. We could also have stored the sizes of `r₁` and `r₂` in the node. However, retaining only the total size is more economical in terms of memory space, and there is no loss of efficiency in practice.

## Genericity

We notice that the notion of rope is not related to that of string. Instead of the type `string`, we could equally use arrays or lists of characters or, more generally still, sequences of values of a type other than that of characters. In fact, all we need is a data structure of *sequences* of a certain *type of characters*. We can then construct ropes whose leaves consist of these sequences.

The resulting data structure has *the same signature* as that with which we started, namely, the signature of sequences for the same type of characters.

Program 24 gives a minimal signature `STRING` for a data structure of strings. The abstract type `t` is that of strings, and the type `char`, that of their characters. This signature contains only the operations that are needed to implement the rope structure. They are compatible with those of the OCaml module `String`.

## Program 24 — Generic String Signature

```ocaml
module type STRING = sig
    type t
    type char
    val length : t -> int
    val empty : t
    val make : int -> char -> t
    val get : t -> int -> char
    val append : t -> t -> t
    val sub : t -> int -> int -> t
end
```

We introduce a signature `ROPE` for ropes in program 25. This signature includes the module `S` of strings that will be the leaves of the ropes. The

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

```python
module type ROPE = sig
    module S : STRING
        include STRING with type char = S char
    val of_string : S.t -> t
    val set : t -> int -> char -> t
    val delete_char : t -> int -> t
    val insert_char : t -> int -> char -> t
    val insert : t -> int -> t -> t
end
```

signature `ROPE` provides the same operations as those of strings, for the same type of characters, which can be translated as follows:

```python
include STRING with type char = S char
```

Ropes are immutable. Update operations (`set`, etc.) return new ropes.

The rope structure is naturally implemented as a functor parametrized by a module `X` of signature `STRING`:

```python
module Make(X : STRING) : (ROPE with module S = X) = struct
```

The module obtained by applying this functor has the signature `ROPE with module S = X`, which specifies that its module `S` is the module `X` passed as argument of the functor. The code thus begins by defining `S` to be equal to `X`:

```python
module S = X
```

The type of characters of the rope is the same as that of strings:

```python
type char = S char
```

The type of ropes is as presented earlier:

```python
type t =
    | Str of S.t * int * int
    | App of t * t * int
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We will enforce several invariants on this type. On the one hand, for every rope of the form `Str (s, o, n)`, we have the inequalities:

$$0 \le o, \ 0 \le n \text{ and } o + n \le S.length \ s$$

On the other hand, for every rope of the form `App (u, v, n)`, we have the inequalities:

$$0 < \text{length } u, \ 0 < \text{length } v \text{ and } n = \text{length } u + \text{length } v$$

## Basic Operations

By definition of the type `t`, the length of a rope can be computed in constant time.

```h
let length = function
  | Str (_,_,n)
  | App (_,_,n) -> n
```

The construction of the empty rope is straightforward using the empty string:

```h
let empty =
  Str (S.empty, 0, 0)
```

More generally, the rope corresponding to a string `s` is given by:

```h
let of_string s =
  Str (s, 0, S.length s)
```

Importantly, the type `S.t` must itself be persistent in order to guarantee both the persistent nature of ropes and the correctness of rope operations. This is the case when `S.t` is the type `string`, as strings in OCaml are immutable.

To access the `i`-th character of a rope, it suffices to go down the tree until the target leaf is reached. We assume that the index is valid. The recursive part of the operation is then written as follows:

```h
let rec unsafe_get t i = match t with
  | Str (s, ofs,_) ->
    S.get s (ofs + i)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 26 — Basic Operations on Ropes

module Make(X : STRING) : (ROPE with module S = X) = struct

module S = X

type char = S char

type t =

| Str of S.t * int * int

| App of t * t * int

let empty = Str (S.empty, 0, 0)

let length = function

| Str (_,_,n)

| App (_,_,n) -> n

let of_string s = Str (s, 0, S.length s)

let make n c = of_string (S.make n c)

let rec unsafe_get t i = match t with

| Str (s, ofs, _ ) ->

S.get s (ofs + i)

| App (t1, t2, _ ) ->

let n1 = length t1 in

if i < n1 then unsafe_get t1 i else unsafe_get t2 (i - n1)

let get t i =

if i < 0 || i >= length t then invalid_arg "get";

unsafe_get t i

— openly licensed via CC BY SA 4.0 —
| App (t1, t2, _ ) ->
  let n1 = length t1 in
  if i < n1 then unsafe_get t1 i else unsafe_get t2 (i - n1)

We see here the importance of being able to retrieve the size of t1 in constant time. The complexity of this operation is therefore bound by the height of the tree. As we will see later, ropes can be balanced so as to minimize this height.

We define a function `get` that also checks whether the index is valid, as a wrapper around `unsafe_get`.

let get t i =
    if i < 0 || i >= length t then invalid_arg "get";
    unsafe_get t i

These basic operations on ropes are presented together in program 26 (see page 185).

## Concatenation

A *priori*, the concatenation of two ropes t1 and t2 is as simple as applying the constructor App and calculating the total length, that is:

let append t1 t2 =
    App (t1, t2, length t1 + length t2)

We note that this operation thus takes constant time. However, iterated concatenations may cause the number of nodes, and hence the height of the tree, to increase rapidly, to the detriment of other operations.

Two ideas allow us to control the number of nodes and the height of the tree. The first idea consists in actually concatenating “small” leaves (i.e. short strings) when they are found side by side in the tree. We may choose, for example, to concatenate the leaves s1 and s2 in the three situations illustrated in figure 4.1. The first situation corresponds to the concatenation of a rope whose right branch is the small leaf s1, with another small leaf s2. The second corresponds to the concatenation of two small leaves, s1 and s2. The third is the mirror image of the first.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
<figure><img src="image_67.png" /><figcaption>Figure 4.1: Possible situations with adjacent leaves.</figcaption></figure>

To determine whether the leaves are small enough to be concatenated, we use a constant:

let small_length = 256

The constant is arbitrary and should be chosen depending on the specific use of the rope structure. Exercise 4.15 proposes making this constant a parameter of the functor.

To implement the concatenation of two leaves, we define the following general function that concatenates fragments of two strings, s1 and s2:

let append_string s1 ofs1 len1 s2 ofs2 len2 =
    Str (S.append (S.sub s1 ofs1 len1) (S.sub s2 ofs2 len2)),
    0, len1 + len2)

We now give the code of the function `append`, which implements the concatenation of two ropes `t1` and `t2`.

We begin by considering the case in which one of the two ropes is empty.

let append t1 t2 = match t1, t2 with
| Str (_,_,0), t | t, Str (_,_,0) ->
  t

Next, we consider the three possible cases in which two small leaves are found side by side. The simplest case is that in which `t1` and `t2` are the leaves in question. We then use the function `append_string`:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```
| Str (s1, ofs1, len1), Str (s2, ofs2, len2)
  when len1 <= small_length && len2 <= small_length ->
    append_string s1 ofs1 len1 s2 ofs2 len2
```

The two other cases are similar:

```
| App (t1, Str (s1, ofs1, len1), _), Str (s2, ofs2, len2)
  when ... -> ...
| Str (s1, ofs1, len1), App (Str (s2, ofs2, len2), t2, _)
  when ... -> ...
```

Finally, the general case is simply the application of the constructor App, as we discussed above:

```
| t1, t2 ->
  App (t1, t2, length t1 + length t2)
```

The entire code of `append` is given in program 27.

In the rest of the section, we will use the `infix` operator `++` to denote rope concatenation.

```
let (++) = append
```

The second idea that allows us to control the height of ropes consists in *rebalancing* the underlying trees. We could implement balancing incrementally as the rope is constructed, using for example the same technique as for AVL trees (see chapter 5). It would then be necessary to modify the last line of the function `append`, to invoke a balancing function instead of the constructor App. We may equally conceive of an *a posteriori* rebalancing implemented either selectively, when the height of the tree becomes too large, or explicitly, when the user requests it. Exercises 4.17–4.20 propose different ways of implementing an *a posteriori* rebalancing.

## Subrope Extraction

The next operation consists in extracting a rope fragment, defined by an offset and a length. Extraction consists in retaining only those parts of the rope that are within this fragment, possibly reconstructing `Str` nodes that partially

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 27 — Concatenation of Two Ropes

```pascal
let small_length = 256

let append_string s1 ofs1 len1 s2 ofs2 len2 =
    Str (S.append (S.sub s1 ofs1 len1) (S.sub s2 ofs2 len2)),
    0, len1 + len2)

let append t1 t2 = match t1, t2 with
| Str (_,_,0), t | t, Str (_,_,0) ->
    t
| Str (s1, ofs1, len1), Str (s2, ofs2, len2)
    when len1 <= small_length && len2 <= small_length ->
        append_string s1 ofs1 len1 s2 ofs2 len2
| App (t1, Str (s1, ofs1, len1), _), Str (s2, ofs2, len2)
    when len1 <= small_length && len2 <= small_length ->
        App (t1, append_string s1 ofs1 len1 s2 ofs2 len2,
              length t1 + len1 + len2)
| Str (s1, ofs1, len1), App (Str (s2, ofs2, len2), t2, _)
    when len1 <= small_length && len2 <= small_length ->
        App (append_string s1 ofs1 len1 s2 ofs2 len2, t2,
              len1 + len2 + length t2)
| t1, t2 ->
    App (t1, t2, length t1 + length t2)

let (++) = append
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
overlap it. It is in fact preferable to specify the fragment to be extracted as extending from an offset `start` (inclusive) to the offset `stop` (exclusive). We assume that this is a valid and non-empty fragment, that is:

$$0 \le start < stop \le length t.$$

The extraction function, `mksub`, begins by considering the particular case in which the fragment is the whole rope.

```hml
let rec mksub start stop t =
    if start = 0 && stop = length t then
        t
```

This allows, to the extent possible, the sharing of subropes between the result of the extraction and the initial rope. Without this special case, these subropes would all be reconstructed.

In the general case, we examine the shape of the rope `t`. If `t` is a leaf, it suffices to modify the fragment specification:

```hml
else match t with
| Str (s, ofs,_) ->
    Str (s, ofs+start, stop-start)
```

Note that this is a constant-time operation, which does not call `S.sub`, and that it shares `s` between the initial rope and the result of the extraction. For a rope of form `App`, there are three cases to be considered. The first is when the fragment is completely contained in the left subrope. It then suffices to make a recursive call.

```hml
| App (t1, t2,_) ->
    let n1 = length t1 in
    if stop <= n1 then mksub start stop t1
```

Symmetrically, the fragment may be completely contained in the right subrope.

```hml
else if start >= n1 then mksub (start-n1) (stop-n1) t2
```

Finally, the fragment may overlap both `t1` and `t2`. It suffices then to concatenate the fragment of `t1` with that of `t2`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
else mksub start n1 t1 ++ mksub 0 (stop-n1) t2

Note that neither of these fragments is empty, which respects the invariant of `mksub`. Note also that `t1` or `t2` may be completely contained in the result, in which case they will be shared by virtue of the first two lines of the function `mksub`.

Next, we define an extraction function `sub` specified by an offset `ofs` and a length `len` (similar to `String.sub` or `Array.sub`). It verifies the validity of the arguments, and then handles the special case of an empty fragment or calls the recursive function `mksub`.

let sub t ofs len =
let stop = ofs + len in
if ofs < 0 || len < 0 || stop > length t then invalid_arg "sub";
if len = 0 then empty else mksub ofs stop t

The entire code is given in program 28.

## Update Operations

We now consider several operations to insert or delete characters in a rope. Since ropes are persistent, these operations do not mutate them, but instead return new ropes.

Let us consider for example the operation `set`, which inserts the character `c` at offset `i` in a rope `t`. We begin by verifying that the offset `i` is valid, that is, `0 <= i < length t`.

let set t i c =
let n = length t in
if i < 0 || i >= n then invalid_arg "set";

Next, it suffices to extract the subropes to the left and right of the offset `i`, and use concatenation to insert the character `c`.

sub t 0 i ++ make 1 c ++ sub t (i + 1) (n - i - 1)

We note, however, that this solution is not optimal, since it performs two recursive traversals of the rope where one would have sufficed. Exercise 4.16 proposes an improvement in this regard.

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

```pascal
let rec mksub start stop t =
    if start = 0 && stop = length t then
        t
    else match t with
        | Str (s, ofs,_) ->
            Str (s, ofs+start, stop-start)
        | App (t1, t2,_) ->
            let n1 = length t1 in
                if stop <= n1 then mksub start stop t1
                else if start >= n1 then mksub (start-n1) (stop-n1) t2
                else mksub start n1 t1 ++ mksub 0 (stop-n1) t2

let sub t ofs len =
    let stop = ofs + len in
    if ofs < 0 || len < 0 || stop > length t then invalid_arg "sub";
    if len = 0 then empty else mksub ofs stop t
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 29 — Update Operations on Ropes

```pascal
let set t i c =
  let n = length t in
  if i < 0 || i >= n then invalid_arg "set";
  sub t 0 i ++ make 1 c ++ sub t (i + 1) (n - i - 1)

let insert t i r =
  let n = length t in
  if i < 0 || i > n then invalid_arg "insert";
  sub t 0 i ++ r ++ sub t i (n - i)

let insert_char t i c =
  insert t i (make 1 c)

let delete_char t i =
  let n = length t in
  if i < 0 || i >= n then invalid_arg "delete_char";
  sub t 0 i ++ sub t (i + 1) (n - i - 1)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We may similarly define operations `insert` (which inserts a rope within another at a given offset), `insert_char` (which inserts a character into a rope), and `delete_char` (which deletes the *i*-th character of a rope). The entire code of the four operations is given in program ?? (see previous page). This concludes our discussion of the functor defining ropes.

## Application: Text Editor

Ropes are an ideal structure for text editors, in particular to support very long texts, which are rarely handled well by text editors, including the best-known ones.

Rather than using a single rope to represent the text to be edited in its entirety, we will use our functor for greater flexibility. Handling lines of text using a single rope is awkward: Line breaks have to be found, or their offsets recorded in a table that must be maintained in sync with the text. Instead, we can use ropes whose elements are characters to represent lines, and a rope whose elements are lines to represent the entire text.

We therefore begin by constructing a rope structure for lines. The argument of the functor `Make` is based on the OCaml module `String`:

```ocaml
module Str = struct
  include String
  let get = unsafe_get
  type char = Char.t
  let empty = ""
  let append = (^
end
```

Note that we use `String.unsafe_get` rather than `String.get`, because every access to the characters of a string contained in a rope is guaranteed to be valid. We can thus avoid unnecessary checks. Ropes are obtained by applying the functor `Make` as follows:

```ocaml
module Line = Make(Str)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Next, we construct another rope structure for the whole text, whose “characters” are lines. For this, it suffices to apply the functor `Make` once again, this time using arrays for the leaves of our ropes.

```python
module Text = Make(struct
    type char = Line.t
    type t = Line.t array
    let empty = [||]
    let length = Array.length
    let make = Array.make
    let append = Array.append
    let get = Array.unsafe_get
    let sub = Array.sub
end)
```

We see here the usefulness of defining ropes as a functor, which allows us to apply it twice on different arguments.

Let us assume, for simplicity's sake, that the text manipulated by the editor is stored in a reference containing a rope of type `Text.t`.

```hsl
let text = ref ...
```

To insert a character `c` at offset `ofs` in line `l` of the text, it suffices to retrieve the line with `Text.get`, to modify it using `Line.insert`, and finally to update the text using `Text.set`:

```hsl
let insert_char l ofs c =
    let line = Text.get !text l in
    let line' = Line.insert_char line ofs c in
    text := Text.set !text l line'
```

Similarly, to delete a character:

```hsl
let delete_char l ofs =
    let line = Text.get !text l in
    let line' = Line.delete_char line ofs in
    text := Text.set !text l line'
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Finally, to insert a new line at offset `ofs` in line 1 of the text, it suffices to cut the line 1 at offset `ofs` with two calls to `Line.sub`, then insert the prefix in line 1 using `Text.insert`, and to place the suffix in line 1+1 using `Text.set`:

```perl
let insert_newline 1 ofs =
    let line = Text.get !text 1 in
    let prefix = Line.sub line 0 ofs in
    let suffix = Line.sub line ofs (Line.length line - ofs) in
    let r = Text.insert_char !text 1 prefix in
    text := Text.set r (1 + 1) suffix
```

Note that it is not necessary to “shift” all the lines: we use insertion in the rope of lines, just as we used insertion in the ropes of characters in `insert_char`.

## Remark

Just as concatenation operations are suspended in ropes, extraction operations too may be suspended. The resulting OCaml type would be as follows:

``` OCaml
type t =
    | Str of S.t
    | Sub of t * int * int
    | App of t * t * int
```

Everything then depends on the strategy used to choose between performing the concatenation and subrope operations immediately or suspending them.

The extraction operation may, in fact, be suspended “for free,” by applying the functor `Make` repeatedly to its own result, as follows:

``` OCaml
module R1 = Make(Str)
module R2 = Make(R1)
...
```

In the ropes of the module `R2`, the leaves are ropes of `R1`. Hence, the function `R1.sub` is only called when the leaf becomes sufficiently small. As long as this is not the case, the operation remains suspended. With a small abuse of notation, the types `R1.t` and `R2.t` could be said to correspond to the following definitions:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```pascal
type R1.t =
  | R1.Str of string * int * int
  | R1.App of R1.t * R1.t * int
type R2.t =
  | R2.Str of R1.t * int * int
  | R2.App of R2.t * R2.t * int
```

It is clear that the node `R2.Str` suspends the extraction on a value of type `R1.t`. By iterating this process, we obtain a type equivalent to the preceding type `t`.

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

**For Further Information**

The rope data structure was introduced by Boehm, Atkinson, and Plass [5] in relation to the development of the Cedar language. Their article notably proposes an *a posteriori* rope rebalancing algorithm based on the numbers of the Fibonacci sequence (see exercise 4.18).

## 4.4 Persistent Arrays

This section presents a *persistent array* data structure. Throughout this section, we use the term “array” in its usual sense, to designate arrays that may be modified in-place. In all other cases, we use the term “persistent array.”

The signature of persistent arrays is given in program 30. This is exactly the same signature as for arrays, except that the function `set` returns a new persistent array, without changing its argument.

A desirable property of persistent arrays is that they provide operations `set` and `get` with the same efficiency—$O(1)$—as arrays, at least as long as their persistent nature is not used. However, we accept that there is a price to be paid for access to previous versions of the array. This section presents a data structure that has this property.

The basic idea consists in using an array for the most recent version of the persistent array, together with extra information to allow us to go back to previous versions. To this end, we introduce the following two mutually recursive types:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 30 — Signature of Persistent Arrays

```pascal
module type PersistentArray = sig
type 'a t
  val init : int -> (int -> 'a) -> 'a t
  val length : 'a t -> int
  val get : 'a t -> int -> 'a
  val set : 'a t -> int -> 'a -> 'a t
  val iteri : (int -> 'a -> unit) -> 'a t -> unit
end
```

```pascal
type 'a t = 'a data ref
and 'a data =
  | Arr of 'a array
  | Diff of int * 'a * 'a t
```

The type `'a t` is that of persistent arrays. It involves a reference to data of type `'a data`, which indicates its nature: either an immediate value `Arr a`, where `a` is an array, or an indirection `Diff (i, v, p)`, representing a persistent array elementwise identical to the persistent array `p`, except at index `i` where the value `v` is to be found.

We illustrate the use of this data structure with an example. Consider the following series of declarations that define a persistent array `pa0`, then two others, `pa1` and `pa2`, obtained by two successive updates:

```pascal
let pa0 = init 7 (fun i -> Char.chr (Char.code 'a' + i))
let pa1 = set pa0 1 'h'
let pa2 = set pa1 2 'i'
```

The situation after these three declarations is the following:

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

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The last constructed persistent array, `pa2`, is a reference containing the value `Arr [|'a';'h';'i';'d';'e';'f';'g'|]`. The persistent array `pa1` is a reference containing `Diff (2, 'c', pa2)`, and the array `pa0`, a reference containing `Diff (1, 'b', pa1)`. Let us assume now that we construct a fourth array `pa3` as follows:

```javascript
let pa3 = set pa1 2 'j'
```

We proceed in two steps: We begin by making sure that the persistent array on which we perform the operation, `pa1`, is of the form `Arr a`. For this, we invert the chain of `Diff` nodes that leads from `pa1` to the array `a`. We then have the following situation:

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

In the second step, we create a new reference for `pa3`, containing `Arr a`, where `a` has been modified to contain `'j'` in the second cell. We finish by modifying the reference `pa1` so that it now contains `Diff (2, 'c', pa3)`. The final situation is therefore as follows:

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

We will now describe the code of the different operations on persistent arrays. The creation of a new persistent array is straightforward:

```javascript
let init n f = ref (Arr (Array.init n f))
```

For all other operations, we need a function `reroot` to invert a chain of `Diff` nodes so as to ensure that a persistent array `pa` is of the form `Arr a`. We write it as a recursive function `reroot : 'a t -> 'a array` that ensures this inversion

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
of pointers and returns the array *a*. If *pa* is a reference to a value of form *Arr a*, it suffices to return *a*.

```h
let rec reroot pa = match !pa with
| Arr a ->
  a
```

If, however, *pa* is a reference to a value of form *Diff (i, v, pa')*, we begin by calling *reroot* recursively on the persistent array *pa'*.

```h
| Diff (i, v, pa') ->
  let a = reroot pa' in
```

It is then guaranteed that *pa'* is a reference containing *Arr a*. It now suffices to exchange the roles of *pa'* and *pa*, that is, to store the value *Arr a* in *pa*, after having modified *a* in place, and to store a value *Diff* in *pa'*, indicating the previous value contained in *a*.

```h
let old = a.(i) in
a.(i) <- v;
pa := Arr a;
pa' := Diff (i, old, pa);
a
```

The definitions of the *length* and *get* operations are straightforward if we use their equivalents in the *Array* module together with the *reroot* function.

```h
let length pa = Array.length (reroot pa)
let get pa i = (reroot pa).(i)
```

The operation *iteri* is implemented by using the function *Array.iteri*, which applies a function to all the elements of an array and to their indices.

```h
let iteri f pa = Array.iteri f (reroot pa)
```

The function *set* remains to be written. It constructs a new persistent array based on an existing persistent array *pa*, an index *i* and value *v*. We begin by calling *reroot* on *pa*.

```h
let set pa i v =
  let a = reroot pa in
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We then proceed as we did in case of the function `reroot`, except that we construct a *new* reference for the result:

```hl
let old = a.(i) in
a.(i) <- v;
let res = ref (Arr a) in
pa := Diff (i, old, res);
res
```

Note that at the end of this operation, the persistent array `pa` is one indirection away from the array `Arr a`. The entire code of persistent arrays is given in program 31.

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

**For Further Information**

The persistent array data structure is attributed to Henry Baker, who used it to represent environments in Lisp closures efficiently [11, 4].

## 4.5 Exercises

### Resizeable Arrays

4.1 Modify the function `create` so that it takes an argument `increment` of type `int option` specifying a resizing strategy. If this argument is `None`, the function `resize` applies the preceding strategy (doubling the size of the array). If, on the other hand, `increment` is `Some n`, then `resize` increases the size of the array by `n` elements (or more if necessary).

4.2 We may sometimes wish to reduce the size of the array, for example when it is large compared with the number of elements actually in use or if it occupies a lot of memory. Modify the function `resize` so that it halves the size of the array when the number of elements is less than a quarter of the size of the array. Show that the amortized complexity remains $O(1)$.

4.3 Use a resizeable array to propose a stack structure with the following interface:

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

```pascal
type 'a t = 'a data ref
and 'a data =
  | Arr of 'a array
  | Diff of int * 'a * 'a t

let init n f = ref (Arr (Array.init n f))

let rec reroot pa = match !pa with
  | Arr a ->
    a
  | Diff (i, v, pa') ->
    let a = reroot pa' in
    let old = a.(i) in
    a.(i) <- v;
    pa := Arr a;
    pa' := Diff (i, old, pa);
    a

let length pa = Array.length (reroot pa)

let get pa i = (reroot pa).(i)

let iteri f pa = Array.iteri f (reroot pa)

let set pa i v =
  let a = reroot pa in
  let old = a.(i) in
  a.(i) <- v;
  let res = ref (Arr a) in
  pa := Diff (i, old, res);
  res
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```python
module type Stack = sig
    type 'a t
    val make : int -> 'a -> 'a t
    val length : 'a t -> int
    val push : 'a t -> 'a -> unit
    val pop : 'a t -> 'a
end
```

The call to `make` and `d` creates a stack containing `n` copies of the value `d`. The function `pop` raises an exception when the stack is empty.

4.4 In the context of the preceding exercise, show that `n` calls to the operations `push` and `pop` on a given queue have total cost $O(n)$.

Bit Vectors

4.5 Justify the fact that the expression `x land -x` extracts the low-order set bit of `x` for a non-zero integer `x`.

4.6 Write a function `ntz`: `int -> int` that calculates the number of low-order zero bits of its argument. Hint: You can tabulate this function over a byte and then use binary search.

4.7 Write a function `blit_bits` that copies bits `i` to `i + n - 1` of an integer `x` to the position `j` of a bit vector `v`, that is, so that we have for every index `k` in `v`:

$$ (\text{blit\_bits } x \text{ in } v \text{ j})_k = \begin{cases} x_{i+k-j} & \text{if } j \le k < j + n, \\ v_k & \text{otherwise} \end{cases} $$

We will assume that the intervals `i..i + n - 1` and `j..j + n - 1` are valid for `x` and `v`, respectively.

4.8 Using the previous exercise, derive a function `blit` that copies the bits `i1..i1 + n - 1` of a bit vector `v1` into a bit vector `v2` at position `i2`.

4.9 Using the preceding function `blit`, write a function `sub` that extracts the bits `i..i + n - 1` of an array in the form of a new bit vector of size `n`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
**4.10** Still using `blit`, write a function `append` that implements the concatenation of two bit vectors.

**4.11** Write a function `fill` that assigns a constant value (0 or 1, given in the form of a boolean) to bits $i..i + n - 1$ of an array. You can reuse the function `blit_bits` with $x$ equal to 0 or $-1$.

**4.12** Write a function `pop`: `int -> int` that counts the number of set bits of an integer by tabulating its values for all 8-bit integers. This function will be four times faster than the one given in section *4.2 Bit Vectors*.

**4.13** The idea of a bit vector may be exploited to represent a subset of $\{0, 1, ..., 30\}$ (respectively, $\{0, 1, ..., 62\}$ in a 64-bit architecture) by a single integer. This is, moreover, a persistent data structure. Use this idea to write a module of the following form:

```python
module Bitset : Set.S type elt = int
```

## Ropes

**4.14** Add a function to the functor `Make` that allows you to iterate over all leaves of a rope in infix order:

```hkl
iter_leaves : (S.t -> int -> int -> unit) -> t -> unit
```

Each leaf is a string fragment corresponding to the three arguments of the constructor `Str`.

**4.15** Add the parameter `small_length` as an argument of the functor `Make`.

**4.16** Rewrite the functions `set`, `insert`, and `delete_char` so that they perform only one recursive traversal of the rope.

**4.17** In this and the following two exercises, we propose methods to rebalance ropes *a posteriori*, that is, functions of the type:

```hkl
val balance : t -> t
```

A simple method consists in constructing the list of all the leaves of the rope in infix order and then constructing a complete binary tree based on this list. Write a function `balance` following this idea.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
**4.18** The balancing algorithm proposed in the above exercise minimizes the height of the rope (as a tree) but does not take into consideration the length of the different leaves. If a leaf contains a large number of characters, it would be worthwhile to bring it closer to the root.

The article introducing ropes [5] proposes the following balancing method: Use an array **a** of ropes, verifying the following invariant: if the rope **a**.(i) is non-empty, its length belongs to the interval $[F_i, F_{i+1}$[, where $F_i$ is the i-th term of the Fibonacci series, defined by $F_0 = F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$ for all $n \ge 0$.

Initially, all the ropes in **a** are empty. We then successively insert in **a** every leaf of the rope to be balanced, in infix order, in the following manner, starting from $i = 2$:

1. Let $r$ be the rope obtained by concatenating the rope to be inserted with **a**.(i).

2. If the length of $r$ is in $[F_i, F_{i+1}$[, assign $r$ to **a**.(i) and then stop.

3. Otherwise, assign the empty rope to **a**.(i), increase $i$, and go back to step 1 with $r$ as the rope to be inserted.

Once all leaves are inserted, the result is the concatenation of all the ropes in **a**. Write a function **balance** that implements this algorithm.

**4.19** Let $r$ be the rope obtained by the algorithm described in the preceding exercise, $n$ its length, and $h$ its height, where the height of a rope is defined by $h(\text{Str}_-) = 0$ and $h(\text{App}(r_1, r_2, _)) = 1 + \max(h(r_1), h(r_2))$. Show that $n \ge F_{h+1}$. (Hint: Show that $h(\text{a.}(i)) \le i - 2$ for every $i$..) From this, deduce that the average distance of a character to the root of the rope $r$ is less than or equal to $\log_{\phi}(n) + K$ for a certain constant $K$, where $\phi$ is the golden ratio $(1 + \sqrt{5})/2$.

**4.20** This exercise presents an optimal strategy to rebalance a rope $c_0$, known as the Garsia-Wachs algorithm. The algorithm acts on a list of ropes $q$ equal to $\langle q_0, q_1, \dots, q_m \rangle$, as follows:

1. Initially, the list $q$ is the list of leaves of $c_0$, in infix order.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
2. As long as the list $q$ contains at least two elements,

(a) determine the smallest index $i$, if it exists, such that $length \ q_i \leq length \ q_{i+1}$; otherwise let $i = m$;

(b) remove $q_{i-1}$ and $q_i$ from the list $q$ and form their concatenation $c$;

(c) determine the largest index $j$, if it exists, such that $j < i$ and $length \ q_{j-1} \geq length \ c$; otherwise let $j = 0$;

(d) insert $c$ in the list $q$ just after $q_{j-1}$.

3. Let $c_1$ be the unique element left in $q$. This rope is optimal, but its leaves are not in the same order as in $c_0$. The result is the rope $c_2$ that has the same leaves as $c_0$ and $c_1$, in the same order as in $c_0$, and at the same depth as in $c_1$.

Write a function `balance` that implements this algorithm. For more details on this algorithm, consult *The Art of Computer Programming* [15, vol. 3, sec. 6.2.2].

## Persistent Arrays

4.21 You may have noticed that the code of `reroot` and of `set` unnecessarily recreates the value `Arr a`. Modify the two operations to avoid this.

4.22 Simplify the function `set` in the case of a call `set pa i v`, where the index `i` already maps to `v` in `pa`.

4.23 The recursive call in the function `reroot` is not a tail call. This can create problems if a persistent array is the result of a large number of modifications. Rewrite the function `reroot` so that it contains only tail-recursive calls.

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

Sets and dictionaries are the most frequently used data structures. This chapter presents several ways of implementing sets. In each case, we discuss how they may be adapted for dictionaries. Some data structures may be used with elements of any type while others are more specialized, applicable to elements of a particular shape (for example, lists) or type (for example, integers).

Some of these data structures are presented in a persistent version and others in an imperative version. This is an arbitrary choice. Other choices are often possible, such as persistent hash tables or imperative AVL trees. Some of these variations are proposed in the exercises.

The choice of a data structure does not depend solely on its persistent or imperative character. Other criteria determine this choice, such as the available operations on the elements (for example, the existence of a total order), the operations provided by the data structure (for example, a union operation), or their respective cost (for example, the possibility of constructing a set in linear time).
## 5.1 Binary Search Trees

In this section, we implement persistent sets. A minimal signature for such sets, `PersistentSet`, is given in program 32. The type of the elements is `elt` and that of the sets is `t`. The empty set is represented by the value `empty`. The operations `add` and `mem` respectively add an element and test the membership of an element in a set. The function `min_elt` returns the smallest element of a set, if such an element exists, and raises the exception `Not_found` otherwise. The function `remove` removes an element from a set, if such an element is present, and returns the same set otherwise. Finally, the operation `cardinal` returns the number of elements of a set. Of course, a more realistic signature would contain additional operations, such as union, intersection, and difference.

The data structure chosen here to implement this signature is that of a *binary search tree*, that is, a binary tree such that every element contained in a node is larger than every element in its left subtree and smaller than every element in its right subtree. This organization allows searching for an element in time proportionate to the height of the tree. This tree structure assumes, however, that the elements can be compared to one another. For this, we require a comparison function `compare`: `elt -> elt -> int` such as:

$$ \texttt{compare x y est} \begin{cases} < 0 & \text{if } x \text{ is strictly smaller than } y, \\ = 0 & \text{if } x \text{ is equal to } y, \\ > 0 & \text{if } x \text{ is strictly larger than } y. \end{cases} $$

We gather the type `elt` and the declaration of the function `compare` in a signature `Ordered` shown in program 33. The code is then written as a functor parametrized by a module of signature `Ordered`:

```python
module Make(X : Ordered) : PersistentSet with type elt = X.t =
    struct
```

The signature of the module returned by this functor is `PersistentSet`, where we specify that the type `elt` of the elements is the type `X.t`.

Accordingly, in the body of the functor, we begin by introducing the type `elt` as a synonym of the type `X.t`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 32 — Signature of Persistent Sets

```python
module type PersistentSet = sig

type elt

type t

val empty : t

val add : elt -> t -> t

val mem : elt -> t -> bool

val min_elt : t -> elt

val remove : elt -> t -> t

val cardinal : t -> int

end
```

Program 33 — Signature of Ordered Types

```python
module type Ordered = sig

type t

val compare: t -> t -> int

end
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_73.png" /><figcaption>Figure 5.1: Two representations of the same binary search tree.</figcaption></figure>

```hkl
type elt = X.t
```

We then define the type `t` of sets as that of binary trees whose internal nodes contain a value of type `elt`:

```hkl
type t = Empty | Node of t * elt * t
```

Consider the following OCaml value:

```hkl
Node (Node (Node (Empty, 'B', Empty), 'D', Empty),
      'E',
      Node (Empty, 'F', Empty))
```

It corresponds to the left tree in figure 5.1, where only the value of type `elt` in each node is shown, and where `Empty` is represented by `⊥`.

In what follows, we will not draw the children of a node when they are both empty, as depicted in the right tree of the figure.

The value `empty`, denoting the empty set, is simply a synonym for the constructor `Empty`, that is, the empty tree.

```hkl
let empty = Empty
```

## Smallest Element

The structure of a binary search tree makes it easy to retrieve its smallest element. It suffices to descend along the left branch as long as possible. The function `min_elt` implements this traversal.

```hkl
let rec min_elt = function
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```
| Empty -> raise Not_found
| Node (Empty, v,_) -> v
| Node (l,_,_) -> min_elt l
```

Rather than the predefined exception `Not_found`, we could have declared and used an exception specific to binary search trees.

## Searching for an Element

Searching for an element `x` in a binary search tree proceeds recursively as follows: If the tree is empty, we return `false`.

```hl
let rec mem x = function
  | Empty ->
    false
```

Otherwise, we compare `x` with the element `v` situated at the root of the tree. If they are equal, the search finishes successfully. If `x < v`, we continue recursively down the left subtree and, otherwise, down the right subtree.

```
| Node (l, v, r) ->
  let c = X comparing x v in
  c = 0 || if c < 0 then mem x l else mem x r
```

## Inserting an Element

Inserting an element `x` in a binary search tree `t` consists in finding the location of `x` in `t`, following the same principle as when searching for an element. If `t` is empty, it suffices to construct a tree that contains only `x`.

```hl
let rec add x t =
  match t with
  | Empty ->
    Node (Empty, x, Empty)
```

Otherwise, we compare the element `x` with the root `v` of `t`. If they are equal, we return the tree `t` unchanged to avoid introducing a duplicate.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
| Node (l, v, r) ->
let c = X compares x v in
if c = 0 then t

Otherwise, we recursively pursue the insertion to the left or to the right,
depending on the result of the comparison.

else if c < 0 then Node (add x l, v, r)
else Node (l, v, add x r)

Of course, this implementation of the insertion function may lead to highly
unbalanced trees. For example, if we successively add F, E, D, and B to the
empty tree, we get the “comb” shown in figure 5.2.

<figure><img src="image_74.png" /><figcaption>Figure 5.2: A binary search tree shaped like a comb.</figcaption></figure>

Such shapes degrade the efficiency of subsequent search and insertion op-
erations. The worst case corresponds to that of the comb where, as shown in
the example, each internal node has only one non-empty subtree. Operations in
such trees are then proportionate to the number of elements. In the following
section, we will see that it is possible to limit the height of a binary search tree
so that it remains logarithmic with respect to the number of elements. The
complete code of the insertion function is given in program 34.

Removing an Element

To remove an element x from a binary search tree t, we proceed in the same
manner as when searching or inserting an element, that is, by recursive descent
towards the possible location of x. If t is empty, it suffices to return the empty
tree.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 34 — Binary Search Trees (1/2)

```pascal
type t = Empty | Node of t * elt * t

let rec min_elt = function
  | Empty -> raise Not_found
  | Node (Empty, v, __) -> v
  | Node (1, __, __) -> min_elt 1

let rec mem x = function
  | Empty ->
    false
  | Node (1, v, r) ->
    let c = X comparisons x v in
    c = 0 || if c < 0 then mem x 1 else mem x r

let rec add x t =
  match t with
  | Empty ->
    Node (Empty, x, Empty)
  | Node (1, v, r) ->
    let c = X comparisons x v in
    if c = 0 then t
    else if c < 0 then Node (add x 1, v, r)
    else Node (1, v, add x r)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```h
let rec remove x = function
  | Empty ->
    Empty
```

Otherwise, we compare `x` to the root `v` of `t`. If they are equal, we face a problem: It is necessary to remove `v`, that is, to construct a tree from the left and the right subtrees of `t`. To implement this operation, we assume that we have written a function `merge` that performs this merging.

```h
| Node (l, v, r) ->
  let c = X compares x v in
  if c = 0 then merge l r
```

If `x` is different from `v`, we descend recursively along the left or the right subtree to remove `x`. The code is similar to that of an insertion.

```h
else if c < 0 then Node (remove x l, v, r)
else Node (l, v, remove x r)
```

The function `merge`, which merges two trees `l` and `r`, remains to be written. The difficulty lies in determining a root for the resulting tree. One way of proceeding consists in choosing the smallest element of `r`. Its value is obtained using the function `min_elt` written earlier. We must then remove this element from `r`, but this is precisely the operation that we are trying to implement.

Fortunately, the removal of the smallest element of a binary search tree is much simpler to implement than the removal of an arbitrary element. Let us write a function `remove_min_elt` for this. If the tree is empty, there is nothing more to be done.

```h
let rec remove_min_elt = function
  | Empty -> Empty
```

If not, and if there is no left subtree, then the root is the smallest element, and we return the right subtree.

```h
| Node (Empty,_, r) -> r
```

Otherwise, we recursively remove the smallest element from the left subtree.

```h
| Node (l, v, r) -> Node (remove_min_elt l, v, r)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 35 — Binary Search Trees (2/2)

```javascript
let rec remove_min_elt = function
  | Empty -> Empty
  | Node (Empty,_, r) -> r
  | Node (l, v, r) -> Node (remove_min_elt l, v, r)
```

```javascript
let merge t1 t2 = match t1, t2 with
  | Empty, t | t, Empty -> t
  | _ -> Node (t1, min_elt t2, remove_min_elt t2)
```

```javascript
let rec remove x = function
  | Empty ->
    Empty
  | Node (l, v, r) ->
    let c = X compares x v in
      if c = 0 then merge l r
      else if c < 0 then Node (remove x l, v, r)
      else Node (l, v, remove x r)
```

We are now ready to write the function `merge`. If one of its two arguments is empty, we return the other. Otherwise, we use `min_elt` and `remove_min_elt`, and apply the idea mentioned previously.

```javascript
let merge t1 t2 = match t1, t2 with
  | Empty, t | t, Empty -> t
  | _ -> Node (t1, min_elt t2, remove_min_elt t2)
```

The complete code for removing an element is given in program 35. Exercise 5.7 proposes a slight improvement, which consists in avoiding the reconstruction of the tree when the element to be removed is not actually present. This optimization is also applicable in the function `add`.

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

We do not show here how to adapt this data structure to implement dictionaries since this will be done in the following section for balanced binary trees.

## 5.2 AVL Trees

As we saw in the previous section, the height of a binary search tree can be as high as the number of elements it contains, which is the case of the comb. The efficiency of each operation is directly affected by this. The problem can be resolved by *balancing* the binary search tree, that is, by trying to make its height as small as possible. In practice, we look for a solution that is not too costly at construction time, but which guarantees that the two subtrees of each node contain the same number of elements up to a small multiplicative factor. The solution discussed here is that of AVL trees, where the difference in heights of the left and right subtrees of each node is never allowed to exceed 1.

We begin by modifying the type of binary search trees to store the height of the tree as the fourth argument of the constructor `Node`.

```h
type t = Empty | Node of t * elt * t * int
```

Consider the following tree BDEF:

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

It is represented by the following OCaml value:

```h
Node (Node (Node (Empty, 'B', Empty, 1), 'D', Empty, 2),
        'E',
        Node (Empty, 'F', Empty, 1),
        3)
```

To manipulate the height of an AVL tree, it is convenient to introduce a function to retrieve it:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
```h
let height = function
  | Empty -> 0
  | Node (/, /, /, h) -> h
```

It is similarly useful to introduce a function that creates a new node while simultaneously computing its height:

```h
let node l v r =
  Node (l, v, r, 1 + max (height l) (height r))
```

Such a function is what we call a *smart constructor*. It will be used in what follows instead of the constructor `Node`. Of course, the height computed by `node` is correct only if the heights stored in `l` and `r` are also correct. This will be guaranteed by making the type of AVL trees abstract.

## Smallest Element and Membership Testing

As an AVL tree is a binary search tree, the functions `min_elt` and `mem` remain identical to those of program 34 (see page 213). The only difference is that they discard the fourth argument of the `Node` constructor.

## Balancing

We illustrate the balancing of an AVL tree with the help of an example. If we insert the element `A` into the tree `BDEF`, we obtain the following tree `ABDEF`:

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

This tree is not balanced since the difference in height between the left and right subtrees of the node `E` is two. Nevertheless, it is easy to restore the balance of the tree. This can be done by performing local transformations that

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_77.png" /><figcaption>Figure 5.3: Right rotation in an AVL tree.</figcaption></figure>

preserve the binary search tree property. An example of such an operation is *right rotation*, illustrated in figure 5.3.

This operation replaces the root **v** by the root **lv** of the left subtree and shifts the subtree **lr** containing the elements between **lv** and **v**. Note that this operation modifies only two nodes in the tree structure. The binary search tree property is preserved: the subtree **ll** remains to the left of **lv**; the subtree **r** remains to the right of **v**; and the subtree **lr** remains to the right of **lv** and to the left of **v**. A left rotation may be performed symmetrically.

Thus, the tree **ABDEF** may be rebalanced by performing a right rotation on the subtree with root **D**. We then obtain the following tree, which satisfies the **AVL condition**.

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

A simple left or right rotation does not necessarily suffice to rebalance the tree. For example, if we insert **C**, we obtain the following tree, which is not an **AVL tree**.

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

We can then try to perform a right rotation at the root E or a left rotation at the node B. However, neither operation yields an AVL tree.

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

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

Nevertheless, the tree on the right can be easily rebalanced by performing a further right rotation at the root E. We obtain the following AVL tree:

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

This double operation is called *left-right rotation*. Needless to say, there is also a symmetrical right-left rotation.

These four operations, that is, the two simple rotations and the two double rotations, suffice to rebalance any AVL tree following an insertion operation. We gather the rebalancing code in a *smart constructor balance* with the following type:

```h
val balance : t -> elt -> t -> t
```

It behaves exactly like the function `node`, except that it also guarantees that the result will be balanced.

We begin by calculating the heights `hl` and `hr` of the left and right subtrees, and consider first the case in which the imbalance is due to the left subtree `l`:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_83.png" /><figcaption>Figure 5.4: Simple rotation in an AVL tree.</figcaption></figure>

<figure><img src="image_84.png" /><figcaption>Figure 5.5: Double rotation in an AVL tree.</figcaption></figure>

```h
let balance l v r =
    let hl = height l in
    let hr = height r in
    if hl > hr + 1 then begin
```

As illustrated in figure 5.4, a simple right rotation suffices if the left subtree
`ll` of `l` is at least as tall as the right subtree `lr`:

```h
match l with
| Node(ll, lv, lr,_) when height ll >= height lr ->
  node ll lv (node lr v r)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
On the other hand, if `ll` is shorter than `lr`, we must perform a left-right double rotation, as illustrated in figure 5.5.

| Node(ll, lv, Node(lrl, lrv, lrr, _), _)->
  node (node ll lv lrl) lrv (node lrr v r)

Here too, the AVL property is guaranteed. Note that the imbalance can be due to either `lrl` or `lrr`, and that in both cases a left-right double rotation suffices to restore the balance.

As `l` and `r` are both assumed to be AVL trees, there is no other possible cause for imbalance when `l` is taller than `r`. This completes the pattern matching:

| _ -> assert false

The case where the imbalance is due to `r` is handled symmetrically:

end else if hr > hl + 1 then begin
  match r with
    | Node (rl, rv, rr, _ ) when height rr >= height rl ->
        node (node l v rl) rv rr
    | Node (Node(rll, rlv, rlr, _), rv, rr, _ ) ->
        node (node l v rll) rlv (node rlr rv rr)
  | _ ->
        assert false

Finally, if the heights of `l` and `r` differ by at most one, we construct the node without rebalancing:

end else
  node l v r

The complete code of the function `balance` is given in program 36.

## Insertion and Removal

We can now adapt the code for inserting an element (function `add` in program 34), replacing each application of the constructor `Node` with an application of the function `balance`. Similarly, we can adapt the code for removing

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 36 — Balancing an AVL Tree

```pascal
let balance l v r =
  let hl = height l in
  let hr = height r in
  if hl > hr + 1 then begin
    match l with
      | Node (ll, lv, lr,_) when height ll >= height lr ->
        node ll lv (node lr v r)
      | Node (ll, lv, Node (lrl, lrv, lrr, _),_) ->
        node (node ll lv lrl) lrv (node lrr v r)
      | _ ->
        assert false
  end else if hr > hl + 1 then begin
    match r with
      | Node (rl, rv, rr,_) when height rr >= height rl ->
        node (node l v rl) rv rr
      | Node (Node(rll, rlv, rlr, _), rv, rr,_) ->
        node (node l v rll) rlv (node rlr rv rr)
      | _ ->
        assert false
  end else
  node l v r
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
an element (functions `remove_min_elt`, `merge`, and `remove`), making the same modification.

The code thus obtained is given in program 37. We emphasize that the adaptions above only involve simple substitutions.

## Comparison of Sets

The implementation of a total order on sets is important. It has the following type:

```h
val compare : t -> t -> int
```

In particular, this allows us to easily construct sets of sets by instantiating the functor `Make` several times in succession, as follows:

```h
module Int = struct
    type t = int
    let compare = Stdlib comparisons
end
module IntSet = Make(Int)
module IntSetSet = Make(IntSet)
```

The comparison on sets cannot be done simply by using `Stdlib comparisons`. Indeed, two binary search trees may contain the same elements without having the same structure. A simple solution would be to construct the list of elements of each tree in the infix order and then compare them. This is, however, very inefficient: On the one hand, constructing the list requires a lot of memory. On the other, this construction can be wasteful if the lists differ near the beginning. Chapter 9 proposes an efficient solution to this problem.

## Complexity

To justify the claim that AVL trees are balanced, we now show that the height of such a tree is always logarithmic in the number of elements.

Consider an AVL tree of height $h$. Let us try to estimate the number of its elements, $n$.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 37 — Insertion and Removal in an AVL Tree

```h
let rec add x = function
  | Empty ->
    Node (Empty, x, Empty, 1)
  | Node (l, v, r,_) as t ->
    let c = X compares x v in
    if c = 0 then t
    else if c < 0 then balance (add x 1) v r
    else balance l v (add x r)

let rec remove_min_elt = function
  | Empty -> Empty
  | Node (Empty,_, r,_) -> r
  | Node (l, v, r,_) -> balance (remove_min_elt 1) v r

let merge t1 t2 = match t1, t2 with
  | Empty, t | t, Empty -> t
  | _ -> balance t1 (min_elt t2) (remove_min_elt t2)

let rec remove x = function
  | Empty ->
    Empty
  | Node (l, v, r,_) ->
    let c = X compares x v in
    if c = 0 then merge l r
    else if c < 0 then balance (remove x 1) v r
    else balance l v (remove x r)
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
If the tree is perfectly balanced, then $n = 2^h - 1$. However, in general, we have only $n \le 2^h - 1$. The smallest possible value of $n$ would be attained in a tree having one subtree of height $h-1$ and the other of height $h-2$. (The reason is that, otherwise, we would still be able to remove elements from one of the two subtrees while maintaining the AVL property.) Thus, if we let $N_h$ be the smallest number of elements in an AVL tree of height $h$, we have $N_h = 1 + N_{h-1} + N_{h-2}$, which can be rewritten as $N_h + 1 = (N_{h-1} + 1) + (N_{h-2} + 1)$. Equivalently, letting $G_h = N_h + 1$, we have $G_h = G_{h-1} + G_{h-2}$. Here, we recognize the recurrence relation that defines the Fibonacci sequence. As we also have $N_0 = 0$ and $N_1 = 1$, that is, $G_0 = 1$ and $G_1 = 2$, we deduce that $G_h = F_{h+2}$, where $(F_i)$ is the Fibonacci sequence.

A mathematical result tells us that $F_i > \phi^i/\sqrt{5} - 1$, where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. Hence:

$$n \ge N_h = F_{h+2} - 1 > \phi^{h+2}/\sqrt{5} - 2,$$

that is,

$$\phi^{h+2}/\sqrt{5} < n + 2.$$

Taking the base 2 logarithm of this inequality, we deduce the desired bound on the height $h$ as a function of the number of elements $n$:

$$h \le \frac{1}{\log_2 \phi} \log_2(n+2) + \frac{\log_2 \sqrt{5}}{\log_2 \phi} - 2 \\ \approx 1,44 \log_2(n+2) - 0,33$$

An AVL tree therefore has a height that is logarithmic in the number of elements. This guarantees, in particular, $O(\log n)$ complexity for the searching, insertion, and removal operations. This also guarantees that these operations will not trigger a stack overflow.

## Dictionary

A minimal signature for a persistent dictionary is given in program 38. It is very similar to that of a set (program 32, at the start of the chapter). The type **key**

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 38 — Minimal Signature for Persistent Dictionaries

```python
module type PersistentMap = sig
    type key
    type 'a t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
end
```

of keys replaces the type `elt` of elements, for greater clarity. The type `t` is now polymorphic, its argument of type `'a` being the type of the values associated with the keys. The function `add` takes an additional argument. Finally, a new function `find` returns the value associated with a key, and raises the exception `Not_found` otherwise.

The adaptation of the structure of AVL trees to dictionaries consists in adding the value associated with the key to each node, that is:

```python
type 'a t = Empty | Node of 'a t * key * 'a * 'a t * int
```

Program 39 — Searching in an AVL Dictionary

```python
let rec find k = function
    Empty ->
        raise Not_found
  | Node (l, k', v, r, _ ) ->
      let c = X compares k k' in
      if c = 0 then v else if c < 0 then find k l else find k r
```

The function `mem` is unchanged. The function `find` follows exactly the same

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
schema as mem, except that the exception Not_found is raised if the key is not present in the dictionary. Its code is given in program 39. All the other functions on AVL trees (balance, add, etc.) are unchanged, except that elements are replaced by key/value pairs.

## Modules Set and Map

The OCaml standard library provides the modules Set and Map, implemented using AVL trees, that are almost identical to those presented in this section. The only difference is that the condition on the height of the subtrees is relaxed (2 for OCaml versus 1 here). This choice is a compromise between the construction cost and the efficiency of the operations. These libraries provide all set-theoretic operations, such as union, intersection, inclusion testing, etc.

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

**For Further Information**

AVL trees were introduced by Georgy Adelson-Velskyǐ and Evgenii Landis in 1962 [2]. The union and intersection operations on AVL trees are detailed in an article by Adams [1]. There are other techniques to balance binary search trees, notably red-black trees [7, 19] and 2-3-4 trees [21].

# 5.3 Hash Tables

An imperative data structure for sets can be implemented using an array of booleans of size *n* if the elements are integers between 0 and *n* − 1. However, this idea is not applicable to other kinds of elements, such as integers in a different range, elements of a different type, or if the number of elements is unbounded. We could also use a list, but searching is then costly.

We present here the *hash table* data structure, which combines these two approaches. The idea consists in using a function *f* that maps each element to an integer between 0 and *n* − 1. In general, it is difficult to find an *f* that is *injective*. We will thus have to handle *collisions*, that is, cases where several elements map to the same value under *f*. Rather than using an array of booleans,

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
we will use an array where each cell contains a “bucket” of elements represented as a list. Thus, an element $x$ will belong to the set if and only if it belongs to the bucket at index $f(x)$. If the function $f$ distributes the elements uniformly across the different buckets, then the search operation will be efficient.

Consider, for example, a hash table representing the following set of strings:

```
{"", "we like", "the codes", "in", "ocaml"}
```

Let us assume the table has $n = 7$ buckets. We also assume that there is a function $h$, called the *hash function*, which associates a positive integer (or zero) to each element. We can then define the function $f$ as:

$$f(s) = h(s) \mod n$$

The operation *modulo* guarantees that the value of $f$ is indeed in the range $0..n-1$. In the case of strings, we can take $h$ to be the length of the string. If we use lists to represent buckets, we then obtain the structure shown in figure 5.6. Thus, for example, bucket 2 contains the two strings `"the codes"` and `"in"`, respectively of length 9 and 2.

<figure><img src="image_86.png" /><figcaption>Figure 5.6: A hash table containing strings.</figcaption></figure>

The choice of the number of buckets $n$ and of the hash function $h$ is important. For example, if we wish to represent the set of the 80 000 words of the French dictionary, we must choose a value of $n$ that is sufficiently large, of the same order of magnitude as the number of elements, with a view to having small buckets. It is also necessary to choose a subtler function $h$ than simply the length of the string, or else only a few buckets will be used.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 40 — Signature for Imperative Sets

module type ImperativeSet = sig
type elt

type t

val create : unit -> t

val add : elt -> t -> unit

val mem : elt -> t -> bool

val remove : elt -> t -> unit

val cardinal : t -> int

end

We will now implement hash tables having the signature given in program 40. The type elt is that of the elements and the type t is that of hash tables. The function create returns a new table that is initially empty. The function add adds an element and the function remove removes an element. The function mem tests for the presence of an element and cardinal returns the number of elements in the set.

To add an element to a hash table, it is necessary to have a hash function `hash` of type `elt -> int`. To search for an element, it is also necessary to have an equality function `equal` of type `elt -> elt -> bool`. Rather than using the OCaml equality operator `=`, we prefer to let users choose their own comparison function. The two functions `hash` and `equal` must verify the following condition:

$$ \forall x, y. \quad equal x y \Rightarrow hash x = hash y $$

It is therefore natural to write hash tables as a functor parametrized by a module of type `HashType`, whose signature contains these two functions (see program 41 below).

The functor then takes the following form:

module Make(X: HashType): ImperativeSet with type elt = X.t = struct
type elt = X.t

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 41 — Signature Required for the Elements of a Hash Table

```python
module type HashType = sig
type t
val hash : t -> int
val equal : t -> t -> bool
end
```

The type `t` of hash tables could be defined as follows:

```python
type t = (elt list) array
```

However, it is also preferable to store the number of elements in the set, so as to be able to implement the function `cardinal` efficiently. We therefore use a record type containing, on the one hand, the number of elements in a field `size` and, on the other, the array of buckets in a field `buckets`

```python
type t = {
    mutable size : int;
    buckets : (elt list) array;
}
```

The function `cardinal` is then immediate.

```python
let cardinal h =
    h.size
```

To create a new hash table, it is necessary to choose the size `n` of the array. Ideally, this size should be of the same order of magnitude as the number of elements that will be stored in the table. The user could provide this information, for example in the form of an additional argument to `create`, but this is not always possible. For the present, let us therefore consider a simplified situation in which the size is an arbitrary constant.

```python
let array_length = 5003
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
We will see later how to eliminate the need for this arbitrary choice. The creation of an empty hash table consists in the creation of an array of size `array_length` containing only empty lists, and in initializing the field `size` to 0.

```h
let create () =
    { size = 0;
      buckets = Array.make array_length [];
    }
```

## Searching for an Element

To search for an element `x` within a hash table `h`, we begin by writing a function `bucket_of` that returns the bucket corresponding to `x` in `h`.

```h
let bucket_of x h =
    (X.hash x land max_int) mod (Array.length h.buckets)
```

Since the result of `mod` has the same sign as its first argument, we make sure that the latter is not negative by clearing the sign bit<fnref n="1" />.

To search for an element `x` in a table `h`, we begin by determining the index `i` of the bucket containing `x` with the function `bucket_of`.

```h
let mem x h =
    let i = bucket_of x h in
```

Next, we search for `x` in the list `h.buckets.(i)`. For this we use the equality function on the type `elt`, namely, `X equal`.

```h
List.exists (X equal x) h.buckets.(i)
```

The complete code of `mem` is given below in program 42. Since the operation of searching within a bucket is reused several times subsequently, we turn it into a function, `mem bucket`.

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

<footnote n="1">¹Another solution, notably adopted in the hash tables of the OCaml standard library, consists in using an array whose size `n` is a power of 2. The modulo operation can then be implemented with `land (n-1)`, which has the added advantage of being much cheaper than a division.</footnote>
## Program 42 — Searching in a Hash Table

```pascal
let bucket_of x h =
    (X.hash x land max_int) mod (Array.length h.buckets)

let mem bucket x b =
    List.exists (X equal x) b

let mem x h =
    let i = bucket_of x h in
    memiran x h.buckets.(i)
```

## Inserting an Element

To insert an element `x` in a table `h`, we begin by retrieving the list `b` of the
bucket that may contain `x`.

```pascal
let add x h =
    let i = bucket_of x h in
    let b = h.buckets.(i) in
```

If `x` is present in the bucket, then there is nothing more to be done. Otherwise,
we increase the field `size` and add `x` at the head of the list `b`.

```pascal
if not (memiran x b) then begin
    h.size <- h.size + 1;
    h.buckets.(i) <- x :: b
end
```

The complete code of `add` is given below in program 43.

*Note:* We could have directly added `x` to the list `b` without checking for its
presence beforehand. This would not modify the contents of the set (from the
point of view of `mem`), and insertion would then happen in $O(1)$ time. On the
other hand, it would have become impossible to keep track of the field `size`, and
the operation `cardinal` would have become more costly. Furthermore, repeated

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
insertions of the same element would have occupied more and more space in the hash table, thereby reducing the efficiency of search operations. Alternatively, to prevent duplicates, buckets may be represented using a more efficient data structure than lists. We could, for example, use AVL trees, presented in the previous section. This would nevertheless require an additional comparison function on the type `elt`.

## Program 43 — Inserting an Element into a Hash Table

```pascal
let add x h =
  let i = bucket_of x h in
  let b = h.buckets.(i) in
  if not (mem bucket x b) then begin
    h.size <- h.size + 1;
    h.buckets.(i) <- x :: b
  end
```

## Removing an Element

Removing an element from a hash table proceeds as in the insertion operation. The code of `remove` is given in program 44.

## Program 44 — Deletion from a Hash Table

```pascal
let remove x h =
  let i = bucket_of x h in
  let b = h.buckets.(i) in
  if mem bucket x b then begin
    h.size <- h.size - 1;
    h.buckets.(i) <- List.filter (fun y -> not (X equal y x)) b
  end
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
When `x` is present in the bucket `b`, it is necessary to decrease the field `size` and delete the occurrence of `x` in `b`. For this last operation, we use the function `List.filter` so as to preserve only the elements of the bucket that are distinct from `x`.

## Resizing the Array Dynamically

The efficiency of the code that we presented above is satisfactory when the order of magnitude of the number of elements of the set is known beforehand. However, our structure is too simplistic if the number of elements can increase arbitrarily. Efficiency decreases rapidly once the *load factor* of the hash table—that is, the ratio between the number of elements in the table and the size of the array—becomes large. To remedy this, it is necessary to resize the array dynamically, depending on the load factor. For example, we may double the size of the array once the load factor is greater than 1/2.

To do this, it is necessary to modify the definition of the type `t` slightly, so as to make the field `buckets` mutable.

```hkl
type t = {
    mutable size : int;
    mutable buckets : elt list array;
}
```

The initial value of the constant `array_length` remains arbitrary but will no longer impact the efficiency of the operations. The user may, nevertheless, continue to indicate an order of magnitude so as to avoid too many resizings.

The main modification is to the function `add`, where the array must be resized when the load factor becomes too large.

```hkl
let add x h =
    let n = Array.length h.buckets in
    ...
    if not (mem bucket x b) then begin
        ...
        if h.size > n/2 then resize h
    end
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The test `h.size > n/2` is done immediately after the insertion of `x`. If the condition holds, we call a function `resize` that will take care of resizing the array. This function proceeds as in section 4.1 *Resizeable Arrays*. It begins by allocating a new array `a`, of size `m = 2 × n`.

```pascal
let resize h =
  let n = Array.length h.buckets in
  let m = 2 * n in
  let a = Array.make m [] in
```

The size of the array having changed, the bucket number of an element is no longer necessarily the same due to the change in the *modulus*. It is therefore necessary to reassign each of the elements of `h` to their respective new buckets. For this, we introduce a function `rehash` that adds the element `x` into its new bucket.

```pascal
let rehash x =
  let i = (X.hash x land max_int) mod m in
  a.(i) <- x :: a.(i)
in
```

It then suffices to execute `rehash` on all the buckets of the previous array `h.buckets`:

```pascal
Array.iter (List.iter rehash) h.buckets;
```

Finally, we replace the array `h.buckets` by `a`.

```pascal
h.buckets <- a
```

The complete code of `resize` is given in program 45.

As the size of arrays is limited to `Sys.max_array_length`, it is a good idea to verify that the length of the array created by the function `resize` is not too large (see exercise 5.11).

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 45 — Resizing a Hash Table

```pascal
let resize h =
    let n = Array.length h.buckets in
    let m = 2 * n in
    let a = Array.make m [] in
    let rehash x =
        let i = (X.hash x land max_int) mod m in
        a.(i) <- x :: a.(i)
    in
    Array.iter (List.iter rehash) h.buckets;
    h.buckets <- a
```

Complexity

The complexity of the operations on a hash table obviously depends on the hash function. If, for example, this function always returns the same value, then the hash table becomes a simple list, and the operations `mem`, `add`, and `remove` all have cost $O(N)$ if the table contains $N$ elements. If, by contrast, the hash function distributes the elements uniformly over the different buckets, and if the number of buckets is sufficiently large, then we can hope that the size of each bucket will be bounded by a small constant. In this case, the complexity of each operation will be $O(1)$.

The tuning of the hash function is done empirically, for example by measuring maximal and average bucket sizes. On values such as integers, strings, or even arrays of integers, we can use the polymorphic hash function `Hashtbl.hash`, provided by the OCaml library, which gives good results. In the section 11.4 *Hash-consing*, we will see how to define an efficient hash function for more complex values, such as lists or trees.

To maintain a bounded load factor, we have shown above how to dynamically resize the hash table. Each operation that triggers a resizing obviously has cost $O(N)$, since each element has to be reintroduced individually into the new array. However, if we follow the above strategy, consisting in doubling the size of the

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
array each time, then the cost is amortized over the entire sequence of operations, exactly as in section 4.1 *Resizeable Arrays*. The operations `mem`, `add`, and `remove` therefore have amortized cost $O(1)$. A hash table is consequently an extremely efficient data structure.

## Dictionary

To adapt the hash table structure to represent dictionaries, we add the values associated with the keys into the buckets. The lists become association lists and the type `t` becomes:

```hkl
type 'a t = {
    mutable size : int;
    mutable buckets : (key * 'a) list array;
}
```

To check for the presence of a key in a list of type `(key * 'a) list`, we modify the function `mem bucket` slightly, as follows:

```hkl
let mem bucket x b =
    List.exists (fun (y,_) -> X equal x y) b
```

All the other functions are subject to similar minor modifications. The only new function that needs to be added is `find`. It looks for the value associated with a key in the corresponding bucket, which boils down to searching in an association list. We cannot use the predefined function `List.assoc`, because here we must use the equality predicate `X equal`. We therefore write a specific function, `lookup`, for this. The code of `find` is given in program 46.

## Module Hashtbl

The standard library of OCaml provides dictionaries implemented as hash tables in the form of a functor `Hashtbl.Make`, analogous to the one we just wrote.

This data structure may be used to associate several values with a single key. More precisely, it allows us to call the function `add` several times with the same key, without losing the values with which the key was previously associated. For example, if we execute the additions `add h x v1` and `add h x v2` sequentially

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 46 — Searching in an Associative Hash Table

```h
let find x h =
  let rec lookup = function
    | [] -> raise Not_found
    | (k, v) :: _ when X equal x k -> v
    | _ :: b -> lookup b
  in
let i = bucket_of x h in
lookup h.buckets.(i)
```

for a key `x` in a table `h`, then `find h x` will return `v2`. If we then perform `remove h x`, this has the effect of deleting the last binding of `x`, and `find h x` will then return `v1`. On the other hand, if we wish to replace the value `v1` by `v2`, we can use the operation `replace`.

The module `Hashtbl` also provides a polymorphic hash table data structure that relies on the polymorphic hash function `Hashtbl.hash` that has type `'a -> int` and that is compatible with the structural equality operation `=`. This way, we avoid having to use the functor `Hashtbl.Make` when the keys are, for example, values of type `int` or `string`.

## 5.4 Prefix Trees

We are concerned in this section with a data structure used to represent sets of words. By “word,” we mean here any OCaml value that can be seen as a sequence of letters. The first data type that comes to mind for such values is obviously the type `string` of strings, where the letters are values of type `char`. However, other values may also be considered as words. For example, an integer written in base 2 can be understood as a word formed of the letters `0` and `1`. More generally, we will assume that words are of type `L.t list`, where `L` is a module of signature `Letter`, given in program 47, containing a type `t` that represents letters. Apart from this type `t`, this signature assumes the existence

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_87.png" /><figcaption>Figure 5.7: Prefix tree for the set {if, in, do, done}.</figcaption></figure>

Program 47 — Minimal Signature of Letter Module

module type Letter = sig
type t
val compare: t -> t -> int
end

of a comparison function that we will need in what follows.

We use this decomposition into letters to represent sets of words with the
help of a data structure called a *prefix tree*, also known as *trie*<fnref n="2" />. In these trees,
each branch is labeled by a letter and each node contains a boolean indicating
whether the sequence of letters leading from the root of the tree to this node is
a word belonging to the set. For example, the prefix tree corresponding to the
set of words {if, in, do, done} is represented in figure 5.7.

This data structure is useful to bound the time needed to search for a word
in a set by the length of the word, independent of the number of words in the
set.

In order to avoid depending on a particular implementation of the mod-

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

<footnote n="2">²This comes from the word *retrieval*.</footnote>
Program 48 — Signature of Persistent Sets

```python
module type PersistentSet = sig
type elt
type t
val empty : t
val add : elt -> t -> t
val mem : elt -> t -> bool
val remove : elt -> t -> t
val inter : t -> t -> t
val compare : t -> t -> int
end
```

ule L, we define the prefix tree data structure as a functor parametrized by L and returning a persistent set whose signature, `PersistentSet`, is given in program 48.

```python
module Make(L: Letter): PersistentSet with type elt = L.t list =
    struct
    type elt = L.t list
```

As mentioned earlier, the type `elt` of elements is defined as a list of letters, that is, a list of type `L.t list`.

The idea behind prefix trees is to represent each node as a dictionary that associates letters with subtrees, that is, with other nodes. We begin by introducing a dictionary `M`, whose keys are letters, by applying the functor `Map.Make` to the module `L`.

```python
module M = Map.Make(L)
```

We can then define the type `t` of nodes as follows:

```python
type t = { word : bool; branches : t M.t }
```

The field `word` contains the boolean value indicating the presence of a word in the set. The field `branches` contains the children of the node.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
## Program 49 — Structure of a Prefix Tree

```python
module Make(L : Letter) : PersistentSet with type elt = L.t list =
    struct

module M = Map.Make(L)

type elt = L.t list
type t = { word : bool ; branches : t M.t; }

let empty = { word = false; branches = M.empty }

let is_empty t = not t.word && M.is_empty t branches

let rec mem x t =
    match x with
    | [] ->
        t.word
    | i::l ->
        try mem l (M.find i t branches)
        with Not_found -> false
```

The empty set is represented by a tree `empty` consisting of a single node, where the field `word` is `false`, and `branches` is the empty dictionary:

```python
let empty = { word = false; branches = M.empty }
```

The code is given in program 49 along with a function `is_empty` that tests whether a set is empty.

### Searching for an Element

Searching for an element `x` proceeds recursively as follows: If the word `x` is the empty list, the search ends, returning the boolean value contained in the root

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

```h
let rec mem x t =
    match x with
    | [] -> t.word
```

Otherwise, we pursue the search recursively within the subtree associated with the branch labeled with the first letter *i* of the word *x*. If this branch does not exist, the search ends immediately with a failure.

```h
| i :: l ->
    try mem l (M.find i t branches)
    with Not_found -> false
```

The code of the function *mem* is given in program 49.

## Inserting an Element

Inserting a word *x* in a prefix tree *t* consists in descending along the branches labeled with the letters of *x*, as was done when searching for an element.

If *x* is the empty word, the insertion ends and returns a tree *t* with a field *word* set to *true*, indicating that *x* now belongs to the set.

```h
let rec add x t =
    match x with
    | [] ->
        if t.word then t else { t with word = true }
```

We avoid reconstructing the node when *t.word* is already *true*.

If *x* is a non-empty list of the form *i::l*, we recursively insert *l* in the subtree *b* associated with the letter *i* in *t*. If *b* does not exist, we perform the insertion starting with an empty tree. The insertion ends with the creation of a new node in which we associate the letter *i* with the subtree obtained recursively.

```h
| i :: l ->
    let b = try M.find i t branches with Not_found -> empty in
        { t with branches = M.add i (add 1 b) t branches }
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
The code of the function `add` is given in program 50.

## Removing an Element

Removing an element `x` in a tree `t` proceeds, once again, with the same recursive traversal. There is, however, a subtlety. Removing an element can leave the tree in a state in which one branch is completely empty, that is, where the fields `word` are all `false`. To avoid wasting space in this manner, we will enforce the property that all leaves of a prefix tree must represent a word belonging to the set. In other words, the boolean `word` of a leaf must always be `true`, with the exception, of course, of the empty set, represented by a single node with the boolean `word` set to `false`.

Let us now write the code of the function `remove`. If the argument `x` is the empty list, it is deleted from `t` by switching the field `word` to `false`.

```hml
let rec remove x t =
  match x with
  | [] ->
    { t with word = false }
```

Otherwise, `x` is of the form `i::l` and we begin by recursively deleting the rest of the word `l` from the subtree associated with `i`. If this subtree does not exist, the function ends, directly returning `t`.

```hml
| i :: l ->
  try
    let s = remove l (M.find i t branches) in
  ...
  with Not_found -> t
```

Next, if the tree `s` exists and is empty, we remove the branch associated with `i` in `t`. Otherwise, we create a new binding between `i` and `s`.

```hml
let newahanes =
  if is_empty s then M.remove i t branches
  else M.add i s t branches
in
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 50 — Insertion and Removal in a Prefix Tree

```h
let rec add x t =
  match x with
  | [] ->
     if t.word then t else { t with word = true }
  | i::l ->
     let b = try M.find i t branches with Not_found -> empty in
     { t with branches = M.add i (add l b) t branches }
```

```h
let rec remove x t =
  match x with
  | [] ->
     { t with word = false }
  | i::l ->
     try
       let s = remove l (M.find i t branches) in
       let newbranches =
           if is_empty s then M.remove i t branches
           else M.add i s t branches
       in
       { t with branches = newbranches }
     with Not_found -> t
```
This guarantees that no branch of `t` will point to an empty tree. Finally, the function ends by updating `t` with the new branches.

```hkl
{ t with branches = newahances }
```

The code of the function `remove` is given above in program 50.

## Intersection of Prefix Trees

The intersection of two prefix trees is implemented with the help of two mutually recursive functions `inter` and `inter Fetehes`. The function `inter` computes the intersection of two trees `t1` and `t2` that are assumed to correspond to the same prefix `p`. The word `p` belongs to the intersection if the roots of `t1` and `t2` both contain the word `p`. The branches of the intersection are calculated by the function `inter Fetehes`.

```hkl
let rec inter t1 t2 =
    { word = t1.word && t2.word ;
     branches = inter Fetehes t1 branches t2. branches }
```

The function `inter Fetehes` implements the intersection of two dictionaries `m1` and `m2`. The idea is to enumerate the branches of `m1` while checking, for each branch, if a corresponding branch exists in `m2`. For this we use the function `M. fold`, starting from an empty dictionary and considering each binding `i` $\mapsto$ `ti` of `m1` in turn.

```hkl
and inter Fetehes m1 m2 =
    M. fold
        (fun i ti m -> ... )
        m1 M. empty
```

For each binding, we recursively compute the intersection `t` of `ti` with the tree bound to `i` in `m2`, if it exists. We add the binding `i $\mapsto$ t` to `m`, taking care to verify that `t` is not empty. If `m2` does not contain the branch `i`, the intersection is empty and `m` is left unchanged.

```hkl
(fun i ti m ->
    try
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 51 — Intersection of Prefix Trees

```h
let rec inter t1 t2 =
    { word = t1.word && t2.word;
        branches = interahanes t1 branches t2 branches; }
and interahanes m1 m2 =
    M.fold
    (fun i ti m ->
        try
            let t = inter ti (M.find i m2) in
            if is_empty t then m else M.add i t m
        with Not_found -> m)
    m1 M.empty
```

```h
let t = inter ti (M.find i m2) in
if is_empty t then m else M.add i t m
with Not_found -> m)
```

The complete code of the intersection function is given in program 51. The union operation is left as an exercise.

## Comparison

Prefix trees can be compared easily. To compare two trees t1 and t2, we begin by comparing the two booleans t1.word and t2.word. In case of equality, it is necessary to compare the two dictionaries t1 branches and t2.branches. For this, we use the comparison function provided by the module M. This takes as argument a function to compare the values in the two dictionaries, which corresponds precisely to the function compare that we seek to define. This function is therefore recursive.

```h
let rec compare t1 t2 =
    let c = Stdlib compares t1 word t2 word in
    if c<>0 then c else M comparisons t1 branches t2 branches
```

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

Consider a prefix tree s containing *N* words in all, and consider a word *x* of length *M*. The search for *x* in *s* necessitates at most *M* recursive calls to the function *mem*, each having the same cost as that of searching in the dictionary *branches* of the corresponding node. Since our dictionaries use the module *Map* of the standard library of OCaml, the cost of searching is logarithmic in the number of elements. The total cost is therefore proportionate to Σ log(*B*ᵢ), where the *B*ᵢ are the sizes of the dictionaries encountered during the search. We can bound each *B*ᵢ by *N*, since the property that each leaf ends with *true* guarantees that a node with a dictionary of size *B* contains at least *B* different words. Hence the complexity is at worst O(*M* log *N*). However, it can be a lot less. If, for example, each *B*ᵢ equals two, then the complexity will be O(*M*), while *N* can be as large as 2<sup>*M*</sup>. More generally, if the set of letters considered has a bounded size, as in case of the 26 letters of the alphabet for example, then searching has complexity O(*M*). The insertion and removal operations have similar complexity.

For the intersection of two prefix trees containing respectively N₁ and N₂
elements of length less than M, we can similarly bound the complexity by
O(N₁M log N₂). If the number of letters is bounded, the complexity reduces
to O(N₁M).

Dictionaries

A prefix tree encodes the presence of an element with a boolean contained in
each node. Adapting this structure to represent dictionaries therefore consists
in replacing the boolean by an optional value. We therefore define the following
type:

type 'a t = { value : 'a option ; branches : 'a t M.t }

The field *value* replaces the boolean field *word*. The necessary adaptations are
immediate: the function *mem* checks if the field *value* is different from *None*; the
function *add* replaces the current value (if present) by a new value; etc. The
code of the function *find* is given in program 52.

— openly licensed via CC BY SA 4.0 —
Program 52 — Searching in a Prefix Tree

```h
let rec find x t =
    match x, t.value with
    | [], None -> raise Not_found
    | [], Some v -> v
    | i :: l, _ -> find l (M.find i t branches)
```

## 5.5 Patricia Trees

We presented prefix trees in the preceding section. This data structure can be used to represent sets of integers by identifying an integer with the word formed by its binary digits. We call this a *Patricia tree*. Thus, the set `{4, 5, 17}` can be seen as the following set of three binary words:

$$ \{(100)_2, (101)_2, (10001)_2\} $$

We can construct a prefix tree for these three words. We have two possible Patricia trees, depending on whether we begin reading from the high- or the low-order bit. In the first case, we speak of *big-endian* Patricia trees and in the second, of *little-endian* Patricia trees<fnref n="3" />. In what follows, we consider only little-endian Patricia trees, which means that we examine the bits starting from the least significant one, that is, from right to left. Adopting the convention that a 0 bit leads to the left subtree while a 1 bit leads to the right subtree, the prefix tree obtained for the integers `{4, 5, 17}` is represented in figure 5.8.

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

<footnote n="3">³The terms *little-endian* and *big-endian* were borrowed from Jonathan Swift's *Gulliver's Travels*.</footnote>
<figure><img src="image_88.png" /><figcaption>Figure 5.8: Prefix tree for the integers {4, 5, 17}.</figcaption></figure>

We observe immediately that there is a lot of redundant information. For instance, the second bit of the three integers is always 0. Yet the prefix tree contains a branching node at this level. This is also the case for the fourth bit in the right subtree. We observe equally that it is useless to branch off when there is only one element left in the tree. To obtain a more compact representation, we will add a branching node to the tree only when necessary, that is, when there is a difference in the bits of the two subsets of elements. More precisely, a node will contain the bit to be tested as well as all the bits situated to its right. We thus obtain the tree of figure 5.9, where the bit to be tested is underlined.

<figure><img src="image_89.png" /><figcaption>Figure 5.9: Patricia tree for the set {4, 5, 17}.</figcaption></figure>

This tree signifies that we can begin by testing the first bit. If it is 0, we go to the left subtree, which contains a single element, $4 = (100)_2$. If it is 1, we go to the right subtree, which indicates that the third bit is to be tested, and that

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
the two low-order bits are $(01)_2$ for this entire subtree. If the third bit is 0, we reach the subtree containing only $17 = (10001)_2$. If it is 1, we reach the subtree containing only $5 = (101)_2$. Note that the order of elements is not preserved in the tree structure. (This would, however, be the case in big-endian Patricia trees containing unsigned integers.)

It is important to note that a branching node such as $(101)_2$ contains two distinct pieces of information: the bit that must be tested (here the third) and the bits lying to its right (here $(01)_2$). Only the first piece of information is necessary to search for an element in the tree. Insertion, however, requires the second piece as well. We will use two integers to represent a branching node such as $(101)_2$: a power of two to represent the bit to be tested (here $(100)_2$) and an integer representing the prefix, that is, the bits of order less than this power of two (here $(01)_2$). One integer alone would suffice (here $(101)_2$), but since it is not easy to extract the high-order bit, it is simpler to maintain the two pieces of information separately. We adopt therefore the following type to represent Patricia trees:

```c
type t =
| Empty
| Leaf of int
| Node of int * int * t * t
```

The constructor `Empty` represents the empty tree; `Leaf x` is a leaf containing an element `x`; and, finally, `Node (p, b, l, r)` represents a branching point, where `p` is the prefix, `b` the bit to test (a power of 2), and `l` and `r` the two subtrees. In what follows we will guarantee the following well-formedness invariant: A tree of the form `Node` does not contain a subtree of the form `Empty`.

## Searching for an Element

To search for an element `x` in a Patricia tree, it suffices to descend along the tree according to the branching bits, until a leaf is reached. We begin by writing a function `zero_bit` that tests whether the bit `b` of `x` is 0, using a *logical and* and assuming that the integer `b` is a power of 2.

```h
let zero_bit x b =
```

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

We can now write the function mem. Its definition is clear if the tree is empty.

let rec mem x = function
| Empty -> false

If we reach a leaf j, we check whether x is equal to j.

| Leaf j -> x = j

Finally, on a branching node, it suffices to determine if the bit corresponding to x is 0 or 1 by using the function zeroBit.

| Node (x, b, l, r) -> mem x (if zeroBit x b then l else r)

The code of mem is given in program 53.

Program 53 — Searching in a Patricia Tree

let zeroBit x b =
  x land b == 0

let rec mem x = function
| Empty -> false
| Leaf j -> x = j
| Node (x, b, l, r) -> mem x (if zeroBit x b then l else r)

Note that this code descends systematically until a leaf is reached, though it
could sometimes stop earlier if the element x does not have the prefix expected
by a branching node. We have chosen here an approach that performs fewer
checks, which privileges situations in which a majority of searches have a positive
outcome. Exercise 5.22 considers the other option.

Inserting an Element

Inserting an element into a Patricia tree consists in descending along the tree
until the insertion position is found. We use an example to illustrate the two

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
<figure><img src="image_90.png" /><figcaption>Figure 5.10: Insertion of $7 = (111)_2$ (on the left) or $13 = (1101)_2$ (on the right) in the Patricia tree of figure 5.9.</figcaption></figure>

cases that may come up. Let us assume that we are inserting $7 = (111)_2$ into the tree of figure 5.9. The first branching node leads to the right subtree, because the low-order bit is 1. However, in the second branching node, namely, $(\underline{101})_2$, the prefix does not coincide: It is $(11)_2$ in the element to be inserted and $(10)_2$ in the subtree. It is therefore necessary to create a new branching node, namely, $(\underline{11})_2$, with the previous subtree to the left and the leaf 7 to the right. In the end, we obtain the left tree of figure 5.10. On the other hand, if we insert not 7 but $13 = (1101)_2$, then we reach the leaf containing 5, which must be separated into two distinct leaves, containing 5 and 13, which gives the tree on the right in figure 5.10.

We begin by implementing a function `branch` that takes two trees `t1` and `t2` as arguments, and creates the corresponding branching node. The prefixes of the two trees, `p1` and `p2`, are assumed to be different. It is therefore necessary to determine the lowest-order bit at which `p1` and `p2` differ. For this, we proceed in two steps: We begin by determining all the bits that differ, using the operation `p1 lxor p2`. Then, we extract the lowest-order set bit, which must exist. We have already seen how to do this using a *logical and* between `x` and `-x` in section 4.2 *Bit Vectors*. Accordingly, we introduce a function `rightmost_1_bit` for this.

```pascal
let rightmost_1_bit x =
  x land -x
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 54 — Insertion in a Patricia Tree

let rightmost_1_bit x =
  x land -x

let branch p1 t1 p2 t2 =
  let b = rightmost_1_bit (p1 lxor p2) in
  let p = p1 land (b-1) in
  if zero_bit p1 b then
    Node (p, b, t1, t2)
  else
    Node (p, b, t2, t1)

let matches_prefix x p b =
  x land (b-1) == p

let rec add x = function
  | Empty ->
    Leaf x
  | Leaf j as t ->
    if j == x then t else branch x (Leaf x) j t
  | Node (p, b, l, r) as t ->
    if matches_prefix x p b then
      if zero_bit x b then
        Node (p, b, add x l, r)
      else
        Node (p, b, l, add x r)
    else
      branch x (Leaf x) p t

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
Let us now write the function `branch`. We begin by calculating the branching bit using `rightmost_1_bit`.

```hml
let branch p1 t1 p2 t2 =
    let b = rightmost_1_bit (p1 lxor p2) in
```

Then, we calculate the common prefix `p` of `p1` and `p2`. This is the set of bits of order less than `b`, that we extract using a *logical and* with the mask `b-1`.

```hml
let p = p1 land (b-1) in
```

We use `p1` here to determine this prefix, but we could have also used `p2`. The only thing that remains now is to determine which of the two, `t1` or `t2`, must be placed on the left, depending on the value of the bit `b`.

```hml
if zero_bit p1 b then
    Node (p, b, t1, t2)
else
    Node (p, b, t2, t1)
```

Let us illustrate how the function `branch` works with $p1 = (011101)_2$ and $p2 = (110101)_2$. The result of $p1 \lxor p2$ is $(101000)_2$. The bit `b` extracted using `rightmost_1_bit` is therefore $(001000)_2$. The mask $b-1$ is then $(000111)_2$, which gives the prefix $p = (000101)_2$.

We next define a function `matches_prefix` that determines if an integer `x` has the prefix defined by `p` and `b`.

```hml
let matches_prefix x p b =
    x land (b-1) == p
```

We are now able to write the function `add` that inserts an element `x` in a Patricia tree. The case of an empty tree is clear.

```hml
let rec add x = function
| Empty ->
    Leaf x
```

In the case of a leaf `j`, we begin by checking if `j` is equal to `x`. If it is, there is nothing more to be done. Otherwise, a branching node must be created for the two leaves, using `branch`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
| Leaf j as t ->
  if j == x then t else branch x (Leaf x) j t

Finally, in case of a `Node`, we determine whether `x` has the prefix of this tree.

| Node (p, b, l, r) as t ->
  if matches_prefix x p b then

If this is the case, we pursue the insertion recursively in the left or the right subtree, depending on whether the bit of `x` defined by `b` equals 0 or 1.

if zero_bit x b then
  Node (p, b, add x l, r)
else
  Node (p, b, l, add x r)

If, on the other hand, `x` does not have the prefix `p`, then it is necessary to create a branching node with two subtrees, `t` and the leaf `x`. The function `branch` is made precisely for this.

else
  branch x (Leaf x) p t

This concludes the function `add`. The complete code is given in program 54 (see page 253).

## Removing an Element

Removing an element in a Patricia tree proceeds exactly as in case of insertion, the only difference being that it is necessary to maintain the well-formedness invariant. To this end, it suffices to introduce a *smart constructor node* that behaves like `Node` when its arguments are not `Empty` and performs a simplification otherwise.

let node = function
| (, , Empty, t)
| (, , t, Empty) -> t
| (p, b, l, r) -> Node (p, b, l, r)

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
Program 55 — Removing an Element in a Patricia Tree

```pascal
let node = function
  | (, , Empty, t)
  | (, , t, Empty) -> t
  | (p, b, l, r) -> Node (p, b, l, r)

let rec remove x = function
  | Empty ->
    Empty
  | Leaf j as t ->
    if x == j then Empty else t
  | Node (p, m, t0, t1) as t ->
    if matches_prefix x p m then
      if zero_bit x m then
        node (p, m, remove x t0, t1)
      else
        node (p, m, t0, remove x t1)
    else
      t
```

By using the function `node` instead of the constructor `Node`, the definition of `remove` is clear. It is given in program 55.

Union

One of the advantages of Patricia trees compared to AVL trees is that the former lend themselves more easily to set-theoretic operations such as union. Indeed, two Patricia trees that have many elements in common will typically have the same, or similar, branching structures, thereby allowing an approach that uses recursive descent. This stands in contrast with AVL trees, where the root depends strongly on the manner in which the tree was constructed.

Let us implement the union of two Patricia trees, `t1` and `t2`. We begin by

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
considering the trivial cases. The simplest is that in which one of the trees is empty.

```h
let rec union t1 t2 = match t1, t2 with
  | Empty, t | t, Empty ->
    t
```

Similarly, we can easily treat the case in which one of the two trees is a leaf, by calling the function `add`.

```h
| Leaf x, t | t, Leaf x ->
    add x t
```

Next we must consider the general case, where `t1` and `t2` are both branching nodes.

```h
| Node (p1, b1, l1, r1), Node (p2, b2, l2, r2) ->
```

There are three possible scenarios. The simplest case is that in which the prefixes of `t1` and `t2` coincide exactly. In this case, it suffices to recursively perform the union of the left and right subtrees respectively.

```h
if b1 == b2 && p1 = p2 then
    Node (p1, b1, union l1 l2, union r1 r2)
```

In the second case, one of the two prefixes is included in the other. Assume for example that the prefix of `t1` is included in the prefix of `t2`. This means that `t1` tests a bit that is of lower order than that of `t2`, that is, `b1 < b2`, and that the bits of `p2` below `b1` coincide with `p1`. In this case, all of `t2` must be recursively merged with the left or right subtree of `t1`, depending on the bit `b1` of the prefix `p2`.

```h
else if b1 < b2 && matches_prefix p2 p1 b1 then
  if zero_bit p2 b1 then
    Node (p1, b1, union l1 t2, r1)
  else
    Node (p1, b1, l1, union r1 t2)
```

We treat the symmetrical case, when the prefix of `t2` is included in that of `t1`, in a similar manner.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
else if b1 > b2 && matches_prefix p1 p2 b2 then
...

The last case is that in which the prefixes differ completely, neither being included in the other. This means that the elements of t1 are disjoint from the elements of t2, and it suffices to create a new branching node with t1 on one side and t2 on the other, which is exactly what is done by the function branch.

else
    branch p1 t1 p2 t2

The complete code of union is given below in program 56. The intersection, difference, and inclusion test operations are written in a similar manner (see exercise 5.23).

## Comparison

Patricia trees can be compared easily. Indeed, two Patricia trees containing the same elements must have the same structure. Hence, the structural comparison functions of OCaml can be directly used on Patricia trees. In this way, we obtain an equality and a total order on the type t with the operator = and the function Stdlibcompare.

## Complexity

The cost of searching, inserting, and removing elements in Patricia trees is proportionate to the number of bits of the integer considered. The cost is thus constant. Note, however, that this cost can reach 64 comparisons on a 64-bit machine, which, in the case of an AVL tree, would correspond to a structure containing more elements than can be represented in the memory of the computer. We therefore cannot deduce from this that a Patricia tree is better than an AVL tree in general. A Patricia tree can require more comparisons than an AVL tree. Indeed, a Patricia tree containing 30 elements can have a comb structure while the corresponding AVL tree would be balanced. Nonetheless, Patricia

— openly licensed via CC BY SA 4.0 —
Program 56 — Union of Two Patricia Trees

let rec union t1 t2 = match t1, t2 with
| Empty, t | t, Empty ->
  t
| Leaf x, t | t, Leaf x ->
  add x t
| Node (p1, b1, l1, r1), Node (p2, b2, l2, r2) ->
  if b1 == b2 && p1 = p2 then
    Node (p1, b1, union l1 l2, union r1 r2)
  else if b1 < b2 && matches_prefix p2 p1 b1 then
    if zero_bit p2 b1 then
      Node (p1, b1, union l1 t2, r1)
    else
      Node (p1, b1, l1, union r1 t2)
  else if b1 > b2 && matches_prefix p1 p2 b2 then
    if zero_bit p1 b2 then
      Node (p2, b2, union t1 l2, r2)
    else
      Node (p2, b2, l2, union t1 r2)
  else
    branch p1 t1 p2 t2

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
trees remain an interesting structure when we have to implement operations like
union, intersection, or comparison.

Dictionaries

It is easy to adapt the type of Patricia trees to make dictionaries out of them.
Indeed, it suffices to add a second argument to the constructor *Leaf*.

```python
type key = int
type 'a t =
| Empty
| Leaf of key * 'a
| Node of int * int * 'a t * 'a t
```

The adaptations needed for the different functions are clear. Exercise 5.27 proposes writing the function *find*.

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

For Further Information

Patricia trees were introduced in 1968 by Morrison, [18], who forged the term
*Patricia* as an acronym for *Practical Algorithm To Retrieve Information Coded In Alphanumeric*. More recently, Patricia trees have been studied in
the context of a functional language by Okasaki and Gill [20].

The technique of *hash-consing*, presented in chapter 11, allows the association of unique integers with values of certain types. We can then exploit Patricia trees to represent sets of values of this type, notably if we have to implement costly operations like the union or comparison of sets.

5.6 Exercises

Binary Search Trees

5.1 Write a function *height* that calculates the height of a tree.

5.2 Write a function *cardinal*: t -> int that returns the number of elements of a binary search tree.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
5.3 Write a function `max_elt`: `t -> elt` analogous to `min_elt`.

5.4 Write a function `floor`: `elt -> t -> elt` that returns the largest element of a binary search tree less than or equal to a given element, if it exists, and raises the exception `Not_found` otherwise.

5.5 Write a function `iter`: `(elt -> unit) -> t -> unit` that traverses the elements of a binary search tree in increasing order.

5.6 Write a function `elements`: `t -> elt list` that returns the elements of a binary search tree in increasing order.

5.7 When calling `add` with an element already present or `remove` with an element that is absent, the efficiency of the two functions can be improved by directly returning the tree passed as argument. Rewrite the functions `add` and `remove` using this idea. You can raise an exception to signal that the tree is unchanged, taking care not to catch it at every recursive call, but only at the level of the initial call.

5.8 If you use the idea of the preceding exercise, it becomes easy to keep track of the cardinal of a binary search tree. You can, for example, use a record that stores the cardinal next to the tree. Rewrite the type `t`, and the functions `add` and `remove` in this way.

## AVL Trees

All the previous exercises on binary search trees may be taken up again with AVL trees.

5.9 Write the function `add` for a dictionary implemented with an AVL tree. What should be done if a key is already associated with a value?

## Hash Tables

5.10 The computation of `(X.hash x) mod (Array.length h.buckets)` would be incorrect if `X.hash x` returns a negative value, since the result would be negative. Explain why `(abs (X.hash x)) mod (Array.length h.buckets)` is not a solution.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
**5.11** Modify the function **resize** so that the size *m* of the new array does not exceed `Sys.max_array_length`.

**5.12** In case of a dictionary, rather than using an association list of type (`key * 'a'` list) to represent the buckets, you could use a more compact type, namely:

type 'a bucket = Nil | Cons of key * 'a * 'a bucket

Show that you would thus economize a third of the memory words. Rewrite the functions on hash tables using the type `'a bucket`.

**5.13** Using persistent arrays, implement a data structure of persistent hash tables.

## Prefix Trees

**5.14** Write the function **cardinal** on prefix trees.

**5.15** Write a function `min_elt` that returns the smallest element of a prefix tree with respect to the lexicographic order derived from `L comparisons`. You can use the fact that the iterators of the module `Map` traverse the bindings in increasing order of the keys.

**5.16** Improve the efficiency of the functions `add` and `remove` using the idea of exercise 5.7.

**5.17** The function `mem` is not tail recursive since the recursive call is contained in a `try-with`. Remedy this problem by only catching the exception `Not_found` at the top of the function.

**5.18** Rather than using the module `Map` of the OCaml standard library, the functor `Make` can take an additional argument `M` of signature

Map.S with type key = L.t

Rewrite the functor `Make` in this manner.

**5.19** Write the function **union** on prefix trees. You can use two mutually recursive functions as we did in case of the function `inter`.

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
**5.20** Write a variant of prefix trees where the dictionary `branches` is implemented with an array, for example, when words are formed from the characters 'a'..'z'.

**5.21** The T9 input method of early mobile phones facilitates typing text on their numeric keyboards: Instead of pressing several times on a key to produce each letter, a single press suffices, and the phone proposes the words that correspond to the sequence of pressed keys, based on a dictionary that the phone has in memory.

For example, when you press the keys 2, 6, 6, 7, 8, 8, 3, 7 successively, you obtain the word *computer*, assuming the following mapping from keys to letters,

2 ↦ abc, 3 ↦ def, 4 ↦ ghi, 5 ↦ jkl, 6 ↦ mno, 7 ↦ pqrs, 8 ↦ tuv, 9 ↦ wxyz.

A sequence of keys may correspond to more than one word. For instance, the sequence 2, 2, 5, 3, 7 corresponds to both *baker* and *cakes*, and the sequence 3, 3, 2, 7 corresponds to both *dear* and *fear*.

You can use prefix trees to represent such dictionaries. We thus have a data structure that allows us to search efficiently for all the words in the telephone's dictionary that correspond to a given sequence of key presses.

To this end, it is necessary to modify the data structure presented in this chapter slightly. First of all, we must assume that the decomposition of words is not necessarily injective. In other words, two different words may now be represented by the same sequence of letters. We will assume the existence of a module implementing this decomposition, with the following signature:

```python
module type Word = sig
type t
type letter
val decomposition: t -> letter list
val compare : t -> t -> int
end
```

Next, in order to store all the words whose decomposition corresponds to the same prefix, we must replace the boolean field `word`, which indicates a complete word, by a field containing a set of matching words. The beginning of the module `Make` will therefore have the following form:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0) —
```python
module Make(L : Letter)(W : Word with type letter = L.t)
    : PersistentSet with type elt = W.t =
        struct
            module S = Set.Make(W)
            module M = Map.Make(L)

    type elt = W.t
    type t = { words : S.t ; branches : t M.t }
```

Complete the code of the functor Make.

## Patricia Trees

**5.22** Modify the function mem on Patricia trees (program 53) so that it fails as soon as x does not possess the prefix corresponding to the node Node.

**5.23** Write functions inter, diff, and subset on Patricia trees, implementing respectively the intersection, the difference, and the inclusion test, taking the function union as a model.

**5.24** Write all the operations of big-endian Patricia trees, that is, where the bits are examined from left to right rather than from right to left. The main difficulty is writing the function `leftmost_1_bit` which is not as simple as `rightmost_1_bit`.

**5.25** Write a library of Patricia trees, independently of the little-endian or big-endian nature, as a functor parameterized by those elements that differ between the two implementations.

**5.26** Improve the representation of prefix trees by factoring out common prefixes as is done in Patricia trees. Thus, for the set of words `{do, doing, dominate, domino}` will have the following representation:

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

The root indicates that the first two letters must be **do** and that the corresponding word, **do**, is in the set. We move down the tree according to the value of the third letter. For **i**, we reach a leaf containing the word **doing**. For **m**, we reach a new branching node that indicates that the two following letters must be **in** and that the corresponding word, **domin**, is not in the set. According to the value of the sixth letter, we obtain either the leaf **dominate** or the leaf **domino**.

5.27 Write the function **find** for dictionaries represented using Patricia trees.
— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
# 6

## Queues

This chapter presents several data structures known as *queues*. A queue is a data structure whose elements are taken out in the order in which they were inserted, thus corresponding precisely to the usual notion of queue. We can also associate elements with priorities, in which case the elements are no longer taken out in the order in which they were inserted. This is called a *priority queue*.

### 6.1 Imperative Queues

This section presents a data structure of imperative queues based on linked lists. The signature of this structure is given in program 57 (see following page). The idea is as follows: If a queue `q` contains the elements 1, 2, 3, inserted in this order, then it is represented by a circular linked list in which each element points to the following one in the queue, and the last element points to the first. To be able to insert and remove elements in constant time, it suffices to keep a pointer to the final element of the queue, here, 3. We therefore have the following situation:

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by/4.0/) —
Program 57 — Minimal signature for imperative queues.

```python
module type ImperativeQueue = sig
type 'a t
val create : unit -> 'a t
val is_empty : 'a t -> bool
val push : 'a -> 'a t -> unit
val pop : 'a t -> 'a
end
```

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

Thus, to insert a new element, 4, it suffices to insert it after 3, that is, between 3 and 1, and to shift the pointer to 4.

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

We access the first element, here 1, by following the pointer contained in the final element. To remove the first element, it suffices to make the final element point to the second one, here 2, which is obtained by following two pointers.

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

We begin by introducing a type 'a cell to represent the cells of the linked list, in the usual way.

```python
type 'a cell = { elt : 'a; mutable next : 'a cell }
```

— openly licensed via [CC BY SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) —
We then represent a queue by a reference to the last cell. A problem arises when it comes to representing the empty queue, for which we would not want to have any list cells at all. We choose therefore to represent a queue with a reference to a value of type 'a cell option, where None represents the empty queue.

```hkl
type 'a t = (('a cell) option) ref
```

The implementation of the functions `create` and `is_empty` is clear.

```hkl
let create () =
    ref None

let is_empty q =
    !q = None
```

## Inserting an Element

Inserting an element `x` into a queue `q` follows the scheme mentioned above. If `q` is empty, we create a circular list of one element and modify `q` so that it points to this element. We use here the possibility afforded by OCaml of constructing a cyclic value with `let rec`.

```hkl
let push x q = match !q with
| None ->
    let rec c = { elt = x; next = c } in
    q := Some c
```

If `q` is not empty, we create a new cell `c` containing `x`, that we insert between the final and first elements, and then modify `q` so that it points to this new cell.

```hkl
| Some last ->
    let c = { elt = x; next = last.next } in
    last.next <- c;
    q := Some c
```

## Extracting an Element

To extract the first element of a queue `q`, we begin by testing whether `q` is empty. In this case, we raise an exception.

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