Monad Transformers for the working programmer

A practical introduction to Monad Transformers, with a problem-to-solution approach.

There you go, you sit at your desk, sip on your coffee, and get ready to write some more Scala code. Functional programming is not so scary as you thought, life is good, you stretch your muscles and your brain and start sketching down that new feature you need to deliver this week.

It’s a day like many others: some glorious oneliners (yay, Scala!), some strange bugs (oh, no, Scala!), some regrets about those oneliners... Then, you face a strange problem: your for-comprehension doesn’t compile. “No big deal”, you think, “let me check on StackOverflow” just like you do every day. Like all of us do every day.

Except, this is going to be a bad day.

At first, you thought the top answer was being unnecessarily clever. Most of the times you scroll down, find a simpler solution and dismiss the mathematical-category-theory-monad-ponies solution without too much remorse.

But this time is different, this time the second answer is similar to the first, and the third, and the fourth. What’s going on?

Monad. Transformers.

Even the name sounds intimidating.

What was your problem again?

It all started when you sketched down your feature

def findUserById(id: Long): Future[User] = ???
def findAddressByUser(user: User): Future[Address] = ???

It looked so elegant at first:Future represents an asynchronous computation and it has a flatMap method, which means you can place it into a for-comprehension. Brilliant!

def findAddressByUserId(id: Long): Future[Address] =
  for {
    user    <- findUserById(id)
    address <- findAddressByUser(user)
  } yield address

Then, the sudden realization: not every possible ID corresponds to an existing user. What if a user can’t be found? Oh, well, doesn’t Option serve just the purpose?

def findUserById(id: Long): Future[Option[User]] = ???

and — now that you think of it — some users don’t even have an address!

def findAddressByUser(user: User): Future[Option[Address]] = ???

Let’s get back to work… oh, compile error?

def findAddressByUserId(id: Long): Future[Address] =
  for {
    user    <- findUserById(id)
    address <- findAddressByUser(user)
  } yield address

Right, the return type is Future[Option[Address]] now

def findAddressByUserId(id: Long): Future[Option[Address]] =
  for {
    user    <- findUserById(id)
    address <- findAddressByUser(user)
  } yield address

Happy now? Let’s get back to w… wait, again?! What’s wrong now?

error: type mismatch;
 found   : Option[User]
 required: User
           address <- findAddressByUser(user)

That doesn’t look good… After thinking for a while, you realize that <- is just a fancy way of writing flatMap and that if you flatMap over a Future[Option[User]] you get to work with a Option[User] . Too bad you needed a User…

You try a few alternatives, but none of them look good. The best you can come up with looks like:

def findAddressByUserId(id: Long): Future[Option[Address]] =
  findUserById(id).flatMap {
    case Some(user) => findAddressByUser(user)
    case None       => Future.successful(None)
  }

Horrible, or — at least — not as beautiful as before.

Ideally you would want something like

def findAddressByUserId(id: Long): Future[Option[Address]] =
  for {
    user    <- userOption    <- findUserById(id)
    address <- addressOption <- findAddressByUser(user)
  } yield address

A sort of double flatMap to extract both from the Option and from the Future . But nobody mentions anything like that on StackOverflow…

So, what’s the real problem here? Why can’t we just have a superflatMap that works on Future[Option[X]] ?

Dear reader, take a deep breath: we are going to mention some theoretical stuff, but don’t despair. Here’s everything you need to know to follow along:

1. A Functor is a structure with a map function.

2. A Monad is a structure with a flatMap function.

That’s it. I promise.

Some basic knowledge from category theory helps solving the mystery.

