# Exercises

# 5.11. Exercises#

Solutions to most exercises are available. Fall 2022 is the first public release of these solutions. Though they have been available to Cornell students for a few years, it is inevitable that wider circulation will reveal improvements that could be made. We are happy to add or correct solutions. Please make contributions through Github.

**Exercise: complex synonym [★]**

Here is a module type for complex numbers, which have a real and imaginary component:

```
module type ComplexSig = sig
val zero : float * float
val add : float * float -> float * float -> float * float
end
```

Improve that code by adding `type t = float * float`

. Show how the signature can
be written more tersely because of the type synonym.

**Exercise: complex encapsulation [★★]**

Here is a module for the module type from the previous exercise:

```
module Complex : ComplexSig = struct
type t = float * float
let zero = (0., 0.)
let add (r1, i1) (r2, i2) = r1 +. r2, i1 +. i2
end
```

Investigate what happens if you make the following changes (each independently), and explain why any errors arise:

remove

`zero`

from the structureremove

`add`

from the signaturechange

`zero`

in the structure to`let zero = 0, 0`

**Exercise: big list queue [★★]**

Use the following code to create `ListQueue`

of exponentially increasing length:
10, 100, 1000, etc. How big of a queue can you create before there is a
noticeable delay? How big until there’s a delay of at least 10 seconds? (Note:
you can abort utop computations with Ctrl-C.)

```
(** Creates a ListQueue filled with [n] elements. *)
let fill_listqueue n =
let rec loop n q =
if n = 0 then q
else loop (n - 1) (ListQueue.enqueue n q) in
loop n ListQueue.empty
```

**Exercise: big batched queue [★★]**

Use the following function to create `BatchedQueue`

of exponentially increasing
length:

```
let fill_batchedqueue n =
let rec loop n q =
if n = 0 then q
else loop (n - 1) (BatchedQueue.enqueue n q) in
loop n BatchedQueue.empty
```

Now how big of a queue can you create before there’s a delay of at least 10 seconds?

**Exercise: queue efficiency [★★★]**

Compare the implementations of `enqueue`

in `ListQueue`

vs. `BatchedQueue`

.
Explain in your own words why the efficiency of `ListQueue.enqueue`

is linear
time in the length of the queue. *Hint: consider the @ operator.* Then explain
why adding \(n\) elements to the queue takes time that is quadratic in \(n\).

Now consider `BatchedQueue.enqueue`

. Suppose that the queue is in a state where
it has never had any elements dequeued. Explain in your own words why
`BatchedQueue.enqueue`

is constant time. Then explain why adding \(n\) elements
to the queue takes time that is linear in \(n\).

**Exercise: binary search tree map [★★★★]**

Write a module `BstMap`

that implements the `Map`

module type using a binary
search tree type. *Binary trees* were covered earlier when we discussed
algebraic data types. A binary *search* tree (BST) is a binary tree that obeys
the following *BST Invariant*:

For any node

n, every node in the left subtree ofnhas a value less thann’s value, and every node in the right subtree ofnhas a value greater thann’s value.

Your nodes should store pairs of keys and values. The keys should be ordered by the BST Invariant. Based on that invariant, you will always know whether to look left or right in a tree to find a particular key.

**Exercise: fraction [★★★]**

Write a module that implements the `Fraction`

module type below:

```
module type Fraction = sig
(* A fraction is a rational number p/q, where q != 0.*)
type t
(** [make n d] is n/d. Requires d != 0. *)
val make : int -> int -> t
val numerator : t -> int
val denominator : t -> int
val to_string : t -> string
val to_float : t -> float
val add : t -> t -> t
val mul : t -> t -> t
end
```

**Exercise: fraction reduced [★★★]**

Modify your implementation of `Fraction`

to ensure these invariants hold for
every value `v`

of type `t`

that is returned from `make`

, `add`

, and `mul`

:

`v`

is in*reduced form*the denominator of

`v`

is positive

For the first invariant, you might find this implementation of Euclid’s algorithm to be helpful:

```
(** [gcd x y] is the greatest common divisor of [x] and [y].
Requires: [x] and [y] are positive. *)
let rec gcd x y =
if x = 0 then y
else if (x < y) then gcd (y - x) x
else gcd y (x - y)
```

**Exercise: make char map [★]**

To create a standard library map, we first have to use the `Map.Make`

functor to
produce a module that is specialized for the type of keys we want. Type the
following in utop:

```
# module CharMap = Map.Make(Char);;
```

The output tells you that a new module named `CharMap`

has been defined, and it
gives you a signature for it. Find the values `empty`

, `add`

, and `remove`

in
that signature. Explain their types in your own words.

**Exercise: char ordered [★]**

The `Map.Make`

