Matt's Blog

Ocaml Functors

Sun Nov 5 15:42:46 EST 2006

Following on from the previous entry, now consider implementations of a signature that are themselves functions of a specific module type - these are called Functors. In the previous example the Interval datatype was defined for some endpoint elements, eg ints or floats. In Ocaml ints and floats have different addition operators (+ versus +. respectively) so the structure definitions for each interval required a lot of duplication. It would be better to define an Elt (element) datatype with addition, subtraction and comparison operators defined for each type, and then pass this module as a parameter for the functor implementing the interval datatype. This is shown below, where I have introduced the convention that the abstract datatype is called t, while the element from which it is constructed is called elt.

(* Define the element abstract data type *)
module type EltSig = sig
 type elt
 type t

 val make :  elt -> t
 (* compare two elements x and y, 
   return -1 if x < y, 0 if x = y and 1 if x > y *)
 val compare : t -> t -> int

 (* add two elts together *)
 val add : t -> t -> t

 (* subtract two elts *)
 val sub : t -> t -> t

 (* halve the size of an elt *)
 val halve : t -> t

 (* double the size of an elt *)
 val double : t -> t
end

(* Define an interval abstract data type *) 
module type IntervalSig = sig
 type elt

 type t

 (* constructor function from two end points *)
 val make_endpoints: elt -> elt ->  t

 (* constructor from centre point and width *)
 val make_centre_width: elt -> elt ->  t

 (* selector of lower limit *)
 val lower:  t -> elt

 (* selector of upper limit *)
 val upper:  t -> elt

 (* test whether an element is a 
    member of the elterval *)
 val test:  t -> elt -> bool

 (* width of the elterval *)
 val width:  t -> elt
end

(* Define a functor that constructs an interval from a
  given element abstract data type *)
module MakeInterval (Elt : EltSig) :
 IntervalSig with type elt = Elt.t 
= struct
 type elt = Elt.t
 type t = (elt * elt)

 let make_endpoints l u = 
   if (Elt.compare l u) < 0 then (l, u) else (u,l)

 let make_centre_width c w = 
   (Elt.sub c w, Elt.add c w)

 let lower (l, _) = l

 let upper (_, u) = u

 let test (l, u) x = 
   ((Elt.compare x l) >= 0) & 
   ((Elt.compare x u) < 1)

 let width (l, u) = Elt.halve (Elt.sub u l)
end

module Int : EltSig with type elt = int
= struct
 type elt = int
 type t = int

 let make x = x
 let compare x y = 
   if x < y then -1 else
   if x > y then  1 else 0
 let add x y = x + y
 let sub x y = x - y
 let halve x = x / 2
 let double x = x * 2
end

module Float : EltSig with type elt = float
= struct
 type elt = float
 type t = float

 let make x = x
 let compare x y = 
   if x < y then -1 else
   if x > y then 1 else 0
 let add x y = x +. y
 let sub x y = x -. y
 let halve x = x /. 2.
 let double x = x *. 2.
end

module IntInterval = MakeInterval(Int)
module FloatInterval = MakeInterval(Float)

This code is longer than the previous example but I am still quite happy - why? Because the details of the underlying ints and floats have been abstracted away from the definition of the interval datatype! I can now define an interval acting on any abstract data type implementing the EltSig signature, without having to change anything about the definition of the Interval datatype. For example, suppose I want to work with string intervals: module Str : EltSig with type elt = String.t = struct type elt = String.t type t = String.t

let make x = x
let compare x y = String.compare x y
let add x y = x ^ y
let sub x y = y ^ x
let halve x = String.sub x 0 ((String.length x)/2)
let double x= x ^ x

end module StringInterval = MakeInterval(Str) Admittedly the definition of subtraction of strings is a bit strange, as is the halving function (ie sub (add x y) y doesn't equal x and doubling a halved string doesn't always give the original string) but this is still sufficient to create string intervals where the user can test whether a string lies within the bounds of the two endpoint strings using the standard string ordering function.

• Sidenote: One possibility for a better string subtraction operator is to regard palindromes as equivalent to the empty string and then subtraction becomes equivalent to concatenation of the reversed string. Redefine the concatenation operator to remove the last character of the first string and the first character of the second string if they are equal, for each element of the new string. That is:

  hello + ole -> hell + le -> hel + e -> hele
  hello - hello -> hello ^ olleh -> (empty string)
  

  Of course this then fouls up the doubling operator for single element strings, so you cannot have everything.

One drawback to the extra abstraction layer is the requirement to specify elements to be tested against the interval as instances of the element abstract data type, eg

let interval = 
  IntInterval.make_endpoints (Int.make 0) (Int.make 10)
IntInterval.test interval (Int.make 5)

but this can be hidden by defining functions such as

let make_interval x y = 
  IntInterval.make_endpoints (Int.make x) (Int.make y)
let test intv x = IntInterval.test intv (Int.make x)

[code]

[permlink]