View on GitHub

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 `int`s 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)

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)

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 `string`s:

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