(Ad, please don’t block.)

Intuitively, a *functor* is a function that takes one or more modules as input and returns a new module. This chapter explains how functors 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:

- 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.

`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.- 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.

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 pairsLet’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 resultIt 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;
}
```

`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 stringsWe 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 stringsAlas, `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"] */
```

- Chap. “The module system” in the OCaml manual
- Chap. “Functors” in “Real World OCaml”
- “Modules” (OCaml.org tutorial)