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,
<*>. The latter is often called
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
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:
A type constructor together with an
Applicative instance, describing how
(<*>) 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
except now our function is also embedded in the
f structure – the same type constructor as the
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
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:
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.
String values – what’s happening there? They concatenate, seemingly by magic.
It’s not magic, though; it’s a
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
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.
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”)
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
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
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
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:
(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:
We accumulate those
Just wrappers, conceptually something like this:
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
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
Tuple a b needs to be applied to both
b. This helps explain why we need a
mempty on the
a for an implementation of
pure for a tuple but not for an
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.
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