31

I was able to map Functor's definition from category theory to Haskell's definition in the following way: since objects of Hask are types, the functor F

  • maps every type a of Hask to the new type F a by, roughly saying, prepending "F " to it.
  • maps every morphism a -> b of Hask to the new morphism F a -> F b using fmap :: (a -> b) -> (f a -> f b).

So far, so good. Now I get to the Applicative, and can't find any mention of such a concept in textbooks. By looking at what it adds to Functor, ap :: f (a -> b) -> f a -> f b, I tried to come up with my own definition.

First, I noticed that since (->) is also a type, morphisms of Hask are objects of it too. In light of this, I made a suggestion that applicative functor is a functor that also can map "arrow"-objects of source category into morphisms of the destination one.

Is this a right intuition? Can you provide a more formal and rigorous definition?

jub0bs
  • 60,866
  • 25
  • 183
  • 186
arrowd
  • 33,231
  • 8
  • 79
  • 110

2 Answers2

46

The key to understanding applicative functors is to figure out what structure they preserve.

Regular functors preserve the basic categorical structure: they map objects and morphisms between categories, and they preserve the laws of the category (associativity and identity).

But a category may have more structure. For instance, it may allow the definition of mappings that are like morphisms but take multiple arguments. Such mappings are defined by currying: e.g., a function of two arguments is defined as a function of one argument returning another function. This is possible if you can define an object that represents a function type. In general, this object is called an exponential (in Haskell, it's just the type b->c). We can then have morphisms from one object to an exponential and call it a two-argument morphism.

The traditional definition of an applicative functor in Haskell is based on the idea of mapping functions of multiple arguments. But there is an equivalent definition that splits the multi-argument function along a different boundary. You can look at such a function as a mapping of a product (a pair, in Haskell) to another type (here, c).

a -> (b -> c)  ~  (a, b) -> c

That allows us to look at applicative functors as functors that preserve the product. But a product is just one example of what is called a monoidal structure.

In general, a monoidal category is a category equipped with a tensor product and a unit object. In Haskell, this could be, for instance, the cartesian product (a pair) and the unit type (). Notice, however that monoidal laws (associativity and unit laws) are valid only up to an isomorphism. For instance:

(a, ())  ~  a

An applicative functor could then be defined as a functor that preserves monoidal structure. In particular, it should preserve the unit and the product. It shouldn't matter whether we do the "multiplication" before or after applying the functor. The results should be isomorphic.

However, we don't really need a full-blown monoidal functor. All we need is two morphisms (as opposed to isomorphisms) -- one for multiplication and one for unit. Such a functor that half-preserves the monoidal structure is called a lax monoidal functor. Hence the alternative definition:

class Functor f => Monoidal f where
  unit :: f ()
  (**) :: f a -> f b -> f (a, b)

It's easy to show that Monoidal is equivalent to Applicative. For instance, we can get pure from unit and vice versa:

pure x = fmap (const x) unit
unit = pure ()

The applicative laws follow simply from the preservation of monoid laws (associativity and unit laws).

In category theory, preservation of monoidal structure is related to tensorial strength, so an applicative functor is also known as a strong lax monoidal functor. However, in Hask, every functor has canonical strength with respect to the product, so this property doesn't add anything to the definition.

Now, if you're familiar with the definition of a monad as a monoid in the category of endofunctors, you might be interested to know that applicatives are, similarly, monoids in the category of endofunctors where the tensor product is the Day convolution. But that's much harder to explain.

Bartosz Milewski
  • 11,012
  • 5
  • 36
  • 45
  • 1
    What is this "strength" stuff? – dfeuer Jan 27 '16 at 22:41
  • Yes, if you can add a bit on what "strength" means here it would be clarifying; especially since leftaroundabout's answer links to https://en.wikipedia.org/wiki/Monoidal_functor which appears to define "strong monoidal functors" to mean "monoidal functor with some constraints assumed" and "lax monoidal functors" to mean "no additional assumptions", so in that terminology "strong lax monoidal functor" doesn't seem to make sense. – Ben Jan 28 '16 at 00:19
  • 8
    I personally prefer to think of applicative functors as 'closed functors' rather than monoidal ones. The fact that they are monoidal is more or less coincidental, and forced by the preservation of exponentials, which is why the 'Monoidal' encoding of things feels so messy, whereas the `(<*>) :: f (a -> b) -> f a -> f b` combinator that we use is precisely the mapping of exponentials! Another way to think about an Applicative is as a monoid object with respect to (covariant) Day convolution. That view has the benefit that it illuminates the path to finding a contravariant form of Applicative. – Edward Kmett Jan 28 '16 at 19:01
  • 4
    It made much more sense to me when i mentally uncurried `(**)` into `(f a, f b) -> f (a, b)`. I wonder why didn't you wrote it this way in first place. – arrowd Feb 04 '16 at 13:47
  • @arrowd: in fact, a perhaps even “deeper” variant is `((a,b)->c) -> (f a,f b)->f c`, reflecting that the functor translates the monoidal structure of one category to that of another (though both categories are **Hask** here). – leftaroundabout Feb 16 '16 at 23:51
  • `(**)` is Haskell's `liftA2` which is a second possible minimal definition of Applicative together with `pure` – oquechy Mar 14 '22 at 12:19
15

You're right, Applicative translates less straightforwardly than Functor or Monad. But in essence, it is the class of monoidal functors:

class Functor f => Monoidal f where
  pureUnit :: f ()
  fzip :: f a -> f b -> f (a,b)

From that you can define – within Hask

pure x = fmap (const x) pureUnit

and

fs <*> xs = fmap (uncurry ($)) $ fzip fs xs

See this answer for a full proof that Applicative and Monoidal are really equivalent.

leftaroundabout
  • 117,950
  • 5
  • 174
  • 319