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.
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:
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.
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
.
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 => ···
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;
});
Repetition
The way we have structured module Repetition
is a common pattern for using functors. It has the following parts:
Make
: the functor.Make
(in our case, Count
).S
: an interface for the result of Make
.That is, Repetition
packages the functor Make
and everything it needs.
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.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);
});
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:
S with type t = u
provides more information for S.t
.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;
}
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 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"] */
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.
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"] */