## Working with the `Map.Make` functor
Note: for this section of the lab, you may want to have a look at the [code from
the lecture](code.zip); particularly the `maps.ml` file.
In the last lab, you wrote two implementations of a dictionary interface.
The [Map module](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.html) in
the OCaml standard library gives a third implementation of
a dictionary, although it requires an ordering on the keys in the dictionary.
The ordering is specified by implementing the
[Map.OrderedType](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.OrderedType.html)
module type.
**Exercise**: Recall the `date` type from [lab 6](../06-data/rec.html):
```
type date = int * int * int (* (year, month, day) *)
```
Write a module `Date` that implements the `Map.OrderedType with type t = date`.
**Exercise**: Use the `Map.Make` functor with your `Date` module to create a
`DateMap` module.
Define a `calendar` type as follows:
```
type calendar = string DateMap.t
```
**Exercise**: Using the functions in the `DateMap` module, create a calendar
with four entries in it.
**Exercise**: Write a function `first_after : calendar -> Date.t -> string` that
returns the name of the first event that occurs after the given date (hint: use
`split`).
## Implementing some arithmetic functors
In the last lab, you implemented the `Arith` module type:
```
module type Arith = sig
type t
val zero : t
val one : t
val (+) : t -> t -> t
val (~-) : t -> t
val ( * ) : t -> t -> t
val to_string : t -> string
end
module Ints : Arith = struct ... end
module Floats : Arith = struct ... end
```
**Exercise**: Write a functor called `ExtendArith` that takes a
module `A` of type `Arith` and produces a module with the
following functions:
- `(-) : A.t -> A.t -> A.t`
- `of_int : int -> A.t`
```
module EInts = ExtendArith(Ints)
utop# Ints.to_string (EInts.of_int 3);;
- : string = 3
```
Note that with this design pattern, the interesting functions are split between
the original `Arith` module and the extended module. It is often convenient if
the "extended" module included all of the functionality of the original module:
```
module EInts = ExtendedArith(Ints)
utop# EInts.(to_string (of_int 3));;
```
An easy way to accomplish this is to "include" the extended module in the
module defined by the `ExtendArith` functor:
```
module ExtendArith (A : Arith) : ... = struct
include A
...
end
```
When you are defining a module, the `include M` includes all of the definitions
from `M` in the current module. This use of `include` differs from `open`
because with `open` the definitions of `M` are made available, but are not
made part of the module's interface.
**Exercise**: use "include" to reimplement `Ints` using only 3 lines (hint: what
module already defines `(+)`, `(~-)`, etc.?):
```
module Ints : Arith with type t = int = struct
...
...
...
end
```
**Exercise**: modify your definition of `ExtendArith` to include the
definitions of the module being extended.
**Exercise**: Implement a functor called `Fractions` that takes a module `A`
of type `Arith` and produces a module that implements `Arith`
using fractions. The produced modules should also include a
`(/)` function for division:
```
module Rationals = Fractions(Ints)
let half = Rationals.(one / (one + one))
let quarter = Rationals.(half * half)
utop# Rationals.to_string quarter;;
- : string = "1/4"
```
**Exercise**: Verify that `ExtendArith(Rationals).(-)` works correctly.
## .mli files
Writing all of your code in a single file does not scale well to large systems.
You've already seen that putting code in a `.ml` file creates a module with the
same name as the file (except capitalized).
You have also seen that if you create a `.mli` file for a `.ml` file, then the
module type of the module is given by the contents of the `.mli` file. For
example, you may have a file `foo.mli` containing (exactly) the following:
```
val x : int
val f : int -> int -> int
```
and a file `foo.ml` containing (exactly) the following:
```
let x = 0
let y = 12
let f x y = x + y
```
Compiling and loading `foo.ml` will have the same effect as defining the module
type`Foo` as follows:
```
module Foo : sig
val x : int
val f : int -> int -> int
end = struct
let x = 0
let y = 12
let f x y = x + y
end
```
**Exercise:** With this definition of `Foo`, what is `Foo.x`? What is `Foo.y`?
**Exercise:** Split your implementations of `Arith` into several files:
- `arith.ml` and `arith.mli` should contain the common infrastructure for `Arith`: the module
type and the `ExtendArith` functor.
- `ints.ml`, `ints.mli`, `floats.ml` and `floats.mli` should contain the
implementations of `Ints` and `Floats`
- `fractions.ml` and `fractions.mli` should contain the implementation of the
`Fractions` functor as well as the definition of the `Rationals` module.
As you do this exercise, you will discover a few issues:
- The module type you want for `Ints` is (roughly) `Arith`. What can you write
in `Ints.mli`? What you want to say is that "the module type of `Ints`
*includes* all of the definitions in `Arith`". You can use `include` to
state that succinctly.
- In the single-file version, `Arith` is the module type of `Ints` and
`Floats`, but in the multiple-file version, `Arith` is the module type of
the `Arith` module, which contains the `Extend` functor, among other things.
You could define a module type `Arith` in the `Arith` module, so that the
types of `Ints` would be `Arith.Arith`. In fact, `Arith.Arith` is a bit
redundant, so a common idiom is to simply use `Arith.S` for "the Arith
signature" (much like `Ints.t` is "the type defined in the Ints module").
- Similarly, in the single-file version, `Fractions` is a functor, but in the
multiple-file version, `Fractions` is a module that contains a functor, so
you need to choose a name for the functor itself. The convention used in
the standard library is to call the functor "`Make`", so that `Rationals`
would be `Fractions.Make(Ints)`.
- Everything declared in a .mli file must be implemented in the corresponding
.ml file. This includes any module types that you define in the .ml file.
This sometimes leads to duplicated code between the .ml and the .mli files.
For example, suppose a signature includes a module type `T`:
```
module X : sig
module type T = sig
val x : int
val y : int
end
module N : T
end = struct
...
end
```
The definition of `X` (the `...`) must itself include a module type `T` that
matches the `T` given in the signature:
```
module X : sig
module type T = sig
val x : int
val y : int
end
module N : T
end = struct
(** This module type duplicated from signature *)
module type T = sig
val x : int
val y : int
end
module N = struct
let x = 0
let y = 1
end
end
```
This often means that you'll have to duplicate module types in both the .mli
and the .ml files. It's good to clearly label the duplicated definitions
in the .ml file.