ReasonML: functors

[2018-01-15] dev, reasonml
(Ad, please don’t block)

Table of contents for this series of posts: “What is ReasonML?”

Functors are mappings from modules to modules. This blog post explains how they work and why they are useful.

The code of the examples is available on GitHub, in repository reasonml-demo-functors.

Note: Functors are an advanced topic. You can get by initially without knowing how to write them. I explain the basics of using them whenever that is required elsewhere.

What are functors?  

Functor is a term from category theory, where it refers to a mapping between categories. In ReasonML, there are two ways of looking at a functor:

  • A function whose parameters are modules and whose result is a module.
  • A module (the result) that is parameterized (configured) via modules (the parameters).

You can only define a functor as a submodule (it can’t be the top-level element in a file). But that is not a problem, because you usually want to deliver a functor inside a module, where it can sit next to the interfaces for its parameters and (optionally) its result.

The syntax of functors looks as follows.

module «F» = («ParamM1»: «ParamI1», ···): «ResultI» => {
  «body of functor»
};

The functor F has as parameters one or more modules ParamM1 etc. Those modules must be typed via interfaces ParamI1 etc. The result type ResultI (another interface) is optional.

The body of a functor has the same syntax as a normal module, but it can refer to the parameters and their contents.

A first functor  

Defining the functor Repetition.Make  

As our first example, we define a functor Repetition.Make that exports a function repeat() that repeats its parameter, a string. The parameter of the functor configures how often the string is repeated.

Before we can define the functor, we need to define an interface Repetition.Count for its parameter:

/* Repetition.re */

module type Count = {
  let count: int;
};

This is what the functor looks like:

/* Repetition.re */

module Make = (RC: Count) => {
  let rec repeat = (~times=RC.count, str: string) =>
    if (times <= 0) {
      "";
    } else {
      str ++ repeat(~times=times-1, str);
    };
};

Make is a functor: Its parameter RC is a module, its result (in curly braces) is also a module.

repeat() is a relatively boring ReasonML function. The only new aspect is the default value for ~times, which comes from the parameter module RC.

An interface for the result of Repetition.Make  

Repetition.Make does not currently define the type of its result. That means that ReasonML infers that type. If we want more control, we can define an interface S for the result:

/* Repetition.re */

module type S = {
  let repeat: (~times: int=?, string) => string;
};

Afterwards, we just need to add S to the definition of Make:

module Make = (RC: Count): S => ···

Using Repetition.Make  

Next, we use Repetition.Make in a separate file, RepetitionMain.re. First, we define a module for the parameter of the functor:

/* RepetitionMain.re */

module CountThree: Repetition.Count = {
  let count=3;
};

The type Repetition.Count is not needed, as long as CountThree has the exact same structure as that interface. But it makes it immediately clear, what the purpose of CountThree is.

Now we are ready to use the functor Repetition.Make to create a module for us:

/* RepetitionMain.re */

module RepetitionThree = Repetition.Make(CountThree);

The following code calls RepetitionThree.repeat, which works as expected:

/* RepetitionMain.re */

let () = print_string(RepetitionThree.repeat("abc\n"));

/* Output:
abc
abc
abc
*/

Instead of defining module CountThree separately, we could have also inlined it:

module RepetitionThree = Repetition.Make({
  let count=3;
});

The structure of the module Repetition  

The way we have structured module Repetition is a common pattern for using functors. It has the following parts:

  • Make: the functor.
  • One or more interfaces for the parameters of Make (in our case, Count).
  • S: an interface for the result of Make.

That is, Repetition packages the functor Make and everything it needs.

Functors for data structures  

One common use case for functors is implementing data structures:

  • The parameters of the functor specify the elements managed by the data structure. Due to the parameters being modules, you can not only specify the types of the elements, but also helper functions that the data structure may need for managing them.

  • The result of the functor is a module that is tailor-made for the specified elements.

For example, the data structure Set (which we’ll look at in more detail later) must be able to compare its elements. Therefore, the functor for sets has a parameter with the following interface:

module type OrderedType = {
  type t;
  let compare: (t, t) => int;
};

OrderedType.t is the type of the elements of the set, OrderedType.compare is used to compare those elements. OrderedType.t is similar to the type variable 'a of the polymorphic type list('a).

PrintablePair1: a first version of a functor for printable pairs  

Let’s implement a very simple data structure: pairs with arbitrary components that can be printed (converted to string). In order to print pairs, we must be able to print their components. Which is why components must be specified via the following interface.

/* PrintablePair1.re */

module type PrintableType = {
  type t;
  let print: t => string;
};

We once again use the name Make for the functor that produces the modules with the actual data structures:

/* PrintablePair1.re */

