In Chapter 6, Exploring Built-In Effects, we talked about standard effects such as Option, Try, Either, and Future. In Chapter 9, Familiarizing Yourself with Basic Monads, we moved on and implemented monads for all of them. In our examples, we demonstrated how Scala provides nice syntax for the code formulated in monadic terms by having for-comprehension, which is a syntactic sugar for the combination of map, flatMap, and possibly filter methods. In all our examples, we used for-comprehension to define a sequence of steps which constitute some process where the result of the previous computation is consumed by the next step. 

For an instance, this is the way we defined the process of fishing in terms of Option in Chapter 6, Exploring Built-In Effects:

val buyBait: String => Option[Bait]
val makeBait: String => Option[Bait]
val castLine: Bait => Option[Line]
val hookFish: Line => Option[Fish]

def goFishing(bestBaitForFish: Option[String]): Option[Fish] =
  for {
    baitName <- bestBaitForFish
    bait <- buyBait(baitName).orElse(makeBait(baitName))
    line <- castLine(bait)
    fish <- hookFish(line)
  } yield fish

With our new obtained knowledge about monads, we could make this implementation effect-agnostic:

def goFishing[M[_]: Monad](bestBaitForFish: M[String]): M[Fish] = {

  val buyBait: String => M[Bait] = ???
  val castLine: Bait => M[Line] = ???
  val hookFish: Line => M[Fish] = ???

  import Monad.lowPriorityImplicits._

  for {
    baitName <- bestBaitForFish
    bait <- buyBait(baitName)
    line <- castLine(bait)
    fish <- hookFish(line)
  } yield fish
}
Ch10.goFishing(Option("Crankbait"))

One thing we can't do with this approach is to use the orElse method specific to Option to define the unhappy path for bait-acquiring.

Another simplification we're making here is pretending that all our actions can be described by the same effect. In reality, this will almost definitely not be the case. To be more specific, obtaining the bait and waiting to hook the fish will probably take much longer than casting the line. Thus, we probably would like to represent these actions with Future instead of Option:

val buyBait: String => Future[Bait]
val hookFish: Line => Future[Fish]

Or, in generic terms, we would have the type of effect N instead of M:

def goFishing[M[_]: Monad, N[_]: Monad](bestBaitForFish: M[String]): N[Fish] = {

  val buyBait: String => N[Bait] = ???
  val castLine: Bait => M[Line] = ???
  val hookFish: Line => N[Fish] = ???
  
  // ... the rest goes as before
}
import scala.concurrent.ExecutionContext.Implicits.global
Ch10.goFishing[Option, Future](Option("Crankbait"))

But, unfortunately, this won't compile anymore. Let's consider a simpler example to understand why:

import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

scala> for {
     | o <- Option("str")
     | c <- Future.successful(o)
     | } yield c
           c <- Future.successful(o)
             ^
On line 3: error: type mismatch;
        found : scala.concurrent.Future[String]
        required: Option[?]

The compiler ceases to accept Future instead of the Option. Let's desugar our for-comprehension to see what is going on:

Option("str").flatMap { o: String =>
  val f: Future[String] = Future(o).map { c: String => c }
  f
}

Now the problem lies on the surface—the Option.flatMap expects some function returning an Option as an effect (this is using the definition of Option.flatMap[B](f: A => Option[B]): Option[B] in particular, and Monad.flatMap in general). But the value we return is wrapped in Future, as a result of applying the map function of the Future.

Generalising this reasoning, we can conclude that it is only possible to use effects of the same type in the single for-comprehension. 

Because of this, it looks like we have two possibilities to combine desired effects:

• Put them in separate for-comprehensions
• Lift different effects to some kind of common denominator type

We can compare both approaches using our fishing example as the playground. The variation of separate for-comprehensions would look like the following:

for {
  baitName <- bestBaitForFish
} yield for {
  bait <- buyBait(baitName)
} yield for {
  line <- castLine(bait)
} yield for {
  fish <- hookFish(line)
} yield fish

This looks slightly worse than the original version but is still quite nice, apart from the fact that the type of the result has changed from N[Fish] to the M[N[M[N[Fish]]]]. In the specific cases of Future and Option, it would be Option[Future[Option[Future[Fish]]]] and there is no easy way to extract the result other than going through all of the layers one by one. This is not a very nice thing to do and we'll leave it as an exercise for the scrupulous reader.

