blog

# Implementing Functor in OCaml

# March 26, 2012

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.