module Make = (Fst: PrintableType, Snd: PrintableType) => {
  type t = (Fst.t, Snd.t);
  let make = (f: Fst.t, s: Snd.t) => (f, s);
  let print = ((f, s): t) =>
    "(" ++ Fst.print(f) ++ ", " ++ Snd.print(s) ++ ")";
};

This functor has two parameters: Fst specifies the first component of a printable pair, Snd specifies the second component.

The modules returned by PrintablePair1.Make have the following parts:

  • t is the type of the data structure supported by this functor. Notice how it refers to the functor parameters Fst and Snd.
  • make is the function for creating values of type t.
  • print is a function for working with printable pairs. It converts a printable pair to a string.

Using the functor  

Let’s use the functor PrintablePair1.Make to create a printable pair whose first component is a string and whose second component is an int.

First, we need to define the arguments for the functor:

/* PrintablePair1Main.re */

module PrintableString = {
  type t=string;
  let print = (s: t) => s;
};
module PrintableInt = {
  type t=int;
  let print = (i: t) => string_of_int(i);
};

Next, we use the functor to create a module PrintableSI:

/* PrintablePair1Main.re */

module PrintableSI = PrintablePair1.Make(PrintableString, PrintableInt);

Lastly, we create and print a pair:

/* PrintablePair1Main.re */

let () = PrintableSI.({
  let pair = make("Jane", 53);
  let str = print(pair);
  print_string(str);
});

Improving encapsulation  

The current implementation has one flaw, we can create elements of type t without using PrintableSI.make():

let pair = ("Jane", 53);
let str = print(pair);

To prevent that, we need to make the type Make.t abstract, via an interface:

/* PrintablePair1Main.re */

module type S = (Fst: PrintableType, Snd: PrintableType) => {
  type t;
  let make: (Fst.t, Snd.t) => t;
  let print: (t) => string;
};

This is how we define Make to have the type S:

module Make: S = ···

Note that S is the type of the whole functor.

PrintablePair2: an interface just for the result  

It is more common to define an interface only for the result of a functor (not for the complete functor, as we did before). That way, you can reuse that interface for other purposes. For the ongoing example, such an interface would look as follows.

/* PrintablePair2.re */

module type S = {
  type fst;
  type snd;
  type t;
  let make: (fst, snd) => t;
  let print: (t) => string;
};

Now we can’t refer to the parameters Fst and Snd of the functor, anymore. Therefore, we need to introduce two new types fst and snd, which we need to define the type of make(). This function previously had the following type:

let make: (Fst.t, Snd.t) => t;

How do we connect fst and snd with Fst.t and Snd.t, then? We do so via so-called sharing constraints, equations that modify interfaces. They are used like this:

/* PrintablePair2.re */

module Make = (Fst: PrintableType, Snd: PrintableType)
: (S with type fst = Fst.t and type snd = Snd.t) => {
  type fst = Fst.t;
  type snd = Snd.t;
  type t = (fst, snd);
  let make = (f: fst, s: snd) => (f, s);
  let print = ((f, s): t) =>
    "(" ++ Fst.print(f) ++ ", " ++ Snd.print(s) ++ ")";
};

The following two equations are sharing constraints:

S with type fst = Fst.t and type snd = Snd.t

The S with hints at those constraints changing the interface S. And they do, indeed. The interface of the result of Make is now:

{
  type fst = Fst.t;
  type snd = Snd.t;
  type t;
  let make: (fst, snd) => t;
  let print: (t) => string;
}

There is one more thing we can improve: fst and snd are redundant. It would be better if the result interface referred to Fst.t and Snd.t directly (like it did when we had an interface for the complete functor). That is done via destructive substitutions.

PrintablePair3: destructive substitutions  

Destructive substitutions work much like sharing constraints. However:

  • A sharing constraint S with type t = u provides more information for S.t.
  • A destructive substitution with type t := u replaces all occurrences of t inside S with u.

This is what Make looks like if we use destructive substitutions:

module Make = (Fst: PrintableType, Snd: PrintableType)
: (S with type fst := Fst.t and type snd := Snd.t) => {
  type t = (Fst.t, Snd.t);
  let make = (fst: Fst.t, snd: Snd.t) => (fst, snd);
  let print = ((fst, snd): t) =>
    "(" ++ Fst.print(fst) ++ ", " ++ Snd.print(snd) ++ ")";
};

The destructive substitutions remove fst and snd from S. Therefore, we don’t need to define them in Make’s body, anymore, and can always directly refer to Fst.t and Snd.t. Due to the destructive substitutions, the definition inside Make matches what the interface requires. The result signature of Make is now:

