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.
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:
Future
and Option
should have Monad
instances defined over themOptionT
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:
Future
and Option
should have Applicative
instances defined over themYou 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
Applicative
s 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:
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]]
. 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)G
and F
) is applicative, but not every applicative is a monadF[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 monadThat 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).
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With