(On September 23rd, 2013, Aleksander Sumowski and I gave a talk on monads at Developer Meetup, ThoughtWorks, Pune. This post is a transcript of that talk.)

Burrito. Not a monad.

I have come across many people who are somewhat familiar with functional programming but have had a hard time understanding the idea of “monads”. I believe monads is a simple concept and the intent of this talk is to provide an intuition for this concept. And we promise not to use burritos in our explanation!

Don’t worry if you haven’t heard of monads before. You might still learn something from this talk.

I will try to motivate the case for monads with some day to day code examples. The language used for examples is Scala.

Example 1: Presence or absence of a value

You are given a string. You have to look up this string in a map named foo. The length of the value obtained is to be used as a key in another map, named bar, to get the final value.

This is how you might do it:

// snippet 1.1
import java.{util => ju}
import scala.collection.JavaConverters._
val fooJ: ju.Map[String, String] = Map("a" -> "xoxox", "b" -> "xoxo").asJava

val barJ: ju.Map[Int, String] = Map(4 -> "P", 5 -> "Q").asJava

def calc(s: String): String = {
  val x = fooJ.get(s)
  val y = barJ.get(x.length)
  y
}

But wait! This code is incorrect. What if the key is missing in the first map itself? In that case, the map will return null, leading to a NullPointerException on next operation.

Clearly we need something that guards us against null. So we add an if-check.

// snippet 1.2
def calc(s: String): String = {
  val x = fooJ.get(s)
  val y = if (x != null) {
    barJ.get(x.length)
  } else {
    null
  }
  y
}

What was wrong with the snippet 1.1 was that the two operations were “sequenced” wrongly i.e. There were some “additional effects” necessary in between, which were missing.

Wouldn’t it be cool if we could write code whose “shape” is like that of snippet 1.1 but which behaves like code in snippet 1.2?

Example 2: Exceptions

You have to look up a couple of keys in a JSON object and then concatenate the obtained values with a space in between. Again, either or both keys might be absent, thus leading to an exception. In such an event, the exception should bubble up to the caller.

This is how you might do it:

// snippet 2.1
import play.api.libs.json._

def calc(json: JsObject): String = {
  val name = (json \ "name").as[String]
  val address = (json \ "address").as[String]
  name + " " + address
}

This code works as expected. The necessary “sequencing” or “effects” here are provided by a first-class language feature called exceptions. Imagine a language without exceptions.

What might you do in such a language? Perhaps send a tuple of error code and result. Or some equivalent structure.

Is it possible to write code whose “shape” and behavior is like that of snippet 2.1, but which doesn’t use first-class exceptions?

Example 3: Futures and promises

A future is an abstraction of a value which will be available at some point in time. This is a concurrency abstraction invented in late 70s but popularized by Java and Javascript. Scala’s variation is a tad better.

Consider a simple, non realistic task. We need to make two web service calls. There’s something that mandates that the second call must be made after the first one is over (I told you it’s a non-realistic example). Then after you obtain both results, you sum the lengths of the response bodies.

In a good old, serial, blocking, non-futurey API, this might look like below:

// snippet 3.1
def calc(s: String): Int = {
  val googleResponse = makeWebServiceCall("https://www.google.com/#q=" + s)
  val bingRespone = makeWebServiceCall("http://www.bing.com/search?q=" + s)
  googleResponse.body.length + bingResponse.body.length
}

Now let’s rewrite this with an API that uses futures. How are we going to sequence operations in such an API? The popular solution seems to be callbacks. With such an approach the code might look like below:

// snippet 3.2
import concurrent.{Promise, Future}
import play.api.libs.ws.WS

def calc(s: String): Future[Int] = {
  val promise = Promise[Int]()
  val googleResponse = WS.url("https://www.google.com/#q=" + s).get()
  googleResponse onSuccess { case res1 =>
    val bingResponse = WS.url("http://www.bing.com/search?q=" + s).get()
    bingResponse onSuccess { case res2 =>
      promise.success(res1.body.length + res2.body.length)
    }
  }
  promise.future
}

The onSuccess here provides necessary “effects” in between the operations.

This code is fairly straightforward, but has the following problems:

  1. It exposes “promise”, an implementation detail of futures.
  2. The onSuccess+promise pattern gets repetitive fast, and soon becomes an eyesore.

Wouldn’t it rock if we could write code whose “shape” is like that of our serial code but which has future-y semantics?

Enter “Type Driven Development”!

Let me introduce you to a style of programming popular in statically typed functional languages - Type Driven Development! (Henceforth referred to as TyDD.)

In TyDD, you encode as much semantic information as possible in your types (and values). (Of course there is a lot more to TyDD but it isn’t the subject of this talk.)

Let us revisit our examples, and try applying TyDD to them.

Revisiting example 1:

Scala has a data type named Option, which is a sum type, that encodes the presence/absence semantics. (Languages with different type systems might use different encodings.) It’s roughly defined as:

// snippet 1.3
sealed abstract class Option[+A]
case class Some[+A](value: A) extends Option[A]
case object None extends Option[Nothing]

