Edit

Introduction to Functors

(Originally written by “Kantian”)

We’ll explain how modules and functors work with a simple example.

Modules

Imagine that you want to define the notion of sets of int with one predefined value and two functions on it:

• the empty set
• is_element to test if an int belongs to a given set
• add to add an int in a set (but only if it is not already present).

We can represent a set of int as a list of int, so we define this module:

module Int_Set = struct
  type elt = int (* an alias to `int` for the elements of the set *)
  type t = elt list (* an alias for the type of sets *)

  let (empty : t) = []

  let rec is_element i (set : t) =
    match set with
    | [] -> false
    | x :: xs -> x = i || is_element i xs

  let add i set = if is_element i set then set else i :: set
end

We can play around a bit with this module:

let s = Int_Set.(add 1 (add 2 empty));;
val s : Int_Set.t = [1; 2]

Int_Set.is_element 2 s;;
- : bool = true

Int_Set.is_element 3 s;;
- : bool = false

We can also add elements and verify that the invariant that an element already present isn’t added again is maintained:

Int_Set.add 3 s;;
- : Int_Set.t = [3; 1; 2]

Int_Set.add 2 s;; (* the invariant is satisfied *)
- : Int_Set.t = [1; 2]

But there is a problem: since the concrete representation of the type of sets is known (they are just lists), we can break the invariant:

Int_Set.add 3 (2 :: s);;
- : Int_Set.t = [3; 2; 1; 2]

The solution is to use what is called an abstract type.

Signatures

When you define a module, the compiler automatically infers its type or its signature. For the module defined above, the toplevel returns:

module Int_Set :
  sig
    type elt = int
    type t = elt list
    val empty : t
    val is_element : elt -> t -> bool
    val add : elt -> t -> t
  end

What we can do is to define a less precise signature to hide the fact that sets are implemented using lists:

module type S = sig
  type elt = int
  type t
  val empty : t
  val is_element : elt -> t -> bool
  val add : elt -> t -> t
end

Here, since we want to add ints to our sets, we don’t hide the fact that elements are int.

We can now restrict the interface of our module and the invariant can’t be broken anymore:

module Abstract_Int_Set = (Int_Set : S)

let s1 = Abstract_Int_Set.(add 1 (add 2 empty));;
val s1 : Abstract_Int_Set.t = <abstr>

1 :: s1;;
Error: This expression has type Abstract_Int_Set.t
       but an expression was expected of type int list

So far so good. We have a simple notion of sets of int and we can preserve an invariant, but what do we do if we want to generalize this notion to have sets over other types without repeating ourselves? That’s where functors come into play.

Functors

In the same way that functions are used to construct new values given other values as parameters, functors are used to construct new modules given other modules as parameters.

First, as in our int case, to define sets for a given type we need to know when two values are equal. So we define this signature:

module type EQ = sig
  type t
  val eq : t -> t -> bool
end

Then we define the general signature for a set module:

module type SET = sig
  type elt
  type t
  val empty : t
  val is_element : elt -> t -> bool
  val add : elt -> t -> t
end

Finally we write code to explain how to construct a set module for a specific type when we are given a function to test equality between its values:

module Make_Set (Elt : EQ) : SET with type elt = Elt.t = struct
  type elt = Elt.t
  type t = elt list

  let empty = []

  let rec is_element i set =
    match set with
    | [] -> false
    | x :: xs -> Elt.eq x i || is_element i xs

  let add i set = if is_element i set then set else i :: set
end

The code is mostly the same as before, except in the function is_element where to test for equality we now use the function Elt.eq given by the parameter of the functor.

Now, with this generic way to construct module of sets, we can easily redefine our previous module:

module Abstract_Int_Set = Make_Set (struct type t = int let eq = (=) end)

let s2 = Abstract_Int_Set.(add 1 (add 2 empty));;
val s2 : Abstract_Int_Set.t = <abstr>

Abstract_Int_Set.is_element 2 s2;;
- : bool = true

Abstract_Int_Set.is_element 3 s2;;
- : bool = false

But now we can also use it to define sets of strings:

module String_Set = Make_Set (struct type t = string let eq = (=) end)

let s = String_Set.(add "hello" (add "world" empty));;
val s : String_Set.t = <abstr>

String_Set.is_element "hello" s;;
- : bool = true

String_Set.is_element "foo" s;;
- : bool = false