Help me to understand functors

Learning
11

Exactly, and we can say this is the only book of reference. :slight_smile: The answers for this thread are given here:

By the way, I’ll try to explain how modules and functors work with a simple example.

Modules.

Imagine that you want to define the notion of set of int with one 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 it:

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 it satisfies the invariant that an element already present isn’t added again:

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 for 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 abstract type.

Signatures.

When you define a module, the compiler infer automatically 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 in 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

Ok, that’s fine: we have a simple notion of sets of int and we can preserve some invariant, but what to do if we want to generalize this notion to have sets over other types without repeat ourself? That’s where functors come into play.

Functors.

In the same way that functions are used to construct new values from given one, functors are used to construct modules from given one.

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 module of set over a type when we have 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 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 redifine our previous one:

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 we can also use it to have sets of string:

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

I hope that you can now see what are functors, how to define them and how to use them.

6 Likes