As you’d expect, calling get on Scala’s map returns an Option value. With use of Scala maps, our code might look like:

// snippet 1.4
val fooS: Map[String, String] = Map("a" -> "xoxox", "b" -> "xoxo")

val barS: Map[Int, String] = Map(4 -> "P", 5 -> "Q")

def calc(s: String): Option[String] = {
  fooS.get(s) match {
    case Some(x) => barS.get(x.length)
    case None => None
  }
}

One advantage of the TyDD approach should be immediately clear by now: Compiler won’t allow you to treat Option[A] as A, and hence you cannot inadvertently write incorrect code like in snippet 1.1. You are forced to deal with optionality of value.

But all that sequencing with pattern matching looks yucky, and will get yuckier with every operation. Wouldn’t it be nice if the data type in question could take care of this sequencing? You know, “Tell, Don’t Ask” and all that?

As it happens, Option does have a method that takes care of this sequencing! The method is called flatMap, and on using it, the code looks like shown below:

// snippet 1.5
def calc(s: String): Option[String] = {
  fooS.get(s) flatMap { x =>
    barS.get(x.length) flatMap { y =>
      Some(y)
    }
  }
}

In the innermost block, you need to put the value in Option. Some is the data constructor we use for the purpose.

If you compare this code to snippet 1.1, you’ll notice that their shape is similar. (Okay, the code is somewhat inverted along vertical axis, but as you’ll soon see, there is a fix for that.)

Revisiting example 2:

Scala has a data type named Try which encodes success/failure semantics. It’s roughly defined as:

// snippet 2.2
sealed abstract class Try[+A]
case class Success[+A](value: A) extends Try[A]
case class Failure(throwable: Throwable) extends Try[Nothing]

Let’s imagine JsObject has a method named asTry[A] that returns Try[A]. With its use, code will look like:

// snippet 2.3
import play.api.libs.json._
import util.{Try, Success, Failure}

def calc(json: JsObject): Try[String] = {
  (json \ "name").asTry[String] match {
    case Success(name) =>
      (json \ "address").asTry[String] match {
        case Success(address) => Success(name + " " + address)
        case Failure(ex) => Failure(ex)
      }
    case Failure(ex) => Failure(ex)
  }
}

Boy, look at all that boilerplate!

As you might probably expect at this point, Try has a method named flatMap that helps you do away with this boilerplate. This is how the code will look like with flatMap:

// snippet 2.4
import play.api.libs.json._
import util.{Try, Success, Failure}

def calc(json: JsObject): Try[String] = {
  (json \ "name").asTry[String] flatMap { name =>
    (json \ "address").asTry[String] flatMap { address =>
      Success(name + " " + address)
    }
  }
}

In the innermost block, you need to put the value in Try, and we use Success data constructor for that.

This code is very similar in shape to code in snippet 2.1.

Revisiting example 3:

Our results are already wrapped in Future, so we are already using a distinct type to encode the semantics.

Now Future also happens to have a flatMap method. Let’s rewrite the code in snippet 3.2 with it.

// snippet 3.3
import concurrent.{Promise, Future}
import play.api.libs.ws.WS

def calc(s: String): Future[Int] = {
  WS.url("https://www.google.com/#q=" + s).get() flatMap { googleResponse =>
    WS.url("http://www.bing.com/search?q=" + s).get() flatMap { bingResponse =>
      Future.successful(googleResponse.body.length + bingResponse.body.length)
    }
  }
}

In the innermost block, we create a future with an already completed promise with our value.

Again, similar in shape to code in snippet 3.1.

Monad comprehensions:

As we have seen flatMap allows our code to have a simple shape, with details of sequencing of operations abstracted away. Now monads are so common in functional programming that functional languages often provide a syntactic sugar on top of them, which makes the “inversion along vertical axis” go away. This sugar is called “monad comprehensions”. Scala calls them “for comprehensions”. (Similarity with for-loops is superficial and should be ignored.) Here’s how our code snippets might look once we start using this notation:

// snippet 1.6
def calc(s: String): Option[String] = {
  for {
    x <- fooS.get(s)
    y <- barS.get(x.length)
  } yield y
}

// snippet 2.5
import play.api.libs.json._
import util.{Try, Success, Failure}

def calc(json: JsObject): Try[String] = {
  for {
    name <- (json \ "name").asTry[String] 
    address <- (json \ "address").asTry[String]
  } yield name + " " + address
}

// snippet 3.4
import concurrent.{Promise, Future}
import play.api.libs.ws.WS

def calc(s: String): Future[Int] = {
  for {
    googleResponse <- WS.url("https://www.google.com/#q=" + s).get()
    bingResponse <- WS.url("http://www.bing.com/search?q=" + s).get()
  } yield googleResponse.body.length + bingResponse.body.length
}

These are even closer in appearance to snippets 1.1, 2.1, and 3.1 respectively.

Note that this is just a sugar and compiles down roughly to the code we wrote before with flatMap.

So what is a monad?

A monad is essentially a two method interface, which can be defined as below:

