In last lecture we saw functors and basic examples. Today we will see more examples of those.

Recall that a *functor* is a module that is parameterized by other modules. Functors allow us to create a module whose implementation depends on the implementation of one or several other module, the argument(s) of the functor. Thus, functor allow to define several modules with very slight differences. This is done without any code duplication, by making the argument module implement those differences.

Here is an example of a functor allowing us to easily implement maps. We reuse the `SETSIG`

and `EQUALSIG`

implementations we had seen last time.

A map is a structure allowing us to easily map *keys* to *values*. Since we want a very general map here, we define a functor taking two arguments: the first argument is an implementation of the keys, and the second argument is an implementation of the values.

module type MAPSIG = sig type map type key type value val empty : map val add : map -> key -> value -> map val find : map -> key -> value end module type VALUESIG = sig type value end module MakeMap (Equal : EQUALSIG) (Value : VALUESIG) : MAPSIG with type key = Equal.t with type value = Value.value = struct type key = Equal.t type value = Value.value (* The actual map is a Set of Pair(key,value); the Key construct is only there to be able to implement the find fonction No Key construct shall be in a real set *) type item = Key of key | Pair of key * value module EqualItem = struct (* implementing the equality of items, of type EQUALSIG *) type t = item let equal (Key key1 | Pair (key1, _)) (Key key2 | Pair (key2, _)) = Equal.equal key1 key2 end module Set = MakeSet (EqualItem) type map = Set.set let empty = Set.empty let add map key value = Set.add (Pair (key, value)) map let find map key = match Set.find (Key key) map with Pair (_, value) -> value | Key _ -> raise (Invalid_argument "find") end module BoolVal = struct type value = bool end module SMap = MakeMap (StringNoCase) (BoolVal) let m = SMap.add SMap.empty "I like CS 3110" true SMap.find m "i LiKe cs 3110";; SMap.find m "Foo";;

`MakePolynomial`

functor that takes a ring module as argument and creates a module for handling polynomials in that ring. This example was inspired by this page, and slightly modified.
We first define module types for a ring and a polynomial:
module type RING = sig type t val zero : t val one : t val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val print : t -> unit end module type POLYNOMIAL = sig type c (* type of numbers used in the polynomial *) type t (* type of the polynomials *) val zero : t val one : t val monom : c -> int -> t val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val print : t -> unit val eval : t -> c -> c endNow we can implement the

`MakePolynomial`

functor. In the following implementation, we implement polynomials using lists of (coefficient,power) pair, ordered by power; no coefficient shall be 0, and no power shall repeat. For example, the only valid implementation of 3*x^2+5 would be [(3,2);(5,0)].
module MakePolynomial (A : RING) : POLYNOMIAL with type c=A.t = struct type c = A.t type monom = (c * int) (* a monom is a pair (coefficient,power) *) type t = monom list (* a polynomial of type t is a list of monoms, where powers are all different and ordered, and where coefficients are all non-zero *) let zero = [] let one = [A.one, 0] let rec equal p1 p2 = match p1, p2 with | [],[] -> true | (a1, k1)::q1, (a2, k2)::q2 -> k1 = k2 && A.equal a1 a2 && equal q1 q2 | _ -> false let monom a k = if k < 0 then failwith "fail monom: negative power" else if A.equal a A.zero then [] else [(a,k)] let rec plus p1 p2 = match p1, p2 with (x1, k1)::r1, ((x2, k2)::r2) -> if k1 < k2 then (x1, k1):: (plus r1 p2) else if k1 = k2 then let x = A.plus x1 x2 in if A.equal x A.zero then plus r1 r2 (* in some rings, like Z/2Z, x=0 can happen *) else (A.plus x1 x2, k1):: (plus r1 r2) else (x2, k2):: (plus p1 r2) | [], _ -> p2 | _ , [] -> p1 let rec times (a, k) p = (* auxiliary function, multiplies p by aX^k *) (* supposes a <> 0 *) match p with | [] -> [] | (a1, k1)::q -> let a2 = A.mult a a1 in if A.equal a2 A.zero (* in some rings, like Z/2Z, a2=0 can happen *) then times (a,k) q else (a2, k + k1) :: times (a,k) q let mult p = List.fold_left (fun r m -> plus r (times m p)) zero let print p = print_string "("; let b = List.fold_left (fun acc (a,k) -> (* acc is false only for the first monom printed *) if acc then print_string "+"; A.print a; print_string "X^"; print_int k; true ) false p in if (not b) then (A.print A.zero); print_string ")" let rec pow c k = match k with (* auxiliary function for eval *) (* given c and k, calculates c^k *) 0 -> A.one | 1 -> c | k -> let l = pow c (k/2) in let l2 = A.mult l l in if k mod 2 = 0 then l2 else A.mult c l2 let eval p c = match List.rev p with [] -> A.zero | (h::t) -> let (* supposes k >= l. *) dmeu (a, k) (b, l) = A.plus (A.mult (pow c (k-l)) a) b, l in let a, k = List.fold_left dmeu h t in A.mult (pow c k) a endNow we can create two examples with ints, and bools:

module IntRing = struct type t=int let zero=0 let one=1 let plus a b=a+b let mult a b=a*b let equal a b=(a=b) let print=print_int end module BoolRing = struct type t=bool let zero=false let one=true let plus a b=a || b let mult a b=a && b let equal a b=(a=b) let print a=if a then print_string "true" else print_string "false" end module IntPolynomial=MakePolynomial(IntRing) module BoolPolynomial=MakePolynomial(BoolRing)Here are examples of using the module IntPolynomial:

# open IntPolynomial;; # let a=monom 5 4;; val a : IntPolynomial.t = <abstr> # print a;; (5X^4)- : unit = () # let b=monom 1 8;; val b : IntPolynomial.t = <abstr> # print b;; (1X^8)- : unit = () # print (plus a b);; (5X^4+1X^8)- : unit = () # print (mult a b);; (5X^12)- : unit = ()Finally, we can see that any set of polynomials on a variable X is itself a ring! By creating a polynomial type on that new ring, we get the polynomials in two variables, say X and Y:

module IntPolynomial2Vars=MakePolynomial(IntPolynomial)