If you have two Functors for A and B (i.e. you know how to map over A and over B), you can compose them together, without knowing anything else. This means that you can take A[B[X]] and derive a Functor[A[B[X]] by composing Functor[B] and Functor[A] .

In other terms, if you know how to map over A[X] and over B[X] you also know how to map over A[B[X]]. Automagically. For free.

This is untrue for Monad: knowing how to flatMap over A[X] and B[X] doesn’t grant you the power of magically deriving a flatMap for A[B[X]] .

It turns out this is a well known fact: Monads do not compose, at least not generically.

So, yeah, Monads may not compose generically, but you only need a flatMap (and a map) that works for Future[Option[A]].

We can certainly do that: let’s write a wrapper for Future[Option[A]] that provides its own map and flatMap.

case class FutOpt[A](value: Future[Option[A]]) {
 
  def map[B](f: A => B): FutOpt[B] =
    FutOpt(value.map(optA => optA.map(f)))
  def flatMap[B](f: A => FutOpt[B]): FutOpt[B] =
    FutOpt(value.flatMap(opt => opt match {
      case Some(a) => f(a).value
      case None => Future.successful(None)
    }))
}

Not too bad! Let’s take it for a spin!

def findAddressByUserId(id: Long): Future[Option[Address]] =
  (for {
    user    <- FutOpt(findUserById(id))
    address <- FutOpt(findAddressByUser(user))
  } yield address).value

It works! 🎉

This is great if you have a Future[Option[A]] but what if you have — say — a List[Option[A]]? Maybe another wrapper? Let’s try:

case class ListOpt[A](value: List[Option[A]]) {
 
 def map[B](f: A => B): ListOpt[B] =
    ListOpt(value.map(optA => optA.map(f)))
 def flatMap[B](f: A => ListOpt[B]): ListOpt[B] =
    ListOpt(value.flatMap(opt => opt match {
      case Some(a) => f(a).value
      case None => List(None)
    }))
}

Mmh, that looks similar to FutOpt, doesn’t it?

If you look closely, you’ll realize we don’t need to know anything specific about the “outer” Monad (Future and List from the previous examples). As long as we can map and flatMap over it, we’re fine. On the other hand, see how we destructured the Option? That’s some specific knowledge about the “inner” Monad (Option in this case) that we need to have.

With this piece of information in our pocket, we can write a generic data structure that “wraps” any Monad M around an Option.

Here’s the shocking news: we’ve just accidentally invented a Monad Transformer, usually named OptionT! 😱

OptionT has two type parameters F and A, where F is the wrapping Monad and A is type inside Option: in other words, OptionT[F, A] is a flat version of F[Option[A]] that has its own map and flatMap.

OptionT[F, A] is a flat version of F[Option[A]] which is a Monad itself

Notice that OptionT is also a monad, so we can use it in a for-comprehension (that was exactly the point, after all).

If you use libraries like cats many Monad Transformers (OptionT, EitherT, …) are already available.

Let’s go back to our original example, this time armed with cats and transformers:

source: http://iwastesomuchtime.com/3948

import cats.data.OptionT, cats.std.future._
def findAddressByUserId(id: Long): Future[Option[Address]] =
  (for {
    user    <- OptionT(findUserById(id))
    address <- OptionT(findAddressByUser(user))
  } yield address).value

It works!

Can we make this even nicer? Probably: if we find ourselves wrapping often, we might consider to change those methods to return an OptionT[F, A] directly. Let’s see

def findUserById(id: Long): OptionT[Future, User] =
  OptionT { ??? }
def findAddressByUser(user: User): OptionT[Future, Address] =
  OptionT { ??? }
def findAddressByUserId(id: Long): OptionT[Future, Address] =
  for {
    user    <- findUserById(id)
    address <- findAddressByUser(user)
  } yield address

And that looks a lot like our original example. Whenever we need an actual Future[Option[Address]] we can simply call .value on the result.

Before concluding, some word of caution:

• Monad Transformers work really well in some common cases (like this one), but don’t push it too far: I don’t advice nesting more than two monads, as it gets really really tricky. For a tragic example, take a look at this README: https://github.com/djspiewak/emm.
• Monad Transformers are not for free, in terms of allocations. There’s a lot of wrapping/unwrapping involved, so if performance is a concern think twice and run some benchmarks.
• Since they’re not standard in the language (there are multiple library implementations available: cats, scalaz and possibly others) don’t expose them as a public API. Call .value on your transformers and expose a regular A[B[X]] which doesn’t impose any opinionated choice on your users and also allows you to swap implementations without introducing a breaking change.

Finally, Monad Transformers are just one of the possible ways of dealing with stacked Monads. They are a straightforward way in case you have a simple problem and don’t want to change your code base a lot, but if you’re ready for a bigger leap, you may want to take a look at Eff.

So, to recap, Monad Transformers help us in dealing with nested monads, by providing a flatten representation of two nested monads that is a monad itself.

I hope I’ve proven they’re not so scary as they sound and that you could have invented them yourself (and you probably already have, to some degree).

They have some very practical use cases, but be sure not to abuse them.

If you want to know more about the subject, here’s a talk I’ve given at Scala Days 2017:

Happy (functional) programming!

—

If you want to work in a place where we care about the quality of our development workflow, take a look at https://buildo.io/careers