{
  type t;
  let make: (Fst.t, Snd.t) => t;
  let print: (t) => string;
}

Example: using the functor Set.Make  

The standard module Set for sets of values follows the conventions I have already explained:

  • Set.Make is the functor that produces the actual module for handling sets.
  • Set.OrderedType is the interface for Make’s parameter:
    module type OrderedType = {
  type t;
  let compare: (t, t) => int;
};
  • Set.S is the interface for Make’s result.

This is how you create and use a module for string sets:

module StringSet = Set.Make({
  type t = string;
  let compare = Pervasives.compare;
});

let set1 = StringSet.(empty |> add("a") |> add("b") |> add("c"));
let set2 = StringSet.of_list(["b", "c", "d"]);

/* StringSet.elements(s) converts set s to list */
StringSet.(elements(diff(set1, set2)));
  /* list(string) = ["a"] */

Conveniently, ReasonML’s standard library comes with a module String that works as a parameter for Set.Make, because it has both String.t and String.compare. Therefore, we could have also written:

module StringSet = Set.Make(String);

Functors for extending modules  

Functors can also be used to extend existing modules with functionality. Used in this manner, they are similar to multiple inheritance and mixins (abstract subclasses).

As an example, let’s extend an existing module that can only add single elements to its data structure with a function for adding all elements of a given data structure. AddAll is a functor for doing so:

module AddAll = (A: AddSingle) => {
  let addAll = (~from: A.t, into: A.t) => {
    A.fold((x, result) => A.add(x, result), from, into);
  };
};

The function addAll() uses fold() to iterate over the elements of ~from and add them to into, one at a time. result is always bound to what has already been computed (first into, then the result of adding the first x to into, etc.).

In this case, we let ReasonML infer the type of the result of AddAll and don’t provide an interface for it. If we were to do that it would have the name S and have the abstract type t (for the parameters and the result of addAll). It would be used like this:

module AddAll = (A: AddSingle)
: (S with type t := A.t) => {
  ···
};

From the source code, we can deduce what addAll needs and collect that in the interface AddSingle:

module type AddSingle = {
  type elt;
  type t; /* type of data structure */

  let empty: t;
  let fold: ((elt, 'r) => 'r, t, 'r) => 'r;
  let add: (elt, t) => t;
};

AddAll for sets of strings  

We take StringSet that have have previously defined and use it to create StringSetPlus:

module StringSetPlus = {
  include StringSet;
  include AddAll(StringSet);
};

The new module StringSetPlus contains both the module StringSet and the result of applying the functor AddAll to the module StringSet. We are doing multiple inheritance between modules, if you will.

This is StringSetPlus in action:

let s1 = StringSetPlus.of_list(["a", "b", "c"]);
let s2 = StringSetPlus.of_list(["b", "c", "d"]);
StringSetPlus.(elements(addAll(~from=s2, s1)));
  /* list(string) = ["a", "b", "c", "d"] */

Could we simplify AddAll?  

At the moment, we need to combine the base module StringSet with the extension AddAll(StringSet) to create StringSetPlus:

module StringSetPlus = {
  include StringSet; /* base */
  include AddAll(StringSet); /* extension */
};

What if we could create it as follows?

module StringSetPlus = AddAll(StringSet);

There are two reasons why we don’t do that.

First, we want to keep the parameter for AddAll and the base of StringSetPlus separate. We’ll need that separation when we use AddAll for lists.

Second, there is no way to implement AddAll so that it extends its parameter. In theory, that would look like this:

module AddAll = (A: AddSingle) => {
  include A;
  ···
};

In practice, including A only includes what is inside the interface AddSingle. That’s generally not enough.

Data structures: polymorphic data types vs. functors  

There are two kinds of data structures provided by ReasonML’s standard library:

  • list and others are implemented as polymorphic data types whose element types are specified via type variables.
  • Set and others are implemented via functors. The element types are specified via modules.

AddAll for lists of strings  

Alas, AddAll works best with data structures implemented via functors. If we want to use it for lists, we must bind the type variable of list('a) to a concrete type (in this case, string). That leads to the following parameter for AddAll:

module AddSingleStringList
: AddSingle with type t = list(string) = {
  type elt = string;
  type t = list(elt);
  let empty = [];
  let fold = List.fold_right;
  let add = (x: elt, coll: t) => [x, ...coll];
};

[This is the simplest solution I could come up with – suggestions for improvements welcome.]

Afterwards, this is how we create and use a module that supports all list operations plus addAll():

module StringListPlus = {
  include List;
  include AddAll(AddSingleStringList);
};

StringListPlus.addAll(~from=["a", "b"], ["c", "d"]);
  /* list(string) = ["a", "b", "c", "d"] */

Material