functor requires its input module to match the `Map.OrderedType`

signature. Look at that signature as well as the
signature for the `Char`

module. Explain in your own words why we are
allowed to pass `Char`

as an argument to `Map.Make`

.

**Exercise: use char map [★★]**

Using the `CharMap`

you just made, create a map that contains the following
bindings:

`'A'`

maps to`"Alpha"`

`'E'`

maps to`"Echo"`

`'S'`

maps to`"Sierra"`

`'V'`

maps to`"Victor"`

Use `CharMap.find`

to find the binding for `'E'`

.

Now remove the binding for `'A'`

. Use `CharMap.mem`

to find whether `'A'`

is
still bound.

Use the function `CharMap.bindings`

to convert your map into an association
list.

**Exercise: bindings [★★]**

Investigate the documentation of the `Map.S`

signature to find the
specification of `bindings`

. Which of these expressions will return the same
association list?

`CharMap.(empty |> add 'x' 0 |> add 'y' 1 |> bindings)`

`CharMap.(empty |> add 'y' 1 |> add 'x' 0 |> bindings)`

`CharMap.(empty |> add 'x' 2 |> add 'y' 1 |> remove 'x' |> add 'x' 0 |> bindings)`

Check your answer in utop.

**Exercise: date order [★★]**

Here is a type for dates:

```
type date = {month : int; day : int}
```

For example, March 31st would be represented as `{month = 3; day = 31}`

. Our
goal in the next few exercises is to implement a map whose keys have type
`date`

.

Obviously it’s possible to represent invalid dates with type `date`

—for
example, `{ month=6; day=50 }`

would be June 50th, which is
not a real date. The behavior of your code in the exercises below
is unspecified for invalid dates.

To create a map over dates, we need a module that we can pass as input to
`Map.Make`

. That module will need to match the `Map.OrderedType`

signature.
Create such a module. Here is some code to get you started:

```
module Date = struct
type t = date
let compare ...
end
```

Recall the specification of `compare`

in `Map.OrderedType`

as you write
your `Date.compare`

function.

**Exercise: calendar [★★]**

Use the `Map.Make`

functor with your `Date`

module to create a `DateMap`

module.
Then define a `calendar`

type as follows:

```
type calendar = string DateMap.t
```

The idea is that `calendar`

maps a `date`

to the name of an event occurring on
that date.

Using the functions in the `DateMap`

module, create a calendar with a few
entries in it, such as birthdays or anniversaries.

**Exercise: print calendar [★★]**

Write a function `print_calendar : calendar -> unit`

that prints each entry in a
calendar in a format similar to the inspiring examples in the previous exercise.
*Hint: use DateMap.iter, which is documented in the
Map.S signature.*

**Exercise: is for [★★★]**

Write a function `is_for : string CharMap.t -> string CharMap.t`

that given an
input map with bindings from \(k_1\) to \(v_1\), …, \(k_n\) to \(v_n\), produces an
output map with the same keys, but where each key \(k_i\) is now bound to the
string “\(k_i\) is for \(v_i\)”. For example, if `m`

maps `'a'`

to `"apple"`

, then
`is_for m`

would map `'a'`

to `"a is for apple"`

. *Hint: there is a one-line
solution that uses a function from the Map.S signature. To convert a character
to a string, you could use String.make. An even fancier way would be to use
Printf.sprintf.*

**Exercise: first after [★★★]**

Write a function `first_after : calendar -> Date.t -> string`

that returns the
name of the first event that occurs strictly after the given date. If there is
no such event, the function should raise `Not_found`

, which is an exception
already defined in the standard library. *Hint: there is a one-line solution
that uses two functions from the Map.S signature.*

**Exercise: sets [★★★]**

The standard library `Set`

module is quite similar to the `Map`

module. Use it
to create a module that represents sets of *case-insensitive strings*. Strings
that differ only in their case should be considered equal by the set. For
example, the sets {“grr”, “argh”} and {“aRgh”, “GRR”} should be considered the
same, and adding “gRr” to either set should not change the set.

**Exercise: ToString [★★]**

Write a module type `ToString`

that specifies a signature with an abstract type
`t`

and a function `to_string : t -> string`

.

**Exercise: Print [★★]**

Write a functor `Print`

that takes as input a module named `M`

of type
`ToString`

. The module returned by your functor should have exactly one value in
it, `print`

, which is a function that takes a value of type `M.t`

and prints a
string representation of that value.

**Exercise: Print Int [★★]**

Create a module named `PrintInt`

that is the result of applying the functor
`Print`

to a new module `Int`

. You will need to write `Int`

yourself. The type
`Int.t`

should be `int`

. *Hint: do not seal Int.*

Experiment with `PrintInt`

in utop. Use it to print the value of an integer.

