Monad

Monad extends the Applicative type class with a new function flatten. Flatten takes a value in a nested context (eg. F[F[A]] where F is the context) and “joins” the contexts together so that we have a single context (ie. F[A]).

The name flatten should remind you of the functions of the same name on many classes in the standard library.

Option(Option(1)).flatten
// res0: Option[Int] = Some(1)

Option(None).flatten
// res1: Option[Nothing] = None

List(List(1),List(2,3)).flatten
// res2: List[Int] = List(1, 2, 3)

Monad instances

If Applicative is already present and flatten is well-behaved, extending the Applicative to a Monad is trivial. To provide evidence that a type belongs in the Monad type class, cats’ implementation requires us to provide an implementation of pure (which can be reused from Applicative) and flatMap.

We can use flatten to define flatMap: flatMap is just map followed by flatten. Conversely, flatten is just flatMap using the identity function x => x (i.e. flatMap(_)(x => x)).

import cats._

implicit def optionMonad(implicit app: Applicative[Option]) =
  new Monad[Option] {
    // Define flatMap using Option's flatten method
    override def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] =
      app.map(fa)(f).flatten
    // Reuse this definition from Applicative.
    override def pure[A](a: A): Option[A] = app.pure(a)

    @annotation.tailrec
    def tailRecM[A, B](init: A)(fn: A => Option[Either[A, B]]): Option[B] =
      fn(init) match {
        case None => None
        case Some(Right(b)) => Some(b)
        case Some(Left(a)) => tailRecM(a)(fn)
      }
  }

flatMap

flatMap is often considered to be the core function of Monad, and cats follows this tradition by providing implementations of flatten and map derived from flatMap and pure.

In addition to requiring flatMap and pure, Cats has chosen to require tailRecM which encodes stack safe monadic recursion, as described in Stack Safety for Free by Phil Freeman. Because monadic recursion is so common in functional programming but is not stack safe on the JVM, Cats has chosen to require this method of all monad implementations as opposed to just a subset. All functions requiring monadic recursion in Cats is done via tailRecM.

An example Monad implementation for Option is shown below. Note the tail recursive and therefore stack safe implementation of tailRecM.

import scala.annotation.tailrec

implicit val optionMonad = new Monad[Option] {
  def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa.flatMap(f)
  def pure[A](a: A): Option[A] = Some(a)

  @tailrec
  def tailRecM[A, B](a: A)(f: A => Option[Either[A, B]]): Option[B] = f(a) match {
    case None              => None
    case Some(Left(nextA)) => tailRecM(nextA)(f) // continue the recursion
    case Some(Right(b))    => Some(b)            // recursion done
  }
}

Part of the reason for this is that name flatMap has special significance in scala, as for-comprehensions rely on this method to chain together operations in a monadic context.

import scala.reflect.runtime.universe
// import scala.reflect.runtime.universe

universe.reify(
  for {
    x <- Some(1)
    y <- Some(2)
  } yield x + y
).tree
// res5: reflect.runtime.universe.Tree = Some.apply(1).flatMap(((x) => Some.apply(2).map(((y) => x.$plus(y)))))

ifM

Monad provides the ability to choose later operations in a sequence based on the results of earlier ones. This is embodied in ifM, which lifts an if statement into the monadic context.

import cats.implicits._
// import cats.implicits._

Monad[List].ifM(List(true, false, true))(List(1, 2), List(3, 4))
// res6: List[Int] = List(1, 2, 3, 4, 1, 2)

Composition

Unlike Functors and Applicatives, not all Monads compose. This means that even if M[_] and N[_] are both Monads, M[N[_]] is not guaranteed to be a Monad.

However, many common cases do. One way of expressing this is to provide instructions on how to compose any outer monad (F in the following example) with a specific inner monad (Option in the following example).

Note: the example below assumes usage of the kind-projector compiler plugin and will not compile if it is not being used in a project.

case class OptionT[F[_], A](value: F[Option[A]])

implicit def optionTMonad[F[_]](implicit F : Monad[F]) = {
  new Monad[OptionT[F, ?]] {
    def pure[A](a: A): OptionT[F, A] = OptionT(F.pure(Some(a)))
    def flatMap[A, B](fa: OptionT[F, A])(f: A => OptionT[F, B]): OptionT[F, B] =
      OptionT {
        F.flatMap(fa.value) {
          case None => F.pure(None)
          case Some(a) => f(a).value
        }
      }

    def tailRecM[A, B](a: A)(f: A => OptionT[F, Either[A, B]]): OptionT[F, B] =
      OptionT {
        F.tailRecM(a)(a0 => F.map(f(a0).value) {
          case None => Either.right[A, Option[B]](None)
          case Some(b0) => b0.map(Some(_))
        })
      }
  }
}

This sort of construction is called a monad transformer.

Cats has an OptionT monad transformer, which adds a lot of useful functions to the simple implementation above.