31

The Typeclassopedia's Monad Transformers section explains:

Unfortunately, monads do not compose as nicely as applicative functors (yet another reason to use Applicative if you don’t need the full power that Monad provides)

Looking at the types of >>= and <*>, the above statement is not clear to me.

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

Please explain the "monads do not compose as nicely as applicative functors."

I read this answer, but could you please give an example to help me understand?

Community
  • 1
  • 1
Kevin Meredith
  • 41,036
  • 63
  • 209
  • 384
  • 6
    Since this is under the "Monad Transformers" section, I believe all this means is that `(Applicative f, Applicative g) => Applicative (C f g)` but its not the case that `(Monad f, Monad g) => Monad (C f g)`, where `data C f g a = C (f (g a))`. If you want a deeper understanding of why this is the case, it may be illustrative to try to write the latter instance. – user2407038 Apr 05 '15 at 04:07
  • 2
    See also [Concrete example showing that monads are not closed under composition (with proof)?](http://stackoverflow.com/q/13034229/1333025) – Petr Apr 05 '15 at 05:13

1 Answers1

45

There are several notions by which types of kind * -> * might "compose". The more important one is you can compose them "sequentially".

newtype Compose f g x = Compose { getCompose :: f (g x) }

Here you can see that Compose has kind (* -> *) -> (* -> *) -> (* -> *) much like any good composition of functors ought to.

So the question is: are there law-abiding instances like the following?

instance (Applicative f, Applicative g) => Applicative (Compose f g)
instance (Monad f,       Monad g)       => Monad       (Compose f g)

And the short answer as to why monads don't compose as well as applicatives is that while the first instance can be written the second cannot. Let's try!

We can warm up with Functor

instance (Functor f,     Functor g)     => Functor     (Compose f g) where
  fmap f (Compose fgx) = Compose (fmap (fmap f) fgx)

Here we see that because we can fmap an fmap-ed f we can pass it through the layers f and g like we need to. A similar game is played with pure

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure a = Compose (pure (pure a))

and while (<*>) appears tricky, if you look carefully it's the exact same trick we used with both fmap and pure.

  Compose fgf <*> Compose fgx = Compose ((<*>) <$> fgf <*> fgx)

In all cases, we can push the operators we need "through" the layers of f and g exactly as we might hope.

But now let's take a look at Monad. Instead of trying to define Monad via (>>=), I'm going to instead work via join. To implement Monad we need to implement

join :: Compose f g (Compose f g x) -> Compose f g x

using

join_f :: f (f x) -> f x  -- and
join_g :: g (g x) -> g x

or, if we strip off the newtype noise, we need

join :: f (g (f (g x))) -> f (g x)

At this point it might be clear what the problem is---we only know how to join consecutive layers of fs or gs, but here we see them interwoven. What you'll find is that we need a commutativity property

class Commute f g where
  commute :: g (f x) -> f (g x)

and now we can implement

instance (Monad f, Monad g, Commute f g) => Monad (Compose f g)

with (the newtype agnostic) join defined as

join :: f (g (f (g x))) -> f (g x)
join fgfgx = fgx where
  ffggx :: f (f (g (g x)))
  ffggx = fmap commute fgfgx
  fggx :: f (g (g x))
  fggx = join_f ffggx
  fgx :: f (g x)
  fgx = fmap join_g fggx

So what's the upshot of all this? Applicatives always Compose, but Monads Compose only when their layers Commute.

When can we commute layers? Here are some examples

instance Commute ((->) x) ((->) y) where
  commute = flip

instance Commute ((,) x) ((,) y) where
  commute (y, (x, a)) = (x, (y, a))

instance Commute ((->) x) ((,) y) where
  commute (y, xa) = \x -> (y, xa x)

-- instance Commute ((,) x) ((->) y) does not exist; try to write yourself!
--
-- OR:
-- It turns out that you need to somehow "travel back in time" to make it
-- work...
-- 
-- instance Commute ((,) x) ((->) y) where
--   commute yxa = ( ..., \y -> let (x, a) = yxa y in a )
J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180
  • 7
    It's probably worth mentioning, that since the `Traversable` type class provides the `sequence` function, which has this type signature: `sequence :: Monad m => t (m a) -> m (t a)`, you can define `NestedMonads` as `type NestedMonads m t = (Monad m, Traversable t, Monad t)` and then `bibind :: NestedMonads m t => m (t a) -> (a -> m (t b)) -> m (t b)`. The [code](http://lpaste.net/130180). – effectfully Apr 05 '15 at 08:23
  • That gives a good intuition as to what `Commute` might do as well, thanks! – J. Abrahamson Apr 05 '15 at 14:57
  • 1
    It might be useful to add here that `Traversable` doesn't appear to be the correct constraint on the inner monad. See the answer [here](http://stackoverflow.com/a/42298943/2684007). – SEC Feb 17 '17 at 18:05