Another option would be to abandon the generosity of our implementation and make it nonpolymorphic as follows:

def goFishing(bestBaitForFish: Option[String]): Future[Fish] =
  bestBaitForFish match {
    case None => Future.failed(new NoSuchElementException)
    case Some(name) => buyBait(name).flatMap { bait: Bait =>
      castLine(bait) match {
        case None => Future.failed(new IllegalStateException)
        case Some(line) => hookFish(line)
      }
    }
  }

Besides losing general applicability, this implementation has the obvious disadvantage of being much less readable.

Let's hope that the second approach, the common denominator for the effect type, will bear more fruit than the first one.

First, we need to decide how we want to compose the two effects we currently have. There are two choices: Future[Option[?]] and Option[Future[?]]. Semantically, having an optional result at some point later feels better than optionally having an operation which will complete in the future, hence we will continue with the first alternative.

With this fixed new type, the functions we have became invalid—they all now have the wrong type of result. Conversion to the proper type just involves juggling the types and we can do this on the spot:

val buyBaitFO: String => Future[Option[Bait]] = (name: String) => buyBait(name).map(Option.apply)
val castLineFO: Bait => Future[Option[Line]] = castLine.andThen(Future.successful)
val hookFishFO: Line => Future[Option[Fish]] = (line: Line) => hookFish(line).map(Option.apply)

All we need to do is to wrap Option into the Future or Future into the Option, depending on the return type of the original function.

To keep everything consistent, we'll also change the type of the argument and return type of the goFishing function in the same way:

def goFishing(bestBaitForFish: Future[Option[String]]): Future[Option[Fish]] = ???

As we strive to formulate the logic itself as a for-comprehension, it is reasonable to try to draw it up it in terms of the flatMap:

bestBaitForFish.flatMap { /* takes Option[?] and returns Future[Option[?]] */ }

As an argument to flatMap, we have to provide some function which takes an Option[String] and returns Future[Option[Fish]]. But our functions expect "real" input, not optional. We can't flatMap over the Option as discussed before and we can't just use Option.map because it will wrap our result type in an additional layer of optionality. What we can use is a pattern match to extract the value:

case None => Future.successful(Option.empty[Fish])
case Some(name) => buyBaitFO(name) /* now what ? */

In the case of None, we just shortcut the process and return the result. In that case, we indeed have a name; we can call a corresponding function, passing this name as an argument. The question is, how do we proceed further? If we look carefully at the return type of buyBaitFO(name), we will see that this is the same as we had for the initial argument—Future[Option[?]]. Hence, we can try to reuse the approach with flatmapping and pattern matching again, which after all its iterations gives us the following implementation:

def goFishingA(bestBaitForFish: Future[Option[String]]): Future[Option[Fish]] =
  bestBaitForFish.flatMap {
    case None => Future.successful(Option.empty[Fish])
    case Some(name) => buyBaitFO(name).flatMap {
      case None => Future.successful(Option.empty[Fish])
      case Some(bait) => castLineFO(bait).flatMap {
        case None => Future.successful(Option.empty[Fish])
        case Some(line) => hookFishFO(line)
      }
    }
  }

There is a lot of duplication in this snippet, but it already looks somehow structured. It is possible to improve its readability by extracting the repetitive code fragments. First, we can make the case of no result polymorphic as shown below:

def noResult[T]: Future[Option[T]] = Future.successful(Option.empty[T])

Second, we might capture our reasoning about flatMap and pattern match as a standalone polymorphic function:

def continue[A, B](arg: Future[Option[A]])(f: A => Future[Option[B]]): Future[Option[B]] =
  arg.flatMap {
    case None => noResult[B]
    case Some(a) => f(a)
  }

With these changes, our last attempt starts to look more concise:

def goFishing(bestBaitForFish: Future[Option[String]]): Future[Option[Fish]] =
  continue(bestBaitForFish) { name =>
    continue(buyBaitFO(name)) { bait =>
      continue(castLineFO(bait)) { line =>
        hookFishFO(line)
      }
    }
  }

