0branch
⊃ 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:

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:

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.

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:

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,

while Functor expects a type matching

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