Why do monads not compose in scala

Why do monads not compose when a Monad is an Applicative and an Applicative is a Functor. You see this inheritance chain in many articles on the web ( Which i have gone through ). But when Functors and Applicatives compose why do Monads break this ?

Can someone provide a simple example in scala which demonstrates this issue ? I know this is asked a lot but kind of hard to understand without a simple example.

回答1:

First, let's start with a simple problem. Let's say, we need to get a sum of two integers, each wrapped in both Future and Option. Let's take cats library in order to resemble Haskell’s standard library definitions with Scala-syntax.

If we use monad approach (aka flatMap), we need:

both Future and Option should have Monad instances defined over them
we also need monadic transformer OptionT which will work only for Option (precisely F[Option[T]])

So, here is the code (let's forget about for-comprehension and lifting to make it simpler):

val fa = OptionT[Future, Int](Future(Some(1)))
val fb = OptionT[Future, Int](Future(Some(2)))
fa.flatMap(a => fb.map(b => a + b)) //note that a and b are already Int's not Future's

if you look at OptionT.flatMap sources:

def flatMap[B](f: A => OptionT[F, B])(implicit F: Monad[F]): OptionT[F, B] =
  flatMapF(a => f(a).value)

def flatMapF[B](f: A => F[Option[B]])(implicit F: Monad[F]): OptionT[F, B] =
  OptionT(F.flatMap(value)(_.fold(F.pure[Option[B]](None))(f)))

You'll notice that the code is pretty specific to Option's internal logic and structure (fold, None). Same problem for EitherT, StateT etc.

Important thing here is that there is no FutureT defined in cats, so you can compose Future[Option[T]], but can't do that with Option[Future[T]] (later I'll show that this problem is even more generic).

On the other hand, if you choose composition using Applicative, you'll have to meet only one requirement:

both Future and Option should have Applicative instances defined over them

You don't need any special transformers for Option, basically cats library provides Nested class that works for any Applicative (let's forget about applicative builder's sugar to simplify understanding):

val fa = Nested[Future, Option, Int](Future(Some(1)))
val fb = Nested[Future, Option, Int](Future(Some(1)))
fa.map(x => (y: Int) => y + x).ap(fb)

Let's swap Option and Future:

val fa = Nested[Option, Future, Int](Some(Future(1)))
val fb = Nested[Option, Future, Int](Some(Future(1)))
fa.map(x => (y: Int) => y + x).ap(fb)

Works!

So yes Monad is Applicative, Option[Future[T]] is still a monad (on Future[T] but not on T itself) but it allows you to operate only with Future[T] not T. In order to "merge" Option with Future layers - you have to define monadic transformer FutureT, in order to merge Future with Option - you have to define OptionT. And, OptionT is defined in cats/scalaz, but not FutureT.

In general (from here):

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 component

And this composition is not even necessary commutative (swappable) as I demonstrated for Option and Future.

As an exercise, you can try to define FutureT's flatMap:

def flatMapF[B](f: A => F[Future[B]])(implicit F: Monad[F]): FutureT[F, B] = 
   FutureT(F.flatMap(value){ x: Future[A] =>
      val r: Future[F[Future[B]] = x.map(f)
      //you have to return F[Future[B]] here using only f and F.pure, 
      //where F can be List, Option whatever
   })

basically the problem with such implementation is that you have to "extract" value from r which is impossible here, assuming you can't extract value from Future (there is no comonad defined on it) at least in a "non-blocking" context (like ScalaJs). This basically means that you can't "swap" Future and F, like Future[F[Future[B]] => F[Future[Future[B]. The latter is a natural transformation (morphism between functors), so that explains the first comment on this general answer:

you can compose monads if you can provide a natural transformation swap : N M a -> M N a

Applicatives however don't have such problems - you can easily compose them, but keep in mind that result of composition of two Applicatives may not be a monad (but will always be an applicative). Nested[Future, Option, T] is not a monad on T, regardless that both Option and Future are monads on T. Putting in simple words Nested as a class doesn't have flatMap.

It would be also helpful to read:

http://typelevel.org/cats/tut/applicative.html
http://typelevel.org/cats/tut/apply.html
http://typelevel.org/cats/tut/monad.html
http://typelevel.org/cats/tut/optiont.html

Putting it all together (F and G are monads)

F[G[T]] is a monad on G[T], but not on T
G_TRANSFORMER[F, T] required in order to get a monad on T from F[G[T]].
there is no MEGA_TRANSFORMER[G, F, T] as such transformer can't be build on top of monad - it requires additional operations defined on G (it seems like comonad on G should be enough)
every monad (including G and F) is applicative, but not every applicative is a monad
in theory F[G[T]] is an applicative over both G[T] and T. However scala requires to create NESTED[F, G, T] in order to get composed applicative on T (which is implemented in cats library).
NESTED[F, G, T] is applicative, but not a monad

That means you can compose Future x Option (aka Option[Future[T]]) to one single monad (coz OptionT exists), but you can't compose Option x Future (aka Future[Option[T]]) without knowing that Future is something else besides being a monad (even though they’re inherently applicative functors - applicative is not enough to neither build a monad nor monad transformer on it) . Basically:

OptionT can be seen as non-commutative binary operator defined as OptionT: Monad[Option] x Monad[F] -> OptionT[F, T]; for all Monad[F], T; for some F[T]. Or in general: Merge: Monad[G] x Monad[F] -> Monad[Merge]; for all T, Monad[F]; but only for **some of Monad[G]**, some F[T], G[T];
you can compose any two applicatives into one single applicative Nested: Applicative[F] x Applicative[G] -> Nested[F, G]; for all Applicative[F], Applicative[G], T; for some F[T], G[T],
but you can compose any two monads (inherently functors) only into one applicative (but not into monad).

回答2:

Tony Morris gave a talk on monad transformers that explains this precise issue very well.

http://tonymorris.github.io/blog/posts/monad-transformers/

He uses haskell, but the examples are easily translatable to scala.