# Implementing Functor in OCaml

This post explores the implementation of *Functor* structures (not to be confused with functor) in OCaml.

Let’s begin with some definitions,

- A
*Functor*is (somewhat informally): a structure that provides a*mapping operation*that applies to a*value*in a given*context*, preserving that context. - Put differently: given a function
`val f: 'a -> 'b`

, a*Functor*allows us to apply`f`

to values in some context`t`

such that the mapping operation is of type`'a t -> 'b t`

. - This mapping operation is typically named
`fmap`

and has the type signature`val fmap: ('a -> 'b) -> 'a t -> 'b t`

. The signature of

`fmap`

may be familiar: when`type 'a t = 'a list`

, the`fmap`

function is simply`List.map`

,`# List.map;; - : ('a -> 'b) -> 'a list -> 'b list = <fun>`

## Begin the Begin

The `option`

type seems as good a place to start as any. Let’s state the problem clearly: given some function `f`

that maps from values of type `'a -> 'b`

, how can we apply this `f`

to optional values of type `'a option`

and mantain the optional context? Here’s a preliminary definition of `OptionFunctor`

and some demo code where `f`

is `abs`

:

```
module OptionFunctor = struct
let fmap f = function
Some a -> Some (f a)
| _ -> None
end
module Demo1 = struct
open OptionFunctor
let eg1 = fmap abs (Some 5 )
let eg2 = fmap abs (Some (-5))
let eg3 = fmap abs None
end
```

In keeping with the definition of *Functor*, `OptionFunctor`

provides an `fmap`

function that takes two arguments (we’ll gloss over currying): some function `f`

which maps from `'a -> 'b`

and an argument of type `'a option`

. When the second argument is present (in the form `Some a`

), `f`

is applied to `a`

and wrapped with the `Some`

constructor; otherwise (where the second argument is `None`

), the result is the same.

Less verbosely, `fmap`

has type: `('a -> 'b) -> 'a option -> 'b option`

. Here it is in practice,

```
# Demo1.eg1;;
- : int option = Some 5
# Demo1.eg2;;
- : int option = Some 5
# Demo1.eg3;;
- : int option = None
```

To make this example a little more interesting, let’s introduce another type, `validation`

, and implement a *Functor* instance for it:

```
type 'a validation = Success of 'a | Failure of string
module OptionFunctor = struct
let fmap f = function
Some a -> Some (f a)
| _ -> None
end
module ValidationFunctor = struct
let fmap f = function
Success a -> Success (f a)
| Failure e -> Failure e
end
module Demo1 = struct
open OptionFunctor
let eg1 = fmap abs (Some 5 )
let eg2 = fmap abs (Some (-5))
let eg3 = fmap abs None
end
module Demo2 = struct
open ValidationFunctor
let eg4 = fmap abs (Success 5 )
let eg5 = fmap abs (Success (-5))
let eg6 = fmap abs (Failure "Something went wrong")
end
```

Our validation type has two constructors: `Success`

and `Failure`

– a slight enrichment of the builtin `option`

type through the provision of reason for failure (= absence of value). `ValidationFunctor`

strongly resembles `OptionFunctor`

, the only difference being that a failure string is propagated in the second prong of the `function`

match. The new `Demo2`

module demonstrates usage; calls to `fmap`

look identical, though `validation`

constructors are employed in `Demo2`

:

```
# Demo2.eg4;;
- : int validation = Success 5
# Demo2.eg5;;
- : int validation = Success 5
# Demo2.eg6;;
- : int validation = Failure "Something went wrong"
```

So far, so good – but can we introduce a generic function and use it with both `option`

and `validation`

types? Unsurprisingly, the answer is yes: To do so, let’s introduce a `Functor`

signature and augment our two *Functor* modules with type specifications.

```
type 'a validation = Success of 'a | Failure of string
module type Functor = sig
type 'a t
val fmap : ('a -> 'b) -> 'a t -> 'b t
end
module OptionFunctor = struct
type 'a t = 'a option
let fmap f = function
Some a -> Some (f a)
| _ -> None
end
module ValidationFunctor = struct
type 'a t = 'a validation
let fmap f = function
Success a -> Success (f a)
| Failure e -> Failure e
end
module Demo3(F: Functor) = struct
let eg7 x = F.fmap abs x
let eg8 f x = F.fmap f x
end
module OptionDemo3 = Demo3(OptionFunctor)
module ValidationDemo3 = Demo3(ValidationFunctor)
```

