Parameterized Modules

Parameterized Modules

Parameterized modules are to modules what functions are to base values. Just like a function returns a new value from the values of its parameters, a parameterized module builds a new module from the modules given as parameters. Parameterized modules are also called functors.

The addition of functors to the module language increases the opportunities for code reuse in structures.

Functors are defined using a function-like syntax:

Syntax

functor ( Name : signature ) -> structure


# module Couple = functor ( Q : sig type t end ) -> 
   struct type couple = Q.t * Q.t end ;;
module Couple :
  functor(Q : sig type t end) -> sig type couple = Q.t * Q.t end

As for functions, syntactic sugar is provided for defining and naming a functor:

Syntax

module Name₁ ( Name₂ : signature ) = structure


# module Couple ( Q : sig type t end ) =  struct type couple = Q.t * Q.t end ;;
module Couple :
  functor(Q : sig type t end) -> sig type couple = Q.t * Q.t end

A functor can take several parameters:

Syntax

functor ( Name₁ : signature₁ ) -> :

functor ( Name_n : signature_n ) -> structure

The syntactic sugar for defining and naming a functor extends to multiple-argument functors:

Syntax

module Name (Name₁ : signature₁ ) ...( Name_n : signature_n ) =

structure

The application of a functor to its arguments is written thus:

Syntax

module Name = functor ( structure₁ ) ...( structure_n )

Note that each parameter is written between parentheses. The result of the application can be either a simple module or a partially applied functor, depending on the number of parameters of the functor.

Warning

There is no equivalent to functors at the level of signature: it is not possible to build a signature by application of a ``functorial signature'' to other signatures.

A closed functor is a functor that does not reference any module except its parameters. Such a closed functor makes its communications with other modules entirely explicit. This provides maximal reusability, since the modules it references are determined at application time only. There is a strong parallel between a closed function (without free variables) and a closed functor.

Functors and Code Reuse

The Objective CAML standard library provides three modules defining functors. Two of them take as argument a module implementing a totally ordered data type, that is, a module with the following signature:


# module type OrderedType =
   sig
     type t
     val compare: t -> t -> int
   end ;;
module type OrderedType = sig type t val compare : t -> t -> int end

Function compare takes two arguments of type t and returns a negative integer if the first is less than the second, zero if both are equal, and a positive integer if the first is greater than the second. Here is an example of totally ordered type: pairs of integers equipped with lexicographic ordering.


# module OrderedIntPair = 
   struct  
     type t = int * int 
     let compare (x1,x2) (y1,y2) =
       if x1 < y1 then -1
       else if x1 > y1 then 1
       else if x2 < y2 then -1
       else if x2 > y2 then 1
       else 0
   end ;;
module OrderedIntPair :
  sig type t = int * int val compare : 'a * 'b -> 'a * 'b -> int end

The functor Make from module Map returns a module that implements association tables whose keys are values of the ordered type passed as argument. This module provides operations similar to the operations on association lists from module List, but using a more efficient and more complex data structure (balanced binary trees).


# module AssocIntPair = Map.Make (OrderedIntPair) ;;
module AssocIntPair :
  sig
    type key = OrderedIntPair.t
    and 'a t = 'a Map.Make(OrderedIntPair).t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  end

The Make functor allows to construct association tables over any key type for which we can write a compare function.

The standard library module Set also provides a functor named Make taking an ordered type as argument and returning a module implementing sets of sets of values of this type.


# module SetIntPair = Set.Make (OrderedIntPair) ;;
module SetIntPair :
  sig
    type elt = OrderedIntPair.t
    and t = Set.Make(OrderedIntPair).t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val add : elt -> t -> t
    val singleton : elt -> t
    val remove : elt -> t -> t
    val union : t -> t -> t
    val inter : t -> t -> t
    val diff : t -> t -> t
    val compare : t -> t -> int
    val equal : t -> t -> bool
    val subset : t -> t -> bool
    val iter : (elt -> unit) -> t -> unit
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
    val cardinal : t -> int
    val elements : t -> elt list
    val min_elt : t -> elt
    val max_elt : t -> elt
    val choose : t -> elt
  end

The type SetIntPair.t is the type of sets of integer pairs, with all the usual set operations provided in SetIntPair, including a set comparison function SetIntPair.compare. To illustrate the code reuse made possible by functors, we now build sets of sets of integer pairs.


# module SetofSet = Set.Make (SetIntPair) ;;

# let x = SetIntPair.singleton (1,2) ;;           (* x = { (1,2) }        *)
val x : SetIntPair.t = <abstr>
# let y = SetofSet.singleton SetIntPair.empty ;;  (* y = { {} }           *)
val y : SetofSet.t = <abstr>
# let z = SetofSet.add x y ;;                     (* z = { {(1,2)} ; {} } *)
val z : SetofSet.t = <abstr>

The Make functor from module Hashtbl is similar to that from the Map module, but implements (imperative) hash tables instead of (purely functional) balanced trees. The argument to Hashtbl.Make is slightly different: in addition to the type of the keys for the hash table, it must provide an equality function testing the equality of two keys (instead of a full-fledged comparison function), plus a hash function, that is, a function associating integers to keys.


# module type HashedType =
   sig
     type t
     val equal: t -> t -> bool
     val hash: t -> int
   end ;;
module type HashedType =
  sig type t val equal : t -> t -> bool val hash : t -> int end
# module IntMod13 = 
   struct 
     type t = int 
     let equal = (=) 
     let hash x = x mod 13 
   end ;;
module IntMod13 :
  sig type t = int val equal : 'a -> 'a -> bool val hash : int -> int end
# module TblInt = Hashtbl.Make (IntMod13) ;;
module TblInt :
  sig
    type key = IntMod13.t
    and 'a t = 'a Hashtbl.Make(IntMod13).t
    val create : int -> 'a t
    val clear : 'a t -> unit
    val add : 'a t -> key -> 'a -> unit
    val remove : 'a t -> key -> unit
    val find : 'a t -> key -> 'a
    val find_all : 'a t -> key -> 'a list
    val mem : 'a t -> key -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
  end

Local Module Definitions

The Objective CAML core language allows a module to be defined locally to an expression.

Syntax

let module Name = structure

in expr

For instance, we can use the Set module locally to write a sort function over integer lists, by inserting each list element into a set and finally converting the set to the sorted list of its elements.


# let sort l =
   let module M = 
      struct 
        type t = int  
        let compare x y =
          if x < y then -1 else if x > y then 1 else 0
      end 
  in
    let module MSet = Set.Make(M) 
    in  MSet.elements (List.fold_right MSet.add l MSet.empty) ;;
val sort : int list -> int list = <fun>

# sort [ 5 ; 3 ; 8 ; 7 ; 2 ; 6 ; 1 ; 4 ] ;; 
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]

Objective CAML does not allow a value to escape a let module expression if the type of the value is not known outside the scope of the expression.


# let test = 
   let module Foo = 
     struct 
       type t 
       let id x = (x:t)
     end
   in Foo.id ;;
Characters 15-101:
This `let module' expression has type Foo.t -> Foo.t
In this type, the locally bound module name Foo escapes its scope