An Introduction to Applicative Functors

In a previous post I talked about functors, data types which act as a context holding contents which can be mapped over. In this post I’ll talk about applicative functors, or “applicatives”, a subtype of functors for which additional functions are defined. In this post we’ll cover the core of applicatives: their interface, laws, some sample implementations, and their basic uses. This post requires familiarity with functors and currying, but doesn’t assume any other prior functional programming knowledge.

All of the examples in this post are written in JavaScript, using Flow type annotations.

Functions within contexts

Recall that functors can be thought of as providing a context holding some other type, and that for some type Foo to be a functor this function must be defined on it:

function map<A, B>(A => B, Foo<A>) : Foo<B>

map allows us to apply a plain function to a value which is contained in a context, or equivalently, it “lifts” a function on values to the level of a function on contexts holding values. (If this does not sound familiar, I recommend going back to my previous post on functors before continuing.) Applicative functors take this a step further by adding the functions pure and ap.

function pure<A>(A) : Foo<A>
function ap<A, B>(Foo<A => B>, Foo<A>) : Foo<B>

pure places a value into a minimal context, and ap serves the purpose of function application within a context. map let you apply a normal function to a value inside a functor, getting a functor that held a new value in an unchanged functor context. ap goes further; given a function and a value that are both already inside functor contexts, it combines these contexts and puts the result of the function application into the new context.

If you curry ap you can see that it’s equivalent to these functions:

ap<A, B>(Foo<A => B>) => Foo<A> => Foo<B>
ap<A, B>(Foo<A => B>) => (Foo<A> => Foo<B>)

So another way to look at ap is that it lets us turn a function within a context into a function that operates on contexts. Effectively ap can let us lift a function through a functor.

We said before that applicatives are a subtype of functors. We can demonstrate that by showing that for any type where pure and ap are defined, we can trivially define map as well:

function map<A, B>(fn: A => B, a: Foo<A>) : Foo<B> {
  return ap(pure(fn), a);
}

The applicative laws

Just as with functors, the functions in an applicative functor’s interface need to follow a set of mathematical laws. These laws are more complicated than the functor laws; while it’s important to get a general idea of them now, you probably don’t need to sweat the details too much until you’re writing your own applicative functors. The gist of these laws is that when using ap to apply functions to values inside applicatives, things work about the same as when we apply functions to values normally. There are four applicative laws in total:

1. ap(pure(id), u) must always equal u, where id is the identity function x => x and u is an applicative functor. This is called the “identity law”. Here, u is a value already in a context; the identity law tells us that applying the identity function preserves values. (Just like how applying the identity function outside of a context preserves values.) This law also shows that the context created by pure doesn’t change the context of u when they’re combined using ap.
2. Say we have this compose function:

// The definition of function composition in curried form.
compose<A, B, C>(f: B => C) : (A => B) => (A => C) {  
  return (g: A => B) =>
    a => f(g(a));
}
// Compose lets us take a function f of type B => C, and a 
// function g of type A => B, and combine them into one 
// function of type A => C by feeding the result of g into f

and three values of these given types:

u : Foo<B => C>,
v : Foo<A => B>,
w : Foo<A>

Then ap(ap(ap(pure(compose), u), v), w) must be equal to ap(u, ap(v, w)) . This is called the “composition law”, and it means that using ap to compose functions contained within applicatives is the same as using normal function composition inside of an applicative.

3. ap(pure(f), pure(x)) must always equal pure(f(x)). This is called the “homomorphism law”. This law means that it doesn’t matter if we apply functions to values before or after putting them into a pure context; we’ll get the same result either way.

4. ap(u, pure(x)) must always equal ap(pure(f => f(x)), u). This is known as the “interchange law”. Here u is an applicative which holds some function A => B, and x is something of type A. f => f(x) is just function application to some x, so the interchange law shows us that function application works the same whether we use ap to apply a function to an applicative value or pure to lift normal function application into a context.

If these all seem very abstract, that’s okay. The most important take-away while learning to use applicatives is that ap behaves like normal function application, just inside of a functor, and that pure produces contexts that can be combined with other contexts, without modifying the other context.

That said, once you start writing your own applicatives, these laws are very important and very valuable. The applicative laws allow us to know a lot about the behavior of any given applicative without looking at its internal implementation. As we’ll see in later in this post, it’s easy to swap out one applicative for another without changing the structure of code which operates on applicatives; if we were afraid of an applicative having some strange quirk in its implementation, we wouldn’t be able to do this.

In general, laws establish a set of ways in which an abstraction cannot leak and allow us to build abstractions which are truly generic. This is very different from polymorphism without laws, where two abstractions which implement the same interface may behave wildly and unpredictably differently from one another. So when implementing the applicative functions for some type, you should go through each of the laws and make sure they hold for your instance, because this will ensure that other developers’ intuition about your applicative’s behavior will be correct.

Simple examples

Let’s look at the applicative implementation of three types from the last post: Set, Promise, and Maybe. First up, Set:

function pureSet<A>(a: A) : Set<A> {
  return new Set().add(a);
}
function apSet<A, B>(fnSet: Set<A => B>, aSet: Set<A>) : Set<B> {
  const result = new Set();
  for (const fn of fnSet) {
    for (const a of aSet) {
      result.add(fn(a));
    }
  }
  return result;
}

The pure implementation for Set just creates a set with a single given element in it. The ap implementation produces a new set containing the results of applying each function from the first set to each value of the second. We can see apSet in action:

const fns = new Set([
  x => x * 2,
  x => x + 1,
  x => x * x]);
const numbers = new Set([1, 2, 3, 4]);
console.log(apSet(fns, numbers));
// Set { 2, 4, 6, 8, 3, 5, 1, 9, 16 }

Note that while we have three functions and four numbers, for a result of 12 pairings, there are only 9 values in the resulting set. It’s Set context’s behavior that duplicate values are only saved once.

The implementation of Promise's applicative functions is even simpler than Set's:

function purePromise<A>(a: A) : Promise<A> {
  return Promise.resolve(a);
}
function apPromise<A, B>(fnPromise: Promise<A => B>,
                         aPromise: Promise<A>) : Promise<B> {
  return fnPromise.then(fn => aPromise.then(a => fn(a)));
}

This does exactly what one might expect, applying a function in a promise to a value in a promise:

const squarePromise = purePromise(x => x * x),
      threePromise = purePromise(3);
apPromise(squarePromise, threePromise)
  .then(x => console.log(x)); // 9

Finally let’s implement an instance for Maybe. Recall that Maybe gives us a safe way to express that a value might be null:

type Maybe<A> = null | Just<A>;
class Just<A> {
  value: A;
  constructor(value) {
    this.value = value;
  }
}

Because Maybe is a union type, we have more decisions to make when implementing its applicative interface. Fortunately we have guidance; there’s only one possible implementation which satisfies the applicative laws.

function pureMaybe<A>(a: A) : Maybe<A> {
  return new Just(a);
}
function apMaybe<A, B>(fn: Maybe<A => B>, a: Maybe<A>) : Maybe<B> {
  return fn === null || a === null ?
    null :
    new Just(fn.value(a.value));
}

We can see this in action as well:

console.log(apMaybe(
  pureMaybe(x => x + 1),
  pureMaybe(3))); // Just { value: 4 }
console.log(apMaybe(null, pureMaybe(3))); // null
console.log(apMaybe(pureMaybe(x => x + 1), null)); // null
console.log(apMaybe(null, null)); // null

The functor instance of Maybe allowed us to safely apply a function to a value which might be null. Maybe's applicative functor instance allows us to do the same when the function may be null as well.

Working with functions of multiple arguments

When looking at the signature for ap, you may find yourself wondering why you’d end up with a function inside a functor in the first place. The trick with applicatives is that ap usually isn’t used when you just incidentally find yourself with a functor full of functions; it’s more common purpose is to let us work with functions that we’ve lifted ourselves, using pure.

As an example, lets say we have two sets of numbers. We want to subtract every number in the second set from every number in the first, and get a set of the answers. For subtraction we’ll use this function:

function subtract(x: number, y: number) : number {
  return x - y;
}

We want to find a way to use subtract with things of type Set<number>, but we face a problem: map and ap only work with unary functions (functions that take a single argument), while subtract is a binary function (taking two arguments). We can convert subtract into a unary function by currying it:

const curriedSubtract = curry2(subtract);

Now curriedSubtract has the type number => (number => number); it takes a number and returns a function. If we use map to apply curriedSubtract to a set of numbers, then we’ll get a set of functions:

const nums = new Set([5, 6, 7]);
const fns = mapSet(curriedSubtract, nums);

Here fns has the type Set<number => number>. Using curry2 and mapSet, we’ve made three functions by binding each number in the input set to the first argument to subtract. fns is thus equivalent to a set like this:

new Set([
  x => subtract(5, x)
  x => subtract(6, x),
  x => subtract(7, x)
])

Now that we have a set of functions, we can use ap to apply it to a set of numbers:

console.log(apSet(fns, new Set([1, 2, 3])));
// Set { 4, 3, 2, 5, 6 }

If we put these steps in one line, we end up with this:

apSet(mapSet(curriedSubtract, new Set([5, 6, 7])),
      new Set([1, 2, 3]));

In this way we’ve taken subtract, a function whose arguments are each a plain value, and applied it to values inside contexts. In my functor posts I said that the Set context can be thought of as representing something that can have multiple possible values. If you look at it like this, what we’ve said here is “When you take something that is either equal to 1, 2, or 3, and subtract it from something that is either equal to 5, 6, or 7, your answer will be 2, 3, 4, 5, or 6”. Here’s a slightly more complex case:

function isBetween(x: number, y: number, z: number) : boolean {
  return x < y && y < z;
}
apSet(apSet(mapSet(curry3(isBetween), new Set([1, 2])),
            new Set([3, 4, 99])),
      new Set([5, 6]));
// Set { true, false }

We can nest apSet multiple times to work with functions of more arguments. Here we took a function which determines whether one number is between two others, and used it to find out whether any or all all numbers in one set is between those of two other sets.

Hopefully this shows a little bit of the power of applicatives: with the applicative instance of Set, we can write programs that model non-determinism. For any function on normal values, we can “lift” that function to take sets of values, and then use these sets to compute every possible output of the function for the given sets of inputs.

Using pure with nested applications of ap like this is such a common task that it’s helpful to have functions to do it for us:

function liftA2Set<A, B, C>(
  fn: A => B => C,
  s1: Set<A>,
  s2: Set<B>) : Set<C> {
    return apSet(mapSet(fn, s1), s2);
}
function liftA3Set<A, B, C, D>(
  fn: A => B => C => D,
  s1: Set<A>,
  s2: Set<B>,
  s3: Set<C>) : Set<D> {
    return apSet(liftA2Set(fn, s1, s2), s3);
}
function liftA4Set<A, B, C, D, E>(
  fn: A => B => C => D => E,
  s1: Set<A>,
  s2: Set<B>,
  s3: Set<C>,
  s4: Set<D>) : Set<E> {
    return apSet(liftA3Set(fn, s1, s2, s3), s4);
}
// Etc. We can implement liftA for functions of any arity.

liftA takes care of the boilerplate of nesting calls to ap for us, and lets us directly say, “apply this function on normal values to these values in context”. As you might have guessed, liftA stands for “lift applicative”, and the number in the function names is the arity of the function that each function lifts. liftA makes our code much more succinct:

liftA2Set(curry2(subtract), new Set([5, 6, 7]), new Set([1, 2, 3]));
liftA3Set(curry3(isBetween),
          new Set([1, 2]),
          new Set([3, 4]),
          new Set([5, 6]));

If the name “lift” seems weird here, it might be helpful to look at the type of liftA2Set in curried form:

(A => B => C) => Set<A> => Set<B> => Set<C>
// equivalent to
(A => B => C) => (Set<A> => Set<B> => Set<C>)

Viewing it this way, we can see that liftA takes functions on plain values and brings them up into the world of a functor.

While the liftA functions in this section are specific to sets, higher-kinded libraries like flow-static-land provide the functions liftA2 and liftA3 which work on any applicative.

Composing applicatives

An important attribute of applicatives is that they compose. That is, if we combine two applicatives, the result will itself be an applicative. Let’s look at an example of composing Promises with Sets. For this example, we’ll use a function of three arguments, which takes the dimensions of a rectangular prism and returns the prism’s volume:

function prismVolume(length: number, width: number, height: number) : number {
  return length * width * height;
}

Let’s say that we want to compute this volume, but each of the dimensions are inside of promises. We can use Promise’s applicative instance to handle this case.

const length = Promise.resolve(2),
      width = Promise.resolve(3),
      height = Promise.resolve(4);
liftA3Promise(curry3(prismVolume), length, width, height)
  .then(volume => console.log(volume)); // 24

As we covered in the last section, we can do the same thing using sets:

const lengthSet = new Set([2]),
      widthSet = new Set([3, 4]),
      heightSet = new Set([5, 6, 7]);
liftA3Set(curry3(prismVolume),
          lengthSet,
          widthSet,
          heightSet);
// Set { 30, 36, 42, 40, 48, 56 }

If we want to deal with Promises containing Sets, though, things get a little more difficult. Our ap functions apply a function directly to the contents of an applicative, and can’t handle the existence of a second applicative in the middle. The solution is to create a new applicative which is a combination of the Set and Promise applicatives, with its own ap and pure functions. We’ll call this new applicative SetPromise, and we can create it in a mechanical way:

type SetPromise<A> = Promise<Set<A>>;
function pureSetPromise<A>(a: A) : SetPromise<A> {
  return purePromise(pureSet(a));
}
function apSetPromise<A, B>(
  fn: SetPromise<A => B>,
  a: SetPromise<A>) : SetPromise<B> {
  return liftA2Promise(curry2(apSet), fn, a)
}

The implementation of pure for a SetPromise is easy; it’s just normal function composition of purePromise and pureSet. The implementation of ap is more puzzling. liftA2Promise lifts a function whose arguments aren’t promises to work on promise arguments; we can think of it as “peeling away” the promise from the input arguments, and then wrapping the applied function’s output in a promise. So by lifting apSet with liftA2Promise, apSet gets the contents of fn (which has type Promise<Set<A => B>>) and a (which has type Promise<Set<A>>) with their promise layers stripped away. This means apSet gets arguments of type Set<A => B> and Set<A>, just as it expects.

This may seem a little mind-bending, but what’s important is that this implementation is the same no matter what two applicatives we’re composing. If we’re using higher-kinded types, we can implement a composeA function which takes the pure and ap arguments of two applicatives and returns the pure and ap functions of their composition as a result.

Using liftSetPromise and pureSetPromise we can implement liftA on SetPromise, just as we did before. And liftA lets us accomplish our original goal, taking a function on numbers and giving it arguments which are promises of sets of numbers:

const length = Promise.resolve(new Set([2])),
      width = Promise.resolve(new Set([3, 4])),
      height = Promise.resolve(new Set([5, 6, 7]));
liftA3SetPromise(curry3(prismVolume), length, width, height)
  .then(volume => console.log(volume)); 
  // Set { 30, 36, 42, 40, 48, 56 }

As you can see, whether the concrete structure we’re dealing with is a set, a promise, or a combination of the two, applicatives give us a standard way to apply functions to a structure’s contents.

So there’s the basics of applicative functors. By slightly expanding the signature of functors, we’ve greatly increased their capabilities: applicatives let us use normal, context-unaware functions of any arity to work with values inside of contexts. Applicatives are a perfect demonstration of core functional principles. When coding with them, ap and pure encapsulate the internal representation of our abstractions, while normal functions express the computations we want to perform on the contents of these abstractions. This lets calling code focus on the “what” that we want to do to these abstractions, without having to specify the “how” of how to actually tear the structures apart and put them back together. This separation of responsibilities gives us strong abstractions, because we can completely swap out one applicative for another without changing the way we apply functions to their contents. By letting us use normal functions in a wide range of contexts, applicatives can help us keep our code structured, well-factored, and composable.

Further resources

If you want to get more experience working with applicatives, it can be helpful to implement them yourself for some data types. Good candidates are Array<A> and type Thunk<A> = () => A. (Note that there are two different valid implementations for Array.) Whenever you implement an applicative, don’t forget to verify that your implementation obeys the applicative laws.

If you want to make practical use of applicatives in typed code it is helpful to use a library which provides higher-kinded types, like flow-static-land, fp-ts, or funfix. Alternatively, the fantasy-land and static-land specifications give guidance for using applicatives, functors, and other algebraic structures in untyped code. Most of these use the name of to refer to the function pure, but the concepts are the same.

The use of applicative functors isn’t limited to simple structures like sets and promises. More complex applicatives are possible, and can be used to express certain side effects idiomatically in pure code. I’ve written a three-part series about this, which begins here. You can view a complete list of all of my posts on algebraic structures here.

The full source for all of the code in this post may be found here.

Thanks to Lizz Katsnelson for editing this post.