I’ve recently heard the following suprisingly general question:

The premise is that we have three services which return Future[Option[Int]]:

trait FooService {
  def find(id:Int): Future[Option[Foo]]
}

trait BarService {
  def find(id:Int): Future[Option[Bar]]
}

trait QuuxService {
  def find(id:Int): Future[Option[Quux]]
}

And we need to query across all three services, i.e. in a non blocking/no option service we would have:

val foo = fooService.find(1)
val bar = barService.find(foo.barId)
val quux = quuxService.find(bar.quuxId)

Now, monads don’t compose, and because we have multiple Future[Option[T]] here, the quickest route to resolving an Option from a Future (without short-circuiting the failure case) is to use a partial function or fold, and then just break things down into very small methods so it doesn’t get too nesty.

I’ve heard that there’s a third option which is to use a monad transformer or a Reader monad.

Then he ran into implementation-specific terminology for that particular method. So, this is my (pointed) answer to the specific sub-question of how to deal with this problem ‘using a monad transformer’. I’ll try to make it prerequisite-free, using just Wikipedia-accessible mathematical definitions and Scala.

Basics

So, just to check our bases, the idea of defining a Monad transformer for Future and Option would require them to indeed be monads. They’re functors, and they have a constructor, and a flatMap. Do they verify the monadic laws ?

For Option (where, in scala, the apply Option(x) resolves to Some(x) on non-derelict inputs):

• left identity: ∀ (f: A, g: A → Option[B]) Option (f) flatMap g = g f
• right identity: ∀ (f: Option[A]), f flatMap ( λ(x:A). Option(x) ) = f
• associativity: ∀ (f: Option[A], g: A → Option[B], h: B → Option[C]) f flatMap g flatMap h = f flatMap ( λ(x:A). g x flatMap h)

It’s a good exercise to check, e.g. for Option, that these equalities hold whatever the output of the functions whose type matches the pattern (X → Option[Y]) is.

For Future, the monadic laws look like this:

• left identity: ∀ (f: A, g: A → Future[B]) future { f } flatMap g = g f
• right identity: ∀ (f: Future[A]), f flatMap ( λ(x:A). future { x } ) = f
• associativity: ∀ (f: Future[A], g: A → Future[B], h: B -> Future[C]) f flatMap g flatMap h = f flatMap ( λ(x:A). g x flatMap h)

By the way, the left identity law for Futures doesn’t work if g throws an exception before returning its Future:

scala> val g = { (x: Int) => if (x == 0) throw new IllegalArgumentException("Zero !") else Future { 3 / x } }
g: Int => scala.concurrent.Future[Int] = <function1>

scala> g(0)
java.lang.IllegalArgumentException: Zero !
  at $anonfun$1.apply(<console>:11)
  at $anonfun$1.apply(<console>:11)
  ... 32 elided

scala> Future { 0 } flatMap g
res11: scala.concurrent.Future[Int] = scala.concurrent.impl.Promise$DefaultPromise@68f3b76b

In sum, it tells us something we knew : Futures put some exception-raising behavior of their arguments in the future. We’ll have to be careful about which results depend on that left identity in the following.

Composition

On to the statement that ‘monads don’t compose’. This is true, but it means that there is no general function that takes two monads as input, and systematically returns a monad for the composition of the two underlying functors, for any two input monads. At best, what one can always hope to return is a functor.

That being said, it’s a starkly different statement from dealing with two particular monads. For two very specific, fixed monads, there may well be a way to compose them into a monad, and that is not a contradiction with the prior statement.

And we’re in the case of two very specific monads: Option and Future.

In fact, there’s even a construction called a monad transformer, slightly more demanding than a monad, that can be injected into a monad to yield another (transformed) monad (¹).

So, a monad transformer requires an interface with:

• A type constructor T which takes a type constructor and returns another. Technically, it’s said to be of kind (★ → ★) → ★ → ★. As can be expected, the intent is to make it take the “transformee” monad as argument.

• Monad operations (a constructor and a flatMap), for every output T(M) (the transformed monad), provided the input M (the transformee) is a monad. Notice how making sure the transformed monad is here a requirement.

• Another operation, lift : ∀A: ★, ∀M: ★ → ★. M[A] → T[M[A]] (this reads, ∀ A a type and M a type constructor) satisfying the following laws:

  • ∀ M: ★ → ★, lift ∘ M = T
  • lift (M flatMap k) = (lift M) flatMap (lift ∘ k)

