λ Tony's blog λ

The weblog of Tony Morris

Posted on February 24, 2011, in Programming

On the Scala mailing list, I said “monads do not compose.” What does this mean exactly? Hopefully the following answers it.

Let us first state the `Functor`

, `Applicative`

and `Monad`

interfaces:

```
trait Functor[F[_]] {
def fmap[A, B](f: A => B, a: F[A]): F[B]
}
trait Applicative[F[_]] extends Functor[F] {
def ap[A, B](f: F[A => B], a: F[A]): F[B]
def point[A](a: A): F[A]
override final def fmap[A, B](f: A => B, a: F[A]) =
ap(point(f), a)
}
trait Monad[F[_]] extends Applicative[F] {
def flatMap[A, B](f: A => F[B], a: F[A]): F[B]
override final def ap[A, B](f: F[A => B], a: F[A]) =
flatMap((ff: A => B) => fmap((aa: A) => ff(aa), a), f)
}
```

Let’s now restate our claims:

Functors compose

Applicatives compose

Monads do not compose

I will now address points 1) and 2). What does it mean for X to compose in this context? Let us now answer that question more succinctly:

It means that we can write a function with this signature (for some X):

```
def XCompose[M[_], N[_]](implicit mx: X[M], nx: X[N]):
X[({type λ[α]=M[N[α]]})#λ]
```

This return type may look like gobbledy, but it’s just a fancy way of doing partial type constructor application in Scala. It is essentially the X type constructor applied to the composition of M and N and followed by a type variable just like M and N itself (kind * -> *). Let us now test our claims.

Functors compose. That is to say, we can write:

```
def FunctorCompose[M[_], N[_]]
(implicit mx: Functor[M], nx: Functor[N]):
Functor[({type λ[α]=M[N[α]]})#λ]
```

Let’s do it!

```
new Functor[({type λ[α]=M[N[α]]})#λ] {
def fmap[A, B](f: A => B, a: M[N[A]]) =
mx.fmap((na: N[A]) => nx.fmap(f, na), a)
}
```

Here we are composing two Functors. Claim 1) is demonstrated. What about claim 2)? Here we go. Hold your breath!

```
def ApplicativeCompose[M[_], N[_]]
(implicit ma: Applicative[M], na: Applicative[N]):
Applicative[({type λ[α]=M[N[α]]})#λ] =
new Applicative[({type λ[α]=M[N[α]]})#λ] {
def ap[A, B](f: M[N[A => B]], a: M[N[A]]) = {
def liftA2[X, Y, Z](f: X => Y => Z, a: M[X], b: M[Y]): M[Z] =
ma.ap(ma.fmap(f, a), b)
liftA2((ff: N[A => B]) => (aa: N[A]) => na.ap(ff, aa), f, a)
}
def point[A](a: A) =
ma point (na point a)
}
```

Have fun untangling that! It’s a bit noisy but this is mostly because Scala requires a lot of boilerplate. Hopefully you can get to the essence of what it means to compose two Applicative functors.

Now let’s move to Monad. Essentially, I am saying that you won’t be able to write such a function for Monad. I really encourage you to try to write it so you can see the twist that you will get into.

```
def MonadCompose[M[_], N[_]](implicit ma: Monad[M], na: Monad[N]):
Monad[({type λ[α]=M[N[α]]})#λ]
```

Here is a compilable version http://paste.pocoo.org/show/343606/

Hope that helps!