Recitation: Functors

# Functors Today we will use the standard library's Map module, practice writing our own functors, and take a closer look at compilation units. ## The Map module The [Map module][map] in the OCaml standard library is an implementation of a dictionary data structure. Recall that dictionaries map *keys* to *values*. If a key \$k\$ maps to a value \$v\$, we say that \$v\$ is *bound* to \$k\$. [map]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.html ##### Exercise: make char map [✭] To create a 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. &square; ##### Exercise: char ordered [✭] The `Map.Make` functor requires its input module to match the `Map.OrderedType` signature. Look at [that signature][ord] as well as the [signature for the `Char` module][char]. Explain in your own words why we are allowed to pass `Char` as an argument to `Map.Make`. [ord]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.OrderedType.html [char]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Char.html &square; ##### 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. Are the correct three bindings active in it? &square; ##### Exercise: bindings [✭✭] Investigate the [documentation of the `Map.S`][map.s] signature to find the specification of `bindings`. Which of these expressions will return the same association list? 1. `CharMap.(empty |> add 'x' 0 |> add 'y' 1 |> bindings)` 2. `CharMap.(empty |> add 'y' 1 |> add 'x' 0 |> bindings)` 3. `CharMap.(empty |> add 'x' 2 |> add 'y' 1 |> remove 'x' |> add 'x' 0 |> bindings)` Check your answer in utop. *Note: make sure you understand the syntax being used in the expressions above. If not, ask your TA to review it.* &square; [map.s]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.S.html 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][parksandrec]. The behavior of your code in the exercises below is unspecified for invalid dates. [parksandrec]: http://nbcparksandrec.tumblr.com/post/46760908046/march-31st-is-a-day ##### Exercise: date order [✭✭] 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`][ord] 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. If you need inspiration, here are some good ideas for entries: * 10/13: CS 3110 Fall 2016 Prelim 1 * 11/17: CS 3110 Fall 2016 Prelim 2 * 12/15: CS 3110 Fall 2016 Final &square; ##### Exercise: print calendar [✭✭] Write a function `print_calendar : calendar -> unit` that prints each entry in a calendar in a format similar the inspiring examples in the previous exercise. *Hint: use `DateMap.iter`, which is documented in the [`Map.S` signature][map.s].* &square; ## Writing functors Our goal in the next series of exercises is to write a functor that, given a module supporting a `to_string` function, returns a module supporting a `print` function that prints that string. ##### Exercise: ToString [✭✭] Write a module type `ToString` that specifies a signature with an abstract type `t` and a function `to_string : t -> string`. &square; ##### Exercise: Print [✭✭] Write a functor `Print` that takes as input a module named `M` of type `ToString`. The structure 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. &square; ##### Exercise: Print Int [✭✭] Create a module named `PrintInt` that is the result of applying the functor `Print` to a new module `Int` of module type `ToString`. You will need to write `Int` yourself. The type `Int.t` should be `int`. Experiment with `PrintInt` in utop. Use it to print the value of an integer. &square; ##### Exercise: Print String [✭✭] Create a module named `PrintString` that is the result of applying the functor `Print` to a new module `MyString` of module type `ToString`. You will need to write `MyString` yourself. Experiment with `PrintString` in utop. Use it to print the value of a string. &square; ##### Exercise: Print reuse [✭] Explain in your own words how `Print` has achieved code reuse, albeit a very small amount. &square; ## Compilation units *This section properly belongs in the previous lab, but we ran out of room there, so it floated forward to this lab.* As the lecture notes on modules discuss, if you have a pair of files named `foo.ml` and `foo.mli` they together form a *compilation unit*. The `.ml` file is called the *implementation*, and the `.mli` file is called the *interface*. If, for example, `foo.mli` contains exactly the following: ``` val x : int val f : int -> int -> int ``` and `foo.ml` contains exactly the following: ``` let x = 0 let y = 12 let f x y = x + y ``` Then compiling `foo.ml` will have the same effect as defining the module `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: implementation without interface [✭] Create a file named `date.ml`. In it put exactly 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) ``` Compile that file to bytecode: ``` $ ocamlbuild date.cmo ``` Now start utop and type the following to use the module you've just created: ``` # #directory "_build";; # #load "date.cmo";; # let j1 = Date.make_date 1 1;; val j1 : Date.date = {Date.month = 1; day = 1} # j1.day;; - : int = 1 # Date.to_string j1;; - : string = "1/1" ``` &square; ##### Exercise: implementation with interface [✭] After doing the previous exercise, also create a file named `date.mli`. In it put exactly 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 ``` Recompile `date.ml` to bytecode: ``` $ ocamlbuild date.cmo ``` Restart utop and re-issue the same phrases as before: ``` # #directory "_build";; # #load "date.cmo";; # let j1 = Date.make_date 1 1;; val j1 : Date.date = {Date.month = 1; day = 1} # j1.day;; - : int = 1 # Date.to_string j1;; - : string = "1/1" ``` &square; ##### Exercise: implementation with abstracted interface [✭] After doing the previous two exercises, edit `date.mli` and change the first declaration in it to be exactly the following: ``` type date ``` The type `date` is now abstract. Recompile `date.ml` to bytecode: ``` $ ocamlbuild date.cmo ``` Restart utop and re-issue the same phrases as before. The responses to two of them will change. Explain in your own words those changes. ``` # #directory "_build";; # #load "date.cmo";; # let j1 = Date.make_date 1 1;; # j1.day;; # Date.to_string j1;; ``` &square; ## Additional exercises ##### 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.*  &square; ##### Exercise: calendar [✭✭] Write a function `first_after : calendar -> Date.t -> string` that returns the name of the first event that occurs after the given date. *Hint: there is a one-line solution that uses a couple functions from the `Map.S` signature.*  &square; ##### Exercise: sets [✭✭✭, recommended] 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. Assuming your module is named `CisSet`, here is some test code: ``` # CisSet.(equal (of_list ["grr"; "argh"]) (of_list ["GRR"; "aRgh"])) - : bool = true ``` &square; ##### 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.*  &square; ##### Exercise: printer for date [✭✭✭, advanced] After finishing **implementation with abstracted interface**, and after reading the notes in the previous lecture about `#install_printer`, 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 and reissue the phrases to utop as you did in the exercises above. The response from one phrase will change in a helpful way. Explain why. &square; ## Challenge exercise: Algebra Download this file: [algebra.ml](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`. *(For afficionados 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.)* Using this code, you can write expressions like the following: ``` # FloatField.(of_int 9 + of_int 3 / of_int 4 |> to_string);; - : string = "9.75" # IntRational.( let half = one / (one+one) in let quarter = half*half in let three = one+one+one in let nine = three*three in to_string (nine + (three*quarter)) );; - : string = "39/4" ``` [ring]: https://en.wikipedia.org/wiki/Ring_(mathematics) [field]: https://en.wikipedia.org/wiki/Field_(mathematics) ##### Exercise: refactor arith [✭✭✭✭] The file [algebra.ml](algebra.ml) contains a great deal of duplicated code. 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 it is possible to eliminate all the duplicated code. Here's some advice to guide you toward a good solution: * 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 `Pervasives.(+)`; 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. (Update: It does not require use of *[destructive substitution][dsub]*, despite what the exercises originally claimed.) 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. [dsub]: http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#sec234 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`, which will originally output the following: ``` module type Ring = 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 val of_int : int -> t end module type Field = sig type t val zero : t val one : t val ( + ) : t -> t -> t val ( ~- ) : t -> t val ( * ) : t -> t -> t val ( / ) : t -> t -> t val to_string : t -> string val of_int : int -> t end module IntRing : Ring module IntField : Field module FloatRing : Ring module FloatField : Field module IntRational : Field module FloatRational : Field ``` The final output of that command on your solution might define additional types, but the ones above should remain literally identical. &square;