blog

# From Functor to Applicative

# March 26, 2012

In the previous post we looked at the Functor structure; now we turn to Applicative Functor. One important enrichment is that applicatives allow for the application of functions that are in some context `t` to values in the same context.

Once more, a couple of definitions to get things rolling,

• Given a function in context, `val f: ('a -> 'b) t`, Applicative Functor provides an operation, `<*>`, such that `f` can be applied to values in like context: `val (<*>) : ('a -> 'b) t -> 'a t -> 'b t`.
• Given a value `'a`, the Applicative Functor function `pure` will lift `'a` into the appropriate (“default” or pure) context: `val pure: 'a -> 'a t`.

Something that I glossed over last time around are the laws associated with the structures under discussion. A module can implement a signature validly while violating these laws. For Functor, the laws are as follows:

1. Mapping the identity function over a value in context `t` should have no effect – i.e., `fmap id = id`.
• For example, `OptionFunctor.fmap (fun x -> x) (Some 5) = Some 5` and `EitherStringFunctor.fmap (fun x -> x) (Left "Oops") = Left "Oops"`.
2. Mapping the composition of functions `g` and `h` over a value in context `t` should be equivalent to mapping function `g` over this value, then mapping function `h` over the output (i.e., the composition of mapping `g` and mapping `h`).

The salient law for Applicative Functor is addressed below.

## Applicative Structure

Let’s begin by providing the signature for an Applicative Functor, defined in terms of `Functor`:

``````module type Functor = sig
type 'a t
val fmap: ('a -> 'b) -> 'a t -> 'b t
end

module type ApplicativeFunctor = sig
include Functor

val pure: 'a -> 'a t
val (<*>): ('a -> 'b) t -> 'a t -> 'b t
val (<\$>): ('a -> 'b)   -> 'a t -> 'b t
end``````

In addition to the signatures mentioned in the introduction, we also define a function (operator) named `<\$>` with a signature identical to `fmap`. Strictly speaking, this should be declared in the `Functor` signature… since we’ll only be using it with applicatives, though, the above factoring will suffice.

## First out of the blocks, option

As before, we’ll start out by implementing something simple – an Applicative Functor module for `option`s. To save some space, only incremental additions will be supplied inline. Here’re our two implementations alongside a simple demo,

``````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 OptionApplicativeF : ApplicativeFunctor
with type 'a t = 'a option = struct
include OptionFunctor

let pure x = Some x

let (<*>) f a = match (f, a) with
(Some f, Some a)    -> Some (f a)
| _                 -> None

let (<\$>) = fmap
end

module Demo1(A: ApplicativeFunctor) = struct
include A
let double x = x * 2
let eg1 x    = double <\$> x
let eg2 x y  = pure (+) <*> x <*> y
let eg3 x y  = (+) <\$> x <*> y
end

module OptionDemo1 = Demo1(OptionApplicativeF)``````

The inheritance relationship indicated in the module signatures is mirrored in in the implementations – `OptionApplicativeF` is defined in terms of `OptionFunctor`: `fmap` is borrowed; `pure`, `<*>` and `<\$>` defined explicitly.

Without further ado, the examples in action:

``````# OptionDemo1.eg1 (Some 5);;
- : int OptionDemo1.t = Some 10

# OptionDemo1.eg1 None;;
- : int OptionDemo1.t = None

# OptionDemo1.eg2 (Some 5) (Some 10);;
- : int OptionDemo1.t = Some 15

# OptionDemo1.eg2 (Some 5) None;;
- : int OptionDemo1.t = None

# OptionDemo1.eg2 None (Some 10);;
- : int OptionDemo1.t = None

# OptionDemo1.eg2 None None;;
- : int OptionDemo1.t = None

# OptionDemo1.eg3 (Some 5) (Some 10);;
- : int OptionDemo1.t = Some 15

# OptionDemo1.eg3 (Some 5) None;;
- : int OptionDemo1.t = None

# OptionDemo1.eg3 None (Some 10);;
- : int OptionDemo1.t = None

# OptionDemo1.eg3 None None;;
- : int OptionDemo1.t = None``````

Notice how `Demo.eg2` and `Demo.eg3` are functionally identical in spite of the variation in their definitions. Where `eg2` raises `+` into context `t` with `pure` before applying `<*>`, `eg3` simply `fmap`s via the convenience operator `<\$>`. This is essentially syntactic sugar, allowing for a pipelined style. Here we’ve hit on the salient law for Applicative Functor:

``fmap g x = pure g <*> x``

or using `<\$>`:

``g <\$> x = pure g <*> x``

Before we leave `OptionApplicativeF`, consider the following case in which the function itself is absent (i.e., `None`) in a `<*>` chain:

``````# None <*> (Some 1) <*> (Some 2);;
- : '_a t = None``````

This follows from definition of `<*>`: unless both the function and its argument are present (`Some _`), the result of `<*>` is `None`.

