2 notes &
A question about the Option monad transformer
A question
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 shortcircuiting 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 implementationspecific terminology for that particular method. So, this is my (pointed) answer to the specific subquestion of how to deal with this problem ‘using a monad transformer’. I’ll try to make it prerequisitefree, using just Wikipediaaccessible 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
nonderelict 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
gflatMap
h = fflatMap
( λ(x:A). g xflatMap
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
gflatMap
h = fflatMap
( λ(x:A). g xflatMap
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 : Future
s put some
exceptionraising 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 (^{1}).
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
(MflatMap
k) = (lift
M)flatMap
(lift
∘ k)
 ∀ M: ★ → ★,
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
gflatMap
h = fflatMap
( λ(x:A). g xflatMap
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 lowerkind 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]. ↩