Applicatives compose, monads don't

Question

If we compare the types

(<*>) :: Applicative a => a (s -> t) -> a s -> a t
(>>=) :: Monad m =>       m s -> (s -> m t) -> m t

we get a clue to what separates the two concepts. That (s -> m t) in the type of (>>=) shows that a value in s can determine the behaviour of a computation in m t. Monads allow interference between the value and computation layers. The (<*>) operator allows no such interference: the function and argument computations don't depend on values. This really bites. Compare

miffy :: Monad m => m Bool -> m x -> m x -> m x
miffy mb mt mf = do
  b <- mb
  if b then mt else mf

which uses the result of some effect to decide between two computations (e.g. launching missiles and signing an armistice), whereas

iffy :: Applicative a => a Bool -> a x -> a x -> a x
iffy ab at af = pure cond <*> ab <*> at <*> af where
  cond b t f = if b then t else f

which uses the value of ab to choose between the values of two computations at and af, having carried out both, perhaps to tragic effect.

The monadic version relies essentially on the extra power of (>>=) to choose a computation from a value, and that can be important. However, supporting that power makes monads hard to compose. If we try to build ‘double-bind’

(>>>>==) :: (Monad m, Monad n) => m (n s) -> (s -> m (n t)) -> m (n t)
mns >>>>== f = mns >>-{-m-} \ ns -> let nmnt = ns >>= (return . f) in ???

we get this far, but now our layers are all jumbled up. We have an n (m (n t)), so we need to get rid of the outer n. As Alexandre C says, we can do that if we have a suitable

swap :: n (m t) -> m (n t)

to permute the n inwards and join it to the other n.

The weaker ‘double-apply’ is much easier to define

(<<**>>) :: (Applicative a, Applicative b) => a (b (s -> t)) -> a (b s) -> a (b t)
abf <<**>> abs = pure (<*>) <*> abf <*> abs

because there is no interference between the layers.

Correspondingly, it's good to recognize when you really need the extra power of Monads, and when you can get away with the rigid computation structure that Applicative supports.

Note, by the way, that although composing monads is difficult, it might be more than you need. The type m (n v) indicates computing with m-effects, then computing with n-effects to a v-value, where the m-effects finish before the n-effects start (hence the need for swap). If you just want to interleave m-effects with n-effects, then composition is perhaps too much to ask!

Applicatives compose, monads don't.

Monads do compose, but the result might not be a monad. In contrast, the composition of two applicatives is necessarily an applicative. I suspect the intention of the original statement was that "Applicativeness composes, while monadness doesn't." Rephrased, "Applicative is closed under composition, and Monad is not."

If you have applicatives A1 and A2, then the type data A3 a = A3 (A1 (A2 a)) is also applicative (you can write such an instance in a generic way).

On the other hand, if you have monads M1 and M2 then the type data M3 a = M3 (M1 (M2 a)) is not necessarily a monad (there is no sensible generic implementation for >>= or join for the composition).

One example can be the type [Int -> a] (here we compose a type constructor [] with (->) Int, both of which are monads). You can easily write

app :: [Int -> (a -> b)] -> [Int -> a] -> [Int -> b]
app f x = (<*>) <$> f <*> x

And that generalizes to any applicative:

app :: (Applicative f, Applicative f1) => f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)

But there is no sensible definition of

join :: [Int -> [Int -> a]] -> [Int -> a]

If you're unconvinced of this, consider this expression:

join [\x -> replicate x (const ())]

The length of the returned list must be set in stone before an integer is ever provided, but the correct length of it depends on the integer that's provided. Thus, no correct join function can exist for this type.

Unfortunately, our real goal, composition of monads, is rather more difficult. .. In fact, we can actually prove that, in a certain sense, there is no way to construct a join function with the type above using only the operations of the two monads (see the appendix for an outline of the proof). It follows that the only way that we might hope to form a composition is if there are some additional constructions linking the two components.

Composing monads, http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf

The distributive law solution l : MN -> NM is enough

to guarantee monadicity of NM. To see this you need a unit and a mult. i'll focus on the mult (the unit is unit_N unitM)

NMNM - l -> NNMM - mult_N mult_M -> NM

This does not guarantee that MN is a monad.

The crucial observation however, comes into play when you have distributive law solutions

l1 : ML -> LM
l2 : NL -> LN
l3 : NM -> MN

thus, LM, LN and MN are monads. The question arises as to whether LMN is a monad (either by

(MN)L -> L(MN) or by N(LM) -> (LM)N

We have enough structure to make these maps. However, as Eugenia Cheng observes, we need a hexagonal condition (that amounts to a presentation of the Yang-Baxter equation) to guarantee monadicity of either construction. In fact, with the hexagonal condition, the two different monads coincide.