## Adding either into the mix

To make things more interesting, we’ll re-introduce `either` and provide an `ApplicativeFunctor` implementation:

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

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 EitherApplicativeF(T: Typed) : ApplicativeFunctor
with type 'a t = (T.t, 'a) either = struct
include EitherFunctor(T)

let pure x = Right x

let (<*>) f a = match (f, a) with
(Right f, Right a)  -> Right (f a)
| (Left err, _)     -> Left err
| (_, Left err)     -> Left err

let (<\$>) = fmap
end

(* Demo1 as before *)
module EitherDemo1 = Demo1(EitherApplicativeF(String))``````

As with `OptionFunctorF`, the only success condition accounted for by `<*>` is where both the function and its value are valid – in the `option` case, `Some _` and in the `either` case, `Right _`. If the first clause of `match` can be unified, `f` is applied to `a` and wrapped with the `Right` constructor as an indication of success. In the other two cases, the error (typed `T.t`) is propagated.

The examples in `EitherDemo1` should yield few surprises,

``````# EitherDemo1.eg1 (Right 5);;
- : int EitherDemo1.t = Right 10

# EitherDemo1.eg3 (Right 5) (Right 10);;
- : int EitherDemo1.t = Right 15

# EitherDemo1.eg3 (Right 5) (Left "Oops");;
- : int EitherDemo1.t = Left "Oops"

# EitherDemo1.eg3 (Left "Um") (Left "Oops");;
- : int EitherDemo1.t = Left "Um"

# EitherDemo1.eg3 (Left "Um") (Right 15);;
- : int EitherDemo1.t = Left "Um"``````

## Recognising abstractions

The demonstration functions defined in `Demo1` share a common semantic purpose: generalising a given function `f` so that it can apply in a context `t`. This is known as lifting.

By way of example: Consider the `double` function: this has the signature `val double : int -> int`; in `Demo1.eg1` we wish to lift `double` into context `t` and double whatever value is embedded in this context – in the case of `OptionDemo1` the context is `option`, in `EitherDemo1`, `either`.

Since we’ve recognised and named this process, all that remains is to implement it. To start with, here’s a module signature that declares three lift operations:

``````module type Lift = sig
type 'a t
val lift:  ('a -> 'b) -> 'a t -> 'b t
val lift2: ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
val lift3: ('a -> 'b -> 'c -> 'd) -> 'a t -> 'b t -> 'c t -> 'd t
end``````

where `lift` takes a function from `'a -> 'b` and a single input in context `t`, mapping to `'b t`. `lift2` takes a “two-argument” function (glossing over currying) and performs the same generalisation over a context; similarly for `lift3`.

We can use an OCaml functor to provide a generic implementation of lifting by leveraging `<\$>` and `<*>`:

``````module ApplicativeLift(A: ApplicativeFunctor) : Lift
with type 'a t := 'a A.t = struct
include A
let lift  f a       = f <\$> a
let lift2 f a b     = f <\$> a <*> b
let lift3 f a b c   = f <\$> a <*> b <*> c
end``````

Finally, let’s compose the signatures of `Lift` and `ApplicativeFunctor` to produce a new signature, `Applicative`,

``````(* Composition of ApplicativeFunctor and Lift *)
module type Applicative = sig
include Lift
include ApplicativeFunctor with type 'a t := 'a t
end``````

Note that this use of destructive substitution (`with type 'a t := 'a t`) requires OCaml 3.12 – see the documentation for more information.

With the above in place, we can now define a couple of enriched applicative modules (with less unseemly names),

``````module OptionApplicative : Applicative
with type 'a t = 'a option = struct
include OptionApplicativeF
include ApplicativeLift(OptionApplicativeF)
end

module EitherApplicative(T: Typed) : Applicative
with type 'a t = (T.t, 'a) either = struct
module EA = EitherApplicativeF(T)
include EA
include ApplicativeLift(EA)
end``````

And expand on our earlier set of demos,

``````module Demo2(A: Applicative) = struct
include A
let double x  = x * 2
let eg1 x     = lift double x
let eg2 x y   = lift2 (+) x y
let eg3 x     = double <\$> x
let eg4 x y   = (+) <\$> x <*> y
let eg5 f x y = lift2 f x y
end

module OptionDemo2       = Demo2(OptionApplicative)
module EitherStringDemo2 = Demo2(EitherApplicative(String))
module EitherIntDemo2    = Demo2(EitherApplicative(struct type t = int end))``````

This composed structure proves to be very useful in practice – as a sketch, here’s an example of lifting a function into `either` context:

``````# let foo x y = (x * y) - (x + y);;
val foo : int -> int -> int = <fun>

# EitherStringDemo2.eg5 foo (Left "Err") (Right 10);;
- : int EitherStringDemo2.t = Left "Err"

# EitherStringDemo2.eg5 foo (Right 15) (Right 10);;
- : int EitherStringDemo2.t = Right 125``````