How is “a monoid on applicative functors” different than “a monoid in the category of endofunctors”?

Question

Perhaps neither of these statements are categorically precise, but a monad is often defined as "a monoid in the category of endofunctors"; a Haskell Alternative is defined as "a monoid on applicative functors", where an applicative functor is a "strong lax monoidal functor". Now these two definitions sound pretty similar to the ignorant (me), but work out significantly differently. The neutral element for alternative has type f a and is thus "empty", and for monad has type a -> m a and thus has the sense "non-empty"; the operation for alternative has type f a -> f a -> f a, and the operation for monad has type (a -> f b) -> (b -> f c) -> (a -> f c). It seems to me that the real important detail is in the category of endofunctors versus over endofunctors, though perhaps the "strong lax" detail in alternative is important; but that's where I get confused because within Haskell at least, monads end up being alternatives: and I see that I do not yet have a precise categorical understanding of all the details here.

How can it be precisely expresseed what the difference is between alternative and monad, such that they are both monoids relating to endofunctors, and yet the one has an "empty" neutral and the other has a "non-empty" neutral element?

Answer 1

In general, a monoid is defined in a monoidal category, which is a category that defines some kind of (tensor) product of objects and a unit object.

Most importantly, the category of types is monoidal: the product of types a and b is just a type of pairs (a, b), and the unit type is ().

A monoid is then defined as an object m with two morphisms:

eta :: () -> m
mu  :: (m, m) -> m

Notice that eta just picks an element of m, so it's equivalent to mempty, and curried mu becomes mappend of the usual Haskell Monoid class.

So that's a category of types and functions, but there is also a separate category of endofunctors and natural transformations. It's also a monoidal category. A tensor product of two functors is defined as their composition Compose f g, and unit is the identity functor Id. A monoid in that category is a monad. As before we pick an object m, but now it's an endofunctor; and two morphism, which now are natural transformations:

eta :: Id ~> m
mu  :: Compose m m ~> m

In components, these two natural transformations become:

return :: a -> m a
join :: m (m a) -> m a

An applicative functor may also be defined as a monoid in the functor category, but with a more sophisticated tensor product called Day convolution. Or, equivalently, it can be defined as a functor that (laxly) preserves monoidal structure.

Alternative is a family of monoids in the category of types (not endofunctors). This family is generated by an applicative functor f. For every type a we have a monoid whose mempty is an element of f a and whose mappend maps pairs of f a to elements of f a. These polymorphic functions are called empty and <|>.

In particular, empty must be a polymorphic value, meaning one value per every type a. This is, for instance, possible for the list functor, where an empty list is polymorphic in a, or for Maybe with the polymorphic value Nothing. Notice that these are all polymorphic data types that have a constructor that doesn't depend on the type parameter. The intuition is that, if you think of a functor as a container, this constructor creates and empty container. An empty container is automatically polymorphic.

Answer 2

Both concepts are tied to the idea of a "monoidal category", which is a category you can define the concept of a monoid in (and certain other kinds of algebraic structures). You can think of monoidal categories as: a category defines an abstract notion of functions of one argument; a monoidal category defines an abstract notion of functions of zero arguments or multiple arguments.

A monad is a monoid in the category of endofunctors; in other words, it's a monoid where the product (a function of 2 arguments) and the identity (a function of 0 arguments) use the concept of multi-argument function defined by a particular (bizarre) monoidal category (the monoidal category of endofunctors and composition).

An applicative functor is a monoidal functor. In other words, it's a functor that preserves all the structure of a monoidal category, not just the part that makes it a category. It should be obvious that that means it has mapN functions for functions with any number of arguments, not just functions of one argument (like a normal functor has).

So a monad exists within a particular monoidal category (which happens to be a category of endofunctors), while an applicative functor maps between two monoidal categories (which happen to be the same category, hence it's a kind of endofunctor).

Answer 3

To supplement the other answers with some Haskell code, here is how we might represent the Day convolution monoidal structure @Bartosz Milewski refers to:

data Day f g a = forall x y. Day (x -> y -> a) (f x) (g y)

With the unit object being the functor Identity.

Then we can reformulate the applicative class as a monoid object with respect to this monoidal structure:

type f ~> g = forall x. f x -> g x
class Functor f => Applicative' f
  where
  dappend :: Day f f ~> f
  dempty :: Identity ~> f

You might notice how this rhymes with other familiar monoid objects, such as:

class Functor f => Monad f
  where
  join :: Compose f f ~> f
  return :: Identity ~> f

or:

class Monoid m
  where
  mappend :: (,) m m -> m
  mempty :: () -> m

With some squinting, you might also be able to see how dappend is just a wrapped version of liftA2, and likewise dempty of pure.