Applicatives are monoidal

Intro

Prerequisites: I will try to keep this beginner-friendly, you should have familiarity with sum and product types, with the Functor typeclass, with case expressions, and with how typeclasses work in Haskell.

The first thing to know about Applicative is that it has two core operations, pure and <*>. The latter is often called ap or apply but I call it the tie-fighter. The second thing to know is that Applicative is superclassed by Functor, so any type with an Applicative instance must also be a Functor instance.

For both Functor and Applicative the type constructor must be of kind * -> *. Type constructor here means what it says: given a type argument, it constructs a type. Hence it is expressed as a function at the type level. The kind for a functor is two stars, no more and no less. Three stars shalt not be the kind, neither shall it be one.

Let’s look at the typeclass declaration, shall we:

class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

A type constructor together with an Applicative instance, describing how pure and (<*>) behave on that type forms an applicative functor. pure lifts a value (yea, even if that value is a function) into a context by applying a type constructor to it.

You may notice the type signature of <*> closely resembles the type of fmap

fmap ::   (a -> b) -> f a -> f b

<*>  :: f (a -> b) -> f a -> f b

except now our function is also embedded in the f structure – the same type constructor as the a and b values are embedded in.

Another thing that is true but is usually less obvious about Applicative is that any type with an Applicative must be a monoid (or, if a sum type, at least a semigroup). McBride and Paterson say in Applicative Programming with Effects: every monoid induces an applicative functor, and that tells us something interesting: it is the monoid that gives rise to the applicative functor.

Most of the time, you do not need to think about the monoid (or semigroup, ok?) implied by an Applicative. Some instances make it more obvious than others, but it’s always there. This is what this post is primarily meant to demonstrate.

Trouble with tuples

The Applicative instance on tuples creates some confusion, and we’re just going to dive right in and see what we can make of it.

The tuple applicative behaves like this:

λ> ("julie", (+8)) <*> (" rocks", 14)
("julie rocks", 22)

The tie-fighter takes a function embedded in some structure – the function here being (+8) – and applies that to a value embedded in (the same type of) structure.

But those String values – what’s happening there? They concatenate, seemingly by magic.

It’s not magic, though; it’s a Monoid constraint:

data (,) a b = (,) a b

instance Monoid a => Applicative ((,) a) where
    pure b = (mempty, b)
    (a, f) <*> (a', b) = (a `mappend` a', f b)

Recall from what you know about Functor that we need to partially apply the type constructor to reduce its arity to * -> *. That application happens, in Haskell at least, left to right. Once we do that, the a is now part of the type constructor. When pure takes a value and embeds it in this type context, it takes a b value and embeds it in a ((,) a) – not (,).

λ> pure (+8) <*> ("hello", 9)
("hello", 17)

We embedded a b (a function, because this is an applicative) in a context. The mempty we used in pure means that the String doesn’t change. That’s what mempty gives us: a way to ensure, parametrically, that a value won’t change.

The b values still do what we expect them to do with the function application.

So we must have a Monoid on the a (or first, or leftmost) value of the tuple to give us an identity value for the a in the case of pure, or to allow us to merge or combine (where sometimes this means “choose one”) a values.

λ> (3, (*10)) <*> (4, 20)
-- no good because the numbers in the a position
-- do not have a Monoid instance!

λ> (First (Just 3), (*10)) <*> (First (Just 4), 20)
(First {getFirst = Just 3}, 200)
-- but specifying a Monoid, even one that chooses one or the other
-- instead of combining them, is a-OK!

Left unsaid here is that there is already a monoid operation merging or unifying the (,) portion of the structure. But it must be so because we need to add a constraint to let us combine the other portion of the structure. The difference is that (,) is not polymorphic, so we already know how to monoidally combine two of those; the a is polymorphic, so we don’t know how until it is applied to a concrete type.

An applicative functor is a functor over some type. When we know what type we’re talking about, then we already know which monoid to rely on to collapse two layers of constructor. But when there’s a polymorphic parameter, we can’t know in advance how to merge those values. We add the constraint to ensure that, for any a, we at least know there is a way. You don’t see the constraint added explicitly for sum types such as Either because the standard applicative functors don’t merge two (or more) a values inside a Left constructor.

We’ll look more at sum types next, and the next post in this series will look at an Either type that does require a (Semigroup, in this case) constraint on the a values because it does merge them instead of returning only one.

Sum type applicatives

