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.


comments powered by Disqus