Recitation 9: Examples of functors

In the previous lecture we saw functors for the first time. Today we will see more examples of them. Recall that a functor is a module that is parameterized on other modules. Functors allow us to create a module whose implementation depends on the implementation of one or several other modules, the argument(s) of the functor. Among other uses, functors allow us to define several modules with small differences. This is done without any code duplication, by making the argument module implement those differences.

An implementation of maps using functors

A map is a data abstraction that binds keys to values. 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. The key implementation is required to support an equality comparison. There are no requirements placed on the value implementation.

Many implementations of maps are possible. Here we use one of the simplest: association lists, which are lists of pairs, where each pair contains a (key,value) binding.

Here is an example of how to use our map abstraction.

Once you understand this map abstraction, you're ready to understand the map abstraction provided by OCaml's standard library. Here's the documentation for version 4.01.0: http://caml.inria.fr/pub/docs/manual-ocaml-4.01/libref/Map.html. Note the following differences with respect to our abstraction:

The input signature requires a comparison operator, generalizing our equality operator. This enables more efficient implementations of the map abstraction.
The output signature provides many more operations on map than our simple example did.
The functor does not bother to parameterize on a value type. Instead, it uses a polymorphic representation type 'a t. The 'a there is essentially our value type.
The implementation uses balanced binary trees instead of association lists.

You're also ready to understand the set abstraction provided by OCaml's standard library. Here's the documentation for version 4.01.0: http://caml.inria.fr/pub/docs/manual-ocaml-4.01/libref/Set.html.

You should study both the Set and Map abstractions provided by OCaml to make sure you have a good understanding of functors. We suggest writing some code of your own to experiment with them!

A general implementation of polynomials

A ring is a mathematical structure consisting of a set of elements equipped with two operations + and * called addition and multiplication. These operations must satisfy specific requirements for the set to be a ring. The zero, written 0, is a member of the set such that for any element, a+0=a ; the one, written 1, is a member of the set such that for any element, a*1=a. See this page for more details. For instance, the set of integers with the usual + and * is a ring. The set of booleans with the or operator as + and the and operator as * is also a ring. Polynomials can be defined on any ring, since they only use the + and the * operations. We are going to define a 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
end

Now 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
end

Now 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)