**Exercise: Print String [★★]**

Create a module named `PrintString`

that is the result of applying the functor
`Print`

to a new module `MyString`

. You will need to write `MyString`

yourself.
*Hint: do not seal MyString.*

Experiment with `PrintString`

in utop. Use it to print the value of a string.

**Exercise: Print Reuse [★]**

Explain in your own words how `Print`

has achieved code reuse, albeit a very
small amount.

**Exercise: Print String reuse revisited [★★]**

The `PrintString`

module you created above supports just one operation: `print`

.
It would be great to have a module that supports all the `String`

module
functions in addition to that `print`

operation, and it would be super great to
derive such a module without having to copy any code.

Define a module `StringWithPrint`

. It should have all the values of the built-in
`String`

module. It should also have the `print`

operation, which should be
derived from the `Print`

functor rather than being copied code. *Hint: use two
include statements.*

**Exercise: implementation without interface [★]**

Create a file named `date.ml`

. In it put the following code:

```
type date = {month : int; day : int}
let make_date month day = {month; day}
let get_month d = d.month
let get_day d = d.day
let to_string d = (string_of_int d.month) ^ "/" ^ (string_of_int d.day)
```

Also create a dune file:

```
(library
(name date))
```

Load the library into utop:

```
$ dune utop
```

In utop, open `Date`

, create a date, access its day, and convert it to a string.

**Exercise: implementation with interface [★]**

After doing the previous exercise, also create a file named `date.mli`

. In it
put the following code:

```
type date = {month : int; day : int}
val make_date : int -> int -> date
val get_month : date -> int
val get_day : date -> int
val to_string : date -> string
```

Then re-do the same work as before in utop.

**Exercise: implementation with abstracted interface [★]**

After doing the previous two exercises, edit `date.mli`

and change the first
declaration in it to the following:

```
type date
```

The type `date`

is now abstract. Again re-do the same work in utop. Some of the
responses will change. Explain in your own words those changes.

**Exercise: printer for date [★★★]**

Add a declaration to `date.mli`

:

```
val format : Format.formatter -> date -> unit
```

And add a definition of `format`

to `date.ml`

. *Hint: use Format.fprintf and
Date.to_string.*

Now recompile, load utop, and after loading `date.cmo`

install the printer by
issuing the directive

```
#install_printer Date.format;;
```

Reissue the other phrases to utop as you did in the exercises above. The response from one phrase will change in a helpful way. Explain why.

**Exercise: refactor arith [★★★★]**

Download this file: algebra.ml. It contains two signatures and four structures:

`Ring`

is signature that describes the algebraic structure called a*ring*, which is an abstraction of the addition and multiplication operators.`Field`

is a signature that describes the algebraic structure called a*field*, which is like a ring but also has an abstraction of the division operation.`IntRing`

and`FloatRing`

are structures that implement rings in terms of`int`

and`float`

.`IntField`

and`FloatField`

are structures that implement fields in terms of`int`

and`float`

.`IntRational`

and`FloatRational`

are structures that implement fields in terms of ratios (aka fractions)—that is, pairs of`int`

and pairs of`float`

.

Note

Dear fans of abstract algebra: of course these representations don’t necessarily
obey all the axioms of rings and fields because of the limitations of machine
arithmetic. Also, the division operation in `IntField`

is ill-defined on zero.
Try not to worry about that.

Refactor the code to improve the amount of code reuse it exhibits. To do that,
use `include`

, functors, and introduce additional structures and signatures as
needed. There isn’t necessarily a right answer here, but here’s some advice:

No name should be

*directly declared*in more than one signature. For example,`( + )`

should not be directly declared in`Field`

; it should be reused from an earlier signature. By “directly declared” we mean a declaration of the form`val name : ...`

. An indirect declaration would be one that results from an`include`

.You need only three

*direct definitions*of the algebraic operations and numbers (plus, minus, times, divide, zero, one): once for`int`

, once for`float`

, and once for ratios. For example,`IntField.( + )`

should not be directly defined as`Stdlib.( + )`

; rather, it should be reused from elsewhere. By “directly defined” we mean a definition of the form`let name = ...`

. An indirect definition would be one that results from an`include`

or a functor application.The rational structures can both be produced by a single functor that is applied once to

`IntField`

and once to`FloatField`

.It’s possible to eliminate all duplication of

`of_int`

, such that it is directly defined exactly once, and all structures reuse that definition; and such that it is directly declared in only one signature. This will require the use of functors. It will also require inventing an algorithm that can convert an integer to an arbitrary`Ring`

representation, regardless of what the representation type of that`Ring`

is.

When you’re done, the types of all the modules should remain unchanged. You can
easily see those types by running `ocamlc -i algebra.ml`

.