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:

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,

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:

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:

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 <*>:

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

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),

And expand on our earlier set of demos,

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.


comments powered by Disqus