This is arguably something that is already quite good, and we could stop at this moment, but there is one aspect we might improve further on. The continue function calls are nested. This makes it nontrivial to formulate the business logic flow. It might be beneficial if we could have a kind of fluent interface instead and we would be able to chain the continue calls.

It is easily achieved by capturing the first argument of continue as a value of some class. This will change our implementation to the following form:

final case class FutureOption[A](value: Future[Option[A]]) {
  def continue[B](f: A => FutureOption[B]): FutureOption[B] = new FutureOption(value.flatMap {
    case None => noResult[B]
    case Some(a) => f(a).value
  })
}

There are two ways to improve this further. First, the signature of continue reveals that it is a Kleisli arrow, which we introduced in the previous chapter. Second, in this form, we will need to wrap the value in FutureOption manually each time we need to call the continue method. This will make the code unnecessarily verbose and we can enhance our implementation by making it an implicit class:

implicit class FutureOption[A](value: Future[Option[A]]) {
  def compose[B](f: A => FutureOption[B]): FutureOption[B] = new FutureOption(value.flatMap {
    case None => noResult[B]
    case Some(a) => f(a).value
  })
}

Let's take a look at what our main flow looks like with these changes incorporated:

def goFishing(bestBaitForFish: Future[Option[String]]): Future[Option[Fish]] = {
  val result = bestBaitForFish.compose { name =>
    buyBaitFO(name).compose { bait =>
      castLineFO(bait).compose { line =>
        hookFishFO(line)
      }
    }
  }
  result.value
}

Wonderful! Can you spot further possibility for improvement? If we scrutinise the type signature of the FutureOption, we'll see that everything we're doing with the wrapped value is calling a flatMap method which is defined on Future. But we already know the proper abstraction for that—this is a monad. Utilizing this knowledge will allow us to make our class polymorphic and possibly reuse it for other types of effects, if needed:

implicit class FOption[F[_]: Monad, A](val value: F[Option[A]]) {
  def compose[B](f: A => FOption[F, B]): FOption[F, B] = {
    val result = value.flatMap {
      case None => noResultF[F, B]
      case Some(a) => f(a).value
    }
    new FOption(result)
  }
  def isEmpty: F[Boolean] = Monad[F].map(value)(_.isEmpty)
}

To demonstrate that the polymorphic nature of the new implementation won't harm our flexibility to define helper functions as needed, we've also added a method to check that the composition of monads we have is empty.

Unfortunately, if we'll try to make this implementation polymorphic in the type of the second effect, we'll see that it is impossible—we need to decompose it as explained previously, and for this we need to know the specifics of the effect's implementation.

At this point, an astute reader will remember that all monads we developed in the previous chapter were implemented in terms of compose function, which had the same signature. Could we try to do the same trick again and implement a monad for the FutureOption type? Readers familiar with the previous chapter will know that this is almost a mechanical task of delegating to the implementation we just came up with:

implicit def fOptionMonad[F[_] : Monad] = new Monad[FOption[F, ?]] {
  override def unit[A](a: => A): FOption[F, A] = Monad[F].unit(Monad[Option].unit(a))
  override def flatMap[A, B](a: FOption[F, A])(f: A => FOption[F, B]): FOption[F, B] =
    a.compose(f)
}

Now, we also need to change the return type of the original functions to be a FOption[Future, ?] to match the type signature of our new monad. We don't need to touch the implementation—the compiler will wrap implicit FOption around the result automatically:

val buyBaitFO: String => FOption[Future, Bait] = // as before
val castLineFO: Bait => FOption[Future, Line] = // as before
val hookFishFO: Line => FOption[Future, Fish] = // as before

Now we can formulate our logic once again, this time in terms of for-comprehension:

def goFishing(bestBaitForFish: FOption[Future, String]): FOption[Future, Fish] = for {
  name <- bestBaitForFish
  bait <- buyBaitFO(name)
  line <- castLineFO(bait)
  fish <- hookFishFO(line)
} yield fish

Finally, this is nice and clean! The final touch would be to do something with the adhoc name of FOption. What the type does is transform an Option into something monadic of higher order, by wrapping an Option into a monadic effect of our choice. We could rename it into OptionTransformer or OptionT for short.

Congratulations! We just implemented a monad transformer.