Introduction to Functors
(Originally written by “Kantian”)
We’ll explain how modules and functors work with a simple example.
Imagine that you want to define the notion of sets of
int with one
predefined value and two functions on it:
is_elementto test if an
intbelongs to a given set
addto 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.
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
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.
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
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
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