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