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