// snippet 4.1
trait Monad[M[_]] {
  def flatMap[A, B](x: M[A], f: A => M[B]): M[B]
  def point[A](x: A): M[A]
  def map[A, B](x: M[A], f: A => B): M[B] = flatMap(x, a => point(f(a)))
}

I am using the word “interface” here in its generic sense, not in the OO sense. A more specific term for this abstraction mechanism would be “type-class”, and you can learn more about it here.

About the methods:

  • flatMap: We already talked about it.
  • point: It’s basically a method that allows you to put a value in monad’s context in the innermost block.
  • map: It’s a method by default defined in terms of flatMap and point, and you can override it in case a more performant implementation specific to the data type is possible.

As an example here’s a monad implementation for Option:

// snippet 4.2
implicit object OptionMonad extends Monad[Option] {
  def flatMap[A, B](x: Option[A], f: A => Option[B]): Option[B] = x match {
    case Some(a) => f(a) 
    case None => None
  }
  
  def point[A](x: A): Option[A] = Some(x)
  
  override def map[A, B](x: Option[A], f: A => B): Option[B] = x match {
    case Some(a) = Some(f(a))
    case None => None
  }
}

The implementation of Monad type-class also needs to obey some laws which we won’t go into here.

Intuition for monads:

You use the monad abstraction when:

  1. You need a “customized sequencing” for operations i.e. You need “additional effects” in between computations, and you want them abstracted away.
  2. You need to abstract over the sequencing details. i.e. Write code that is parametrized over M (some monad), and plug specific monad instance as necessary. This technique is used in Precog code to a good effect (pun unintended! ;).

One gentleman once cleverly described monads as something that lets you “overload semicolon”. (Since Scala doesn’t use semicolons at the end of statements/expressions, this perhaps isn’t as helpful/funny, but you get the idea (I hope).)

Other monads:

We have covered only three monads here - Option, Try, and Future - there are many more out there. Here’re some more interesting and common ones:

  1. Seq - Non-determinism.
  2. Either - Binary type disjunction. Often used for error handling.
  3. Reader - An “implicit” context passed around from which values can be read.
  4. Writer - Logging.
  5. State - What the name says.
  6. ST - Localized mutation.
  7. Undo - Ability to undo (and redo) operations.

Kleisli composition:

Given two functions f: A => B and g: B => C, it’s fairly trivial to compose them together. Here’s how you can write a function to compose them:

// snippet 5.1
def compose[A, B, C](f: A => B, g: B => C): A => C =
  a => g(f(a))

Now what happens when I have two “effectful” functions instead, say f: A => M[B] and g: B => M[C]? Composing these isn’t trivial since the output type of f and input type of g don’t match. We need a new composition function with signature like:

// snippet 5.2
def mcompose[A, B, C, M[_]](f: A => M[B], g: B => M[C]): A => M[C] = 
  ???

It’s not possible to write this generically. How the operations would be composed will depend on the structure of M. Hmm, why don’t we then have M tell us how to wire this operations up? We can. Monads to the rescue!

// snippet 5.3
def mcompose[A, B, C, M[_]](f: A => M[B], g: B => M[C])(implicit e: Monad[M]): A => M[C] = 
  a => {
    val mb = f(a)
    e.flatMap(mb, { b =>
      val mc = g(b)
      e.flatMap(mc, { c =>
        m.point(c)
      })
    })
  }

This kind of composition is called “Kleisli composition” and is often denoted with symbol >=>.

Monads are not alone!

I hope this talk helped you gain some intuition for what a monad is and when to use this abstraction.

As it happens, monads are not alone. There is a whole slew of such type-classes that let you abstract over computational patterns. Some key examples might be: Functor, Applicative, MonadPlus, Arrow, Alternative etc. If you find monads interesting/useful, I strongly recommend exploring the rest of the brethren as well. The best medium to do that is probably Haskell, and here is a good book to learn this beautiful language.

Some more notes:

  • Note that the names flatMap and point are not standard and different languages refer to them with different names. Various other names of flatMap: >>=, bind, m-bind, SelectMany. Various other names of point: pure, return.)
  • Scala’s Try violates certain monad laws and is therefore not quite a monad. However those details are irrelevant considering the basic nature of this talk. I could have used Either, but its implementation would require me to touch upon many tangential ideas and that would be a distraction.
  • A question is often asked, given that monads are so centered around types, are they possible/useful in dynamic languages? Yes, they are possible in dynamic languages. But much of their utility is lost. Also they require a somewhat different encoding. (I intend to blog about this point separately.)
  • Scala standard library does not have a Monad type-class. How do its for-comprehensions work then? The answer is Scala compiler blindly translates them to flatMap and map method calls on that data type (Yes, map, not point). This approach has its pros and cons. Nevertheless, a Monad type-class can be useful in many cases, and there’re libraries that will provide it for you.
  • If you want to really really understand monads in all their glory, here is a brilliant tutorial. Mind you it’s rather long, but from my experiences I can tell, it’s totally worth it.
  • Monad comprehensions sugar is pretty neat, but it still leaves much to be desired. People have taken the idea further in many different directions and come up with better syntaxes, such as this one.