This becomes more clear, as with every abstract structure, after building a couple of concrete cases. Intuitively, the transformed monad has the operation of the transformer injected in its inputs. So, given that we’re interested in services that return a Future[Option[A]] (as opposed to an Option[Future[A]]), we’re interested in defining the Option Monad Transformer (as opposed to the Future Monad Transformer).

Thankfully, not only does this Option Monad Transformer exists, but it’s easy to define.

trait ApplicativeFunctor[A, F[A]] {
  def apply[X](a:X): F[X]
  def map[B](f: A => B): F[B]
}

trait Monad[A, M[A]] extends ApplicativeFunctor[A, M] {
  def flatMMap[B](f: A => M[B]): M[B]
}


class OptionT[A, M[A]] (m:ApplicativeFunctor[Option[A], M]) extends ApplicativeFunctor[A, ({type T[X]=M[Option[X]]})#T] {
  override def apply[X](a:X): M[Option[X]] = m(Option(a))
  override def map[B](f: A => B): M[Option[B]] =
    m map {(x: Option[A]) => x map f}
}

class OptionTM[A, M[A]](m:Monad[Option[A], M]) extends OptionT[A, M](m) with Monad[A, ({type T[X]=M[Option[X]]})#T] {
  override def flatMMap [B] (f:A => M[Option[B]]) : M[Option[B]] =
    m flatMMap {
      case Some(z) => f(z)
      case None => m(None)
    }
}

The name flatMMap instead of flatMap is here to avoid conflicts. The ({type T[X]=M[Option[X]]})#T is unsightly, and pollutes the scope of the program, but how to iron that particular wrinkle is beyond the scope of this post.

Let’s give a moment of pause to the three laws:

• left identity: ∀(f:A, g: A => Future[Option[B]]) Future { Option(f) } flatMap g = g ( f ) Unfolding this one reveals that for this equality to hold, we’d need the left equality for the Future monad to hold. Not that it’s the first time we’ve seen
• right identity: ∀ (f: Future[Option[A]]), f flatMap ( λ(x:A). Future{ Option(x) } ) = f
• associativity: ∀ (f: Option[A], g: A → Option[B], h: B → Option[C]) f flatMap g flatMap h = f flatMap ( λ(x:A). g x flatMap h)

All that’s left is to test it. The inevitable part is reminding Scala there’s a Monad instance for Future, even in the context where Option[A] is the parameter, but it’s more about mapping our terminology with existing Scala methods. Then there is the related implicit declaration to palliate some insufficiencies in implicit search not jumping order in type parameters when a suitable application of a lower-kind constructor is found.

abstract class MyTest{

  import scala.concurrent.Future
  import scala.concurrent.ExecutionContext.Implicits._

  // The unchanged future monad, but applied to Option[A]
  class FutureOM[A](fut: Future[Option[A]]) extends Monad[Option[A], Future] {
    def apply[X](a:X): Future[X] = Future { a }
    def map[B](f: Option[A] => B): Future[B] = fut map f
    def flatMMap[B](f: Option[A] => Future[B]): Future[B] = fut flatMap f
  }

  implicit def optionMF[A](f:Future[Option[A]]) = new OptionTM(new FutureOM(f))


  trait FooService {
    def find(id: Int): Future[Option[Int]]
  }

  trait BarService {
    def find(id: Int): Future[Option[Int]]
  }

  trait QuuxService {
    def find(id:Int): Future[Option[Int]]
  }

  val fooService: FooService
  val barService: BarService
  val quuxService: QuuxService

  def finalRes(): Future[Option[Int]] =
    fooService.find(1) flatMMap (barService.find _) flatMMap (quuxService.find _)
}

The whole source is on github

In the following, I’ll use liberally of the Scala `apply` syntactic sugar of calling the constructor in the same way as the resulting type. Since I’m typing every variable, it should be easy to see what I’m talking about. In case of doubt, I apply the constructor with parentheses, and the type constructor with brackets. the For instance, Option is a type constructor: λ(A:★).Option[A]: ★ → ★, which returns a term of an Option type: ∀A: ★, (λ(x:A). Option(x)): A → Option[A]. So is List λ(A:★).List[A]: ★ → ★, which returns a term of a List type: ∀A: ★, (λ(x:A). List(x)): A → List[A].