Functors

Without type elt = Ord.t in the result signature, IntSet.elt would be abstract and you couldn't add ints.

21.1 Functors are functions from modules to modules

module type ORDERED = sig
  type t
  val compare : t -> t -> int
end

module MakeSet (Ord : ORDERED) : sig
  type elt = Ord.t
  type t
  val empty : t
  val add : elt -> t -> t
  val mem : elt -> t -> bool
  val to_list : t -> elt list
end = struct
  type elt = Ord.t
  type t = elt list            (* sorted, unique *)
  let empty = []
  let rec add x = function
    | [] -> [x]
    | y :: ys as l ->
        let c = Ord.compare x y in
        if c = 0 then l else if c < 0 then x :: l else y :: add x ys
  let mem x = List.exists (fun y -> Ord.compare x y = 0)
  let to_list s = s
end

module IntSet = MakeSet (Int)
module StrSet = MakeSet (String)

21.2 Sharing constraints: with type

Without type elt = Ord.t in the result signature, IntSet.elt would be abstract and you couldn't add ints. Alternatively:

module type SET = sig type elt type t val empty : t val add : elt -> t -> t end
module MakeSet2 (Ord : ORDERED) : SET with type elt = Ord.t = struct ... end

21.3 Multi-argument functors

module MakePair (A : ORDERED) (B : ORDERED) : ORDERED with type t = A.t * B.t = struct
  type t = A.t * B.t
  let compare (a1, b1) (a2, b2) =
    match A.compare a1 a2 with 0 -> B.compare b1 b2 | c -> c
end
module IntStrMap = Map.Make (MakePair (Int) (String))

21.4 Functors for extending modules

module type MONOID = sig type t val empty : t val combine : t -> t -> t end

module Fold (M : MONOID) = struct
  let concat lst = List.fold_left M.combine M.empty lst
end

module Sum = Fold (struct type t = int let empty = 0 let combine = ( + ) end)
module Concat = Fold (struct type t = string let empty = "" let combine = ( ^ ) end)
let six = Sum.concat [1;2;3]

21.5 Standard-library functors

Map.Make, Set.Make, Hashtbl.Make, Weak.Make, Ephemeron.K1.Make.