From Functor to Applicative

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 options. 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 fmaps 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

Further reading

As before, I recommend reading the Haskell Typeclassopedia entry on Applicative Functors. This in turn links to some excellent resources on the subject and addresses the relationship between Applicatives and Monads.

A full code example can be found here.