`Demo3`

is a `functor`

in the OCaml sense – a module that is parameterised by another module. Since the parameter `F`

is required to implement the `Functor`

signature (here we’re using structural typing to unify with `OptionDemo`

and `ValidationDemo`

), `fmap`

can be used in the module body. The `abs`

examples simply take a value in context,

```
# OptionDemo3.eg7 (Some 10);;
- : int OptionFunctor.t = Some 10
# OptionDemo3.eg7 None;;
- : int OptionFunctor.t = None
# ValidationDemo3.eg7 (Success 12);;
- : int ValidationFunctor.t = Success 12
# ValidationDemo3.eg7 (Failure "Something went wrong");;
- : int ValidationFunctor.t = Failure "Something went wrong"
```

while `eg8`

allows us to provide a function,

```
# let square x = x * x;;
val square : int -> int = <fun>
# OptionDemo3.eg8 square (Some 4);;
- : int OptionFunctor.t = Some 16
# OptionDemo3.eg8 square None;;
- : int OptionFunctor.t = None
# ValidationDemo3.eg8 square (Success 5);;
- : int ValidationFunctor.t = Success 25
# ValidationDemo3.eg8 square (Failure "Oops");;
- : int ValidationFunctor.t = Failure "Oops"
```

Finally, here’s how we can define a `ListFunctor`

at the toplevel to make use of `Demo3`

:

```
# module ListFunctor = struct type 'a t = 'a list let fmap = List.map end;;
module ListFunctor :
sig type 'a t = 'a list val fmap : ('a -> 'b) -> 'a list -> 'b list end
# module ListDemo3 = Demo3(ListFunctor);;
module ListDemo3 : sig val eg7 : int ListFunctor.t -> int ListFunctor.t end
# ListDemo3.eg7 [1; 2; 3];;
- : int ListFunctor.t = [1; 2; 3]
# ListDemo3.eg7 [1; 2; -3];;
- : int ListFunctor.t = [1; 2; 3]
# ListDemo3.eg7 [];;
- : int ListFunctor.t = []
# ListDemo3.eg8 square [1; 2; 3];;
- : int ListFunctor.t = [1; 4; 9]
# ListDemo3.eg8 square [];;
- : int ListFunctor.t = []
```

## Providing signatures for *Functors*

Above, we used structural typing to match `OptionFunctor`

and `ValidationFunctor`

against the `Functor`

signature. How about defining these modules with the `Functor`

signature at the outset?

First of all, consider what happens when we attempt to create a new module, `OF`

, by signing `OptionFunctor`

with `Functor`

:

```
# module OF = (OptionFunctor : Functor);;
module OF : Functor
# OF.fmap abs (Some 5);;
Error: This expression has type 'a option
but an expression was expected of type int OF.t
```

In specifying a signature, the type representation in `OptionFunctor`

has been *abstracted over*. The same problem is evidenced in the following code,

```
# module type A = sig type t val id: t -> t end;;
module type A = sig type t val id : t -> t end
# module B = struct type t = int let id x = x end;;
module B : sig type t = int val id : 'a -> 'a end
# B.id;;
- : 'a -> 'a = <fun>
# B.id 10;;
- : int = 10
# module C = (B: A);;
module C : A
# C.id;;
- : C.t -> C.t = <fun>
# C.id 10;;
Error: This expression has type int but an expression was expected of type
C.t
```

By defining module `C`

as having signature `A`

, type `C.t`

has been rendered abstract. What we meant to express is that `C`

is a kind of `A`

… and that `type t = int`

. To achieve this, a sharing constraint is necessary:

```
# module D = (B: A with type t = int);;
module D : sig type t = int val id : t -> t end
# D.id 10;;
- : D.t = 10
```

Returning to `OptionFunctor`

and its cousin `OF`

, let’s look more closely at each module’s signature (by using the assign-to-peek trick in the toplevel):

```
# module T = OptionFunctor;;
module T :
sig
type 'a t = 'a option
val fmap : ('a -> 'b) -> 'a option -> 'b option
end
# module T = OF;;
module T :
sig
type 'a t = 'a OF.t
val fmap : ('a -> 'b) -> 'a t -> 'b t
end
```

As anticipated above, `OF.t`

is abstract; to “fix” `fmap`

we’ll need to add a sharing constraint as follows,

```
# module OF2 = (OptionFunctor : Functor with type 'a t = 'a option);;
module OF2 :
sig
type 'a t = 'a option
val fmap : ('a -> 'b) -> 'a t -> 'b t
end
```

Notice that `t`

has a concrete type in `OF2`

while it remains abstract in `OF`

(as seen through `T`

). The provision of a sharing constraint solves the type incompatibility problem,

```
# OF.fmap abs (Some 5);;
Error: This expression has type 'a option
but an expression was expected of type int OF.t
# OF2.fmap abs (Some 5);;
- : int OF2.t = Some 5
```

So: is it worth explicitly specifying the signature or not in light of the potential confusion caused by sharing constraints? On the one hand, explicit specification buys encapsulation and compile-time safety – the compiler will alert us to missing definitions. On the other, constraint provision is required to prevent nasty surprises from arising – perhaps we could make do with structural typing.

Since ensuring that implementations satisfy the conditions of formal categories (in this case, *Functor*) is desirable, explicit signatures will be employed for the remainder of the post. This is by no means required for what follows though.

## Back to the code

As a final step, let’s introduce an `either`

type – more general than `validation`

in that its failure type is parametric – and `Functor`

signatures for all of our implementations:

```
type 'a validation = Success of 'a | Failure of string
type ('a, 'b) either = Left of 'a | Right of 'b
module type Functor = sig
type 'a t
val fmap : ('a -> 'b) -> 'a t -> 'b t
end
module OptionFunctor : Functor
with type 'a t = 'a option = struct
type 'a t = 'a option
let fmap f = function
Some a -> Some (f a)
| _ -> None
end
module ValidationFunctor : Functor
with type 'a t = 'a validation = struct
type 'a t = 'a validation
let fmap f = function
Success a -> Success (f a)
| Failure e -> Failure e
end
module ListFunctor : Functor
with type 'a t = 'a list = struct
type 'a t = 'a list
let fmap = List.map
end
(* Signature of any module providing its type in `t' *)
module type Typed = sig type t end
module EitherFunctor(T: Typed) : Functor
with type 'a t = (T.t, 'a) either = struct
type 'a t = (T.t, 'a) either
let fmap f = function
Right r -> Right (f r)
| Left l -> Left l
end
module Demo3(F: Functor) = struct
let eg7 x = F.fmap abs x
let eg8 f x = F.fmap f x
end
module OptionDemo3 = Demo3(OptionFunctor)
module ValidationDemo3 = Demo3(ValidationFunctor)
module ListDemo3 = Demo3(ListFunctor)
module EitherDemo3 = Demo3(EitherFunctor(String))
```

Here `EitherFunctor`

is an (OCaml) `functor`

(i.e., a module parameterised with another module). The module argument must satisfy the signature `Typed`

by providing a type member `t`

; this is used for the `Left`

(failure) case.

```
# EitherDemo3.eg7 (Right 12);;
- : int EitherFunctor(String).t = Right 12
# EitherDemo3.eg7 (Left "Something went wrong");;
- : int EitherFunctor(String).t = Left "Something went wrong"
# EitherDemo3.eg8 square (Right 12);;
- : int EitherFunctor(String).t = Right 144
# EitherDemo3.eg8 square (Left "Oh dear");;
- : int EitherFunctor(String).t = Left "Oh dear"
```

Why do we need to use a `functor`

here? The answer lies with the arity of `Functor.t`

. Recall that `either`

is defined as,

`type ('a, 'b) either = Left of 'a | Right of 'b`

while `Functor`

expects a type matching

`type 'a t`

Without the `functor`

, we’d receive a signature mismatch error.

## Applicative Functors

Next time we’ll look at *Applicative Functor*, built on top of the `Functor`

modules described in this post.

For more information on *Functor*, the Haskell Typeclassopedia is an excellent reference.

comments powered by Disqus