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

- 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"`

.

- For example,
- 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
```

## 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