There is no explicit Monoid constraint on most Applicative instances, and you do not usually have to consider how the f types will be merged when you write an Applicative instance. Perhaps we can understand why it can be implicit from McBride and Paterson’s phrasing: a monoid induces an applicative functor – the monoid gives rise to the applicative functor. Knowing which monoid we’re talking about it is enough.

With tuples, the accumulation of structure is made explicit to the degree that we can’t accumulate the a portion of the type structure without specifying that there be a Monoid instance for whatever type it is, but the monoidal merging of the (,) portion of the structure is left implicit.

But a typical instance for a sum type does not need a Monoid (or Semigroup) constraint:

data Maybe a = Nothing | Just a

-- the `f` variable is a function so Just (f a) is the function
-- being applied to the a value

instance Applicative Maybe where
  pure = Just
  (<*>) Nothing _ = Nothing
  (<*>) _ Nothing = Nothing
  (<*>) (Just f) (Just a') = Just (f a)

data Either a b = Left a | Right b

instance Applicative (Either a) where
  pure = Right
  (<*>) (Left a) _ = Left a
  -- GHC 7.10 used to print "Left <function>" in this case
  -- but now gives a "No instance for Show" error
  (<*>) _ (Left a) = Left a
  (<*>) (Right f) (Right b) = Right (f b)

We’ll look at Maybe first. pure is Just because the point of pure is to lift a value into a context. We can most usefully lift a value into a Maybe context by applying the Just constructor to it. (You don’t want Maybe there because function implementations, such as in an instance, are term- or value-level and so we use data constructors and values there, not type constructors which stay up there in the type level.)

Either is similar, but now we have an a on the left. As with tuples, we’ve had to partially apply the Either constructor to get the proper kindedness, so the a, which is wrapped at the value level by the Left constructor, is now part of the type constructor itself. You can try writing this (with a different type name) and changing the implementation to have pure be the left value and see the exciting type error that results, like this:

-- a fake Either
data Choose a b = This a | That b
                  deriving (Eq, Show)

instance Functor (Choose a) where
  fmap _ (This a) = This a
  fmap f (That b) = That (f b)

instance Applicative (Choose a) where
  -- pure _ = This mempty  -- this is possible, if you add a
  -- Monoid constraint but it probably doesn't do what you want
  pure a = This a -- this one will throw a type error
  (<*>) (This a) _ = This a
  (<*>) _ (This a) = This a
  (<*>) (That f) (That b) = That (f b)

An accumulation of context

OK, so back to our monoids. There doesn’t seem to be any monoidal involvement here:

λ> pure (div 12) <*> Just 4
Just 3

λ> pure (++ "Julie") <*> Just " rocks"
Just " rocksJulie"

λ> Just toUpper <*> Just 'j'
Just 'J'

λ> Just toUpper <*> Nothing
Nothing

λ> pure toUpper <*> Right 'j'
Right 'J'

λ> Right (3^) <*> Right 2
Right 9

(sometimes people ask how you even end up with a function embedded in a type context like that, in real code, and we’ll go over that in an upcoming post)

So what’s going on there, where’s the monoid? When we have two f values there, our functor can collapse them into one layer, and implicitly, the operation it uses to do that is the monoid (or semigroup! – since we don’t need the identity for this particular purpose, I suppose this is more accurate) on that type.

When we do this:

Just (+2) <*> Just 2

We accumulate those Just wrappers, conceptually something like this:

(Just Just (+2) 2)

The operation (the function) for the numeric values is specified, but the Justs just … accumulate. The operation that can merge or unify those Justs is left implicit – it’s the Maybe monoid.

Comparing sum and product types

An important difference between sum types and product types that is often taken for granted but is quite noticeable when one is writing instances is that sum types are disjunctive while product types are conjunctive. So, when we talked about Either, a value may be either a Left a or a Right b but not both. Product types, though, require all their parameters to be applied in order to construct a value of the type. Either a b needs to be applied to either an a or a b, but Tuple a b needs to be applied to both a and b. This helps explain why we need a mempty on the a for an implementation of pure for a tuple but not for an Either.

The difference between the sum types and product types is that the a never appears with the b in a sum, but it does in a product.

Outro

Here is the takeaway:

Applicatives are monoidal functors.

Applicative functors accumulate data constructors as they apply their function. With sum types, that accumulation is not visible and relies on an implicit monoidal operation to collapse them (although the type I’ll talk about in the next post gives us a way to visualize this, as we can with tuples). With product types that have multiple parameters, such as tuples, the leftmost type(s) are part of the type constructor, f, but their values must also appear in conjunction with the b values and so we must specify a way to merge or unite the values in the a slot.