Cooking with Monads
Tags: functional, scala
Published: 2020-05-13 11:42:34

*This article was originally published on Nov 8, 2016 on the [BeCompany blog](https://www.becompany.ch/en/blog/2016/11/08/cooking-with-monads).*

#### As a programmer endeavouring to discover the world of functional programming, you will sooner or later be confronted with the concept of monads. Monads are an incredibly useful construct for dealing with a multitude of software design challenges.

Monads are a powerful tool in the repertoire of a functional programmer. Using monads, functional programs can be expressed in ways that are easier to read and maintain:
 
* Monads allow us to decompose complex functions into individual processing steps.
* Monads provide abstractions for various aspects like maintaining state, concurrency, logging and configuration.

The web offers an abundance of resources on this subject, but virtually all of these approach it from a rather abstract point of view, making it difficult to grasp the concept intuitively. Let's try to look at monads from a slightly different angle: Cooking, a task that most of you will be familiar with. Or, more specifically, teaching a machine how to cook. We will use the Scala programming language for the code examples, although they could be expressed using virtually any language that supports the functional programming paradigm.

# Time for Breakfast

To warm up, let's begin with an easy task: Frying an egg for breakfast.

The recipe for frying an egg can be expressed a bit more formally:

* `RawEgg` is the type denoting a raw egg.
* `fryEgg` is a function transforming a raw egg into a sunny-side-up egg: `fryEgg: RawEgg => SunnySideUp`.

Let's write a small program which makes the machine fry an egg for us.

~~~~ scala
val egg = new RawEgg()
val breakfast: SunnySideUp = fryEgg(egg)
~~~~

That was easy, wasn't it? Now let's explore some aspects of cooking.

# Empty Pans

Let's build a first version of our machine, containing a slot which fits a frying pan. For the sake of simplicity, we will assume that you can only put a single raw egg in the frying pan.

Now, what happens if we forget to put an egg into the frying pan, put the empty pan in the slot and press the start button? Our machine will heat up the pan for a couple of minutes (we use the time to brew some coffee) and then present us with – no breakfast egg whatsoever. We have to start from the beginning, and in the meantime our coffee got cold.

How can we tell our machine to check whether the pan is full or empty? If the seemingly innocent word `null` comes to your mind, please read up on [Tony Hoare](https://en.wikipedia.org/wiki/Tony_Hoare). Instead, we will introduce a new type, `Pan`. Since we'd like to use frying pans for all sorts of food items, we parameterize our frying pan type with the type of foodstuff to process: `Pan[A]`. Our `Pan` type has the two subtypes `FullPan[A]` and `EmptyPan`.

Let's summarize what we have defined so far:

~~~~ scala
case class RawEgg()
case class SunnySideUp()

sealed abstract class Pan[A]
case class FullPan[A](a: A) extends Pan[A]
object EmptyPan extends Pan[Nothing]

def makeEgg: Pan[RawEgg] => Pan[SunnySideUp]
~~~~

Our `makeEgg` method needs to determine whether the pan is full or empty and only turn up the heat if it is full. Let's assume that there is a function `fryEgg: RawEgg => SunnySideUp` which actually transforms the raw egg into a sunny-side-up egg.

~~~~ scala
def makeEgg(pan: Pan[RawEgg]): Pan[SunnySideUp] =
  pan match {
    case FullPan(egg) => FullPan(fryEgg(egg))
    case EmptyPan => EmptyPan
  }
~~~~

Now the program will immediately finish if an empty pan was put in the machine.

Looking at the code, it seems unnecessary to explicitly state that an empty pan should be left untouched. Shouldn't the `EmptyPan` know that it's not supposed to fry anything? Let's see if we can do better by moving the `fryEgg` method to our `Pan` class. Since our `Pan` class is generic and therefore doesn't actually know how to fry an egg (how much heat to apply, how long to keep the heat on etc.), we will have to pass the actual `fryEgg` function to the pan. Since our `Pan` type is generic in type `A`, will call the function `fryA`:

~~~~ scala
sealed abstract class Pan[A] {
  def fry[B](fryA: (A) => B): Pan[B]
}
~~~~

The `FullPan` class applies the function to its content and returns a full pan with the result:

~~~~ scala
case class FullPan[A](a: A) extends Pan[A] {
  def fry[B](fryA: (A) => B): Pan[B] = Some(fryA(a))
}
~~~~

The `EmptyPan` class does nothing and returns an empty pan.

~~~~ scala
object EmptyPan extends Pan[Nothing] {
  def fry[B](fryA: (A) => B): Pan[B] = EmptyPan
}
~~~~

Now the `makeEgg` function looks much simpler:

~~~~ scala
def makeEgg(pan: Pan[RawEgg]): Pan[SunnySideUp] =
  pan.fry(fryEgg)
~~~~

# Coffee please!

Now that we have such a sophisticated breakfast machine, of course we want it to brew our coffee for us as well. The ingredients for a cup of coffee are ground coffee and water. We learned from our previous experience that we can't rely on the user to input everything, so we have to design our ground coffee and water receptacles accordingly:

~~~~ scala
sealed abstract class GroundCoffeeBin
case class FullGroundCoffeeRecepticle extends GroundCoffeeBin
object EmptyGroundCoffeeRecepticle extends GroundCoffeeBin

sealed abstract class WaterTank
case class FullWaterTank extends WaterTank
object EmptyWaterTank extends WaterTank
~~~~

We're clearly [repeating ourselves](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself) here. How can we generalize the concept of a generic receptacle that may or may not contain something?

# Exploring Options

We need a generic container which may or may not contain an item. Let's call it `Option` (in some other programming languages, this type is called `Maybe`).

~~~~ scala
sealed abstract class Option[A]
case class Some[A](a: A) extends Option[A]
object None extends Option[Nothing]
~~~~

What could the program for brewing coffee look like? To make it easy for our machine, we'll just boil the water and mix it with the ground coffee.

1. If both water and ground coffee have been provided,
   1. Heat the water and put it in a cup,
   1. Add the ground coffee,
   1. Output the result which is a full cup of coffee.
1. If either of the ingredients are missing, output the result which is an empty tray with no cup on it.

How would we go about implementing this algorithm? Intuitively, we would check whether both the coffee bin and the water tank are full, and only then continue with the brewing:

~~~~ scala
def brew(waterTank: Option[Water], coffeeBin: Option[GroundCoffee]):
    Option[CupOfCoffee] = {
  if (waterTank.isFull && coffeeBin.isFull) {
    Some(CupOfCoffee(waterTank.get, coffeeBin.get))
  } else {
    None
  }
}
~~~~

By using pattern matching we can avoid having to use `Option.isFull` and especially `Option.get` (this one is dangerous since it causes a runtime error if called on an empty `Option`):

~~~~ scala
def brew(waterTank: Option[Water], coffeeBin: Option[GroundCoffee]):
    Option[CupOfCoffee] =
  (waterTank, coffeeBin) match {
    case (Some(water), Some(coffee)) =>
      Some(CupOfCoffee(water, coffee))
    case _ => None
  }
}
~~~~

We put water and coffee in our machine, press the start button, and are immediately presented with a nice cup of cold coffee. We have to add a `boil` function to heat up the water. Additionally, we'd like our machine to grind the coffee for us. Let's take a look at the resulting program:

~~~~ scala
def brew(waterTank: Option[Water], coffeeBin: Option[CoffeeBeans]):
    Option[CupOfCoffee] =
  (waterTank, coffeeBin) match {
    case (Some(water), Some(beans)) =>
      Some(CupOfCoffee(boil(water), grind(beans)))
    case _ => None
  }
}
~~~~

This is looking pretty good already. Let's combine the egg and coffee programs to get a complete breakfast:

~~~~ scala
type Breakfast = (Pan[SunnySideUp], Optional[CupOfCoffee])

def makeBreakfast(
    pan: Pan[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Breakfast =
  (pan.fry(fryEgg), brew(waterTank, coffeeBin))
~~~~

Our `Pan` type is actually very similar to the `Option` type. Maybe we can use the `Option` type to represent our empty or non-empty frying pan? Obviously we don't want to add a `fry` method to `Option`, but since the `Pan.fry` method doesn't do anything but invoke the function that has been passed to it, we might as well make it generic. Since all these concepts have been contrived by mathematicians, the resulting method on `Option` is called `map`:

~~~~ scala
sealed abstract class Option[A] {
  def map[B](f: A => B): Option[B]
}

case class Some[A](a: A) extends Option[A] {
  def map[B](f: A => B): Option[B] = Some(f(a))
}

object None extends Option[Nothing] {
  def map[B](f: A => B): Option[B] = None
}
~~~~

The `makeBreakfast` function using an `Option` for the frying pan looks like this:
 
~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Breakfast =
  (pan.map(fryEgg), brew(waterTank, coffeeBin))
~~~~

OK, now we can finally make some breakfast. Crack an egg in the pan, add some ground coffee, press the start button … Wait, we forgot to fill the water tank! Now we have a sunny-side-up egg, but no coffee. We need to find a way for our machine to verify that _all_ recepticles are full before starting to make breakfast. We can use pattern matching for this purpose. Additionally, we modify the return type to either be a complete `Breakfast`, or none. 

~~~~ scala
type Breakfast = (SunnySideUp, CupOfCoffee)

def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Option[Breakfast] =
  (pan, waterTank, coffeeBin) match {
    case (Some(rawEgg), Some(water), Some(beans)) =>
      Some((fryEgg(rawEgg), CupOfCoffee(boil(water), grind(beans))))
    case _ => None
  }
~~~~

# Burnt Eggs

As we all have experienced, the outcome of frying an egg is not necessarily a sunny-side-up egg, but might as well be an egg that is burnt to a crisp. How can we tell our cooking machine how to handle this case? One option would be to ignore it, add a smoke detector, shut down the whole machinery when smoke is detected, and throw everything away which has been cooked up so far. In computer science we call this an _exception_, i.e. an event which does not occur if everything is working as intended, is not covered directly by the execution instructions, and is dealt with somewhere outside the actual operation code.

The intention behind exceptions is to keep the instructions as simple as possible. But this comes at great cost: A program which uses exceptions is extremely hard to reason about. Throwing an exception disrupts the execution flow, and can cause effects in an entirely different location of the codebase. Fortunately, we can do better.

In the first iteration we're not interested in knowing whether our machine actually burned an egg; we just want it to discard the burnt egg and produce an empty pan. Our `fryEgg` function now produces an _optional_ egg, which means that we will use `Option[SunnySideUp]` as its return type:

~~~~ scala
def fryEgg(egg: RawEgg): Option[SunnySideUp]
~~~~

If we want to use this method in our `makeBreakfast` method, we have to match the `Some`, which is the intially full pan, containing another `Some`, which is the result of the frying process:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Breakfast =
  (pan.map(fryEgg), waterTank, coffeeBin) match {
    case (Some(Some(sunnySideUp)), Some(water), Some(beans)) =>
      Some((sunnySideUp, CupOfCoffee(boil(water), grind(beans))))
    case _ => (None, None)
  }
~~~~

This looks redundant. What will happen if we have to apply more processing steps with potentially disastrous outcomes, e.g. flipping the egg to produce an over-easy egg?

~~~~ scala
(pan.map(fryEgg).map(flip), ...) match {
  case (Some(Some(Some(overEasy))), ...) =>
~~~~

We essentially have an optional value of type `A`, a function `f` which transforms this value into another optional value of type `B`, and want to end up with an optional value of the result type `B`. These are the possible scenarios:

* If the initial option is `Some(a)`, apply `f` to `a`.
   * If the result is `Some(b)`, return `Some(b)`.
   * If the result is `None`, return `None`. 
* If the initial option is `None`, return `None`.

Of course Scala's `Option` type already provides this method. It is called `flatMap`, since it _maps_ the value to an `Option` of the result type, and then _flattens_ the two `Option`s to a single one:

~~~~ scala
sealed abstract class Option[A] {
  ...
  def flatMap[B](f: A => Option[B]): Option[B]
}
~~~~

Now let's use `flatMap` to deal with the case of the burnt egg:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Breakfast =
  (pan.flatMap(fryEgg), waterTank, coffeeBin) match {
    case (Some(sunnySideUp), Some(water), Some(beans)) =>
      (sunnySideUp, CupOfCoffee(boil(water), grind(beans)))
    case _ => (None, None)
  }
~~~~

`flatMap` enables us to chain an arbitrary number of processing steps and still end up with a simple `Option`:

~~~~ scala
def makeBreakfast(pan: Option[RawEgg], ...): Breakfast =
  (pan.flatMap(fryEgg).flatMap(flip), ...) match {
    case (Some(overEasy), ...) => (overEasy, ...)
    case _ => (None, None)
  }
~~~~

Maybe we can apply this concept to the validation of our input receptacles? After all, it follows the same pattern: We start with an optional value; if it is present, we continue with the next optional value and so on. Let's try using `flatMap` for this purpose:
 
~~~~ scala
type Breakfast = (OverEasy, CupOfCoffee)

def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Breakfast =
pan.
  flatMap(fryEgg).
  flatMap(flip).
  flatMap { overEasy =>
    waterTank.flatMap { water =>
      coffeeBin.flatMap { beans =>
        Some((overEasy, CupOfCoffee(boil(water), grind(beans))))
      }
    }
  }
~~~~

In the last step we can actually skip the `Some` and use `map` instead of `flatMap`:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Breakfast =
  pan.
    flatMap(fryEgg).
    flatMap(flip).
    flatMap { overEasy =>
      waterTank.flatMap { water =>
        coffeeBin.map { beans =>
          (overEasy, CupOfCoffee(boil(water), grind(beans)))
        }
      }
    }
~~~~

This is such a common use case that the Scala language provides syntactic sugar for it. Enter the `for` comprehension:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Option[Breakfast] =
  for {
    rawEgg <- pan
    sunnySideUp <- fryEgg(rawEgg)
    overEasy <- flip(sunnySideUp)
    water <- waterTank
    beans <- coffeeBin
  } yield (overEasy, CupOfCoffee(boil(water), grind(beans)))
~~~~

Now that we have such a neat breakfast program, it's time to take a little break and summarize what we came up with so far.

* We have invented a generic container which allows us to manipulate its content using functions without actually accessing it.
* We have invented a way to chain operations.

This is basically what monads are about. Using monads we can express a functional program as a series of processing steps, passing information from one step to the next. This way we can write purely functional programs in a way reminiscent of imperative programming.

Formally, a monad consists of

* A way to construct an instance of the monad type `M[A]` from an instance of the underlying type `A`. In the case of `Option[A]`, this is the case class constructor `Option(a)`.
* A _binding operation_ which takes an `M[A]` and a function `f: A => M[B]` and produces an `M[B]`. In our `Option` monad, this is the `flatMap` method. This operation is used to chain monadic processing steps.

Additionally, a monad has to fulfill three laws, which we illustrate using the `Option` monad:

* Left-identity: `Some(a).flatMap(f) == f(a)`
* Right-identity: `m.flatMap(a => Some(a)) == m`
* Associativity: `m.flatMap(f).flatMap(g) == m.flatMap(a => f(a).flatMap(g))`

# Error Handling

Our machine is now able to procure a decent breakfast, but it is very quiet about it. If we make a mistake when providing the ingredients, we are just presented with an empty tray. This can be problematic, especially once our breakfast will consist of mandatory and optional ingredients. Furthermore, we would like to know when an egg was burned or broke when it was flipped. In any case, we would like to know what stopped the machine from producing our breakfast.

In essence, we want our machine to output either a complete breakfast or a list of errors. For this purpose we introduce the type `Result` with two incarnations: `Success`, which represents a successful result, and `Failure`, which represents a failure together with some information about it in the form of a string:
 
~~~~ scala
abstract class Result[A]
class Success[A](a: A) extends Result[A]
class Failure(error: String) extends Result[A]
~~~~

Our `makeBreakfast` function will now return either a breakfast, or a failure with an error message:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Result[Breakfast]
~~~~

How can we incorporate error reporting in our `makeBreakfast` function? First, we introduce a new function to check whether an option contains a value, and produce a `Result` accordingly:

~~~~ scala
def validate[A](aOption: Option[A], error: String): Result[A] =
  aOption match {
    case Some(a) => Success(a)
    case None => Failure(error)
  }
~~~~

Now we can try using this function to check whether our recepticles are full or empty, and whether our frying and flipping operations were successful:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Result[Breakfast] =
  for {
    rawEgg <- validate(pan, "Missing egg")
    sunnySideUp <- validate(fryEgg(rawEgg), "Egg burnt")
    overEasy <- validate(flip(sunnySideUp), "Egg broken")
    water <- validate(waterTank, "Missing water")
    beans <- validate(coffeeBin, "Missing coffee")
  } yield (overEasy, CupOfCoffee(boil(water), grind(beans)))
~~~~

Now this won't compile, because we haven't implemented the `flatMap` and `map` methods in our `Result` type yet. Doing so is pretty straightforward:

~~~~ scala
abstract class Result[A] {
  def map[B](f: A => B): Result[B]
  def flatMap[B](f: A => Result[B]): Result[B]
}

case class Success[A](a: A) extends Result[A] {
  def map[B](f: A => B): Result[B] = Success(f(a))
  def flatMap[B](f: A => Result[B]): Result[B] = f(a)
}

case class Failure[A](error: String) extends Result[A] {
  def map[B](f: A => B): Result[B] = Failure(error)
  def flatMap[B](f: A => Result[B]): Result[B] = Failure(error)
}
~~~~

Now let's test our new `makeBreakfast` function:

~~~~ scala
makeBreakfast(Some(RawEgg()), Some(Water()), Some(CoffeeBeans()))
// Success((OverEasy(),CupOfCoffee(BoiledWater(),GroundCoffee())))
    
makeBreakfast(Some(RawEgg()), None, Some(CoffeeBeans()))
// Failure(Missing water)
~~~~

This is pretty neat, but as always there's more room for optimization.

# Modules

In the next iteration we want to make our breakfast program more modular. Let's create one module for the validation of the input receptacles, and one module for the actual breakfast preparation.

First, let's split up the code into two stages. In the first stage, all input recepticles are validated, which results in a `Result[(RawEgg, Water, CoffeeBeans)]`. In the second stage, if the result is a `Success`, the ingredients are processed into a breakfast, resulting in a `Result[Breakfast]`. Without further modifications the result of the `makeBreakfast` method would be a nested `Result[Result[Breakfast]]`, but we already know that we can use `flatMap` to avoid the nesting:

~~~~ scala
def makeBreakfast(
    pan: Option[RawEgg],
    waterTank: Option[Water],
    coffeeBin: Option[CoffeeBeans]): Result[Breakfast] = {

  val ingredients = for {
    rawEgg <- validate(pan, "Missing egg")
    water <- validate(waterTank, "Missing water")
    beans <- validate(coffeeBin, "Missing coffee")
  } yield (rawEgg, water, beans)

  ingredients flatMap { case (rawEgg, water, beans) =>
    for {
      sunnySideUp <- validate(fryEgg(rawEgg), "Egg burnt")
      overEasy <- validate(flip(sunnySideUp), "Egg broken")
    } yield (overEasy, CupOfCoffee(boil(water), grind(beans)))
  }
}
~~~~

In order to be able to work with modules, e.g. compose them in various ways, we have to represent them as values. Our modules are essentially functions `A => Result[B]`. Eventually we want to be able to express our breakfast program like this:

~~~~ scala
val makeBreakfast = validateIngredients andThen cookBreakfast
~~~~

For this purpose we create a wrapper `Module` for a function `A => Result[B]`. The module provides an `andThen` method which allows to connect the next module to it. The resulting module uses `flatMap` to execute the second submodule if the execution of the first one was successful:

~~~~ scala
case class Module[A, B](run: A => Result[B]) {
  def andThen[C](k: Module[B, C]): Module[A, C] =
    Module(a => run(a).flatMap(k.run))
}
~~~~

Now we can define our `validateIngredients` and `cookBreakfast` modules:

~~~~ scala
val validateIngredients = Module[
    (Option[RawEgg], Option[Water], Option[CoffeeBeans]),
    (RawEgg, Water, CoffeeBeans)] {
  case (pan, waterTank, coffeeBin) =>
    for {
      rawEgg <- validate(pan, "Missing egg")
      water <- validate(waterTank, "Missing water")
      beans <- validate(coffeeBin, "Missing coffee")
    } yield (rawEgg, water, beans)
  }

val cookBreakfast = Module {
  ingredients: (RawEgg, Water, CoffeeBeans) => {
    val (rawEgg, water, beans) = ingredients
    for {
      sunnySideUp <- validate(fryEgg(rawEgg), "Egg burnt")
      overEasy <- validate(flip(sunnySideUp), "Egg broken")
    } yield (overEasy, CupOfCoffee(boil(water), grind(beans)))
  }
}
~~~~

Let's implement our `makeBreakfast` module using these submodules and test it:

~~~~ scala
val makeBreakfast = validateIngredients andThen cookBreakfast

println(makeBreakfast.run((Some(RawEgg()), Some(Water()), Some(CoffeeBeans()))))
// Success((OverEasy(),CupOfCoffee(BoiledWater(),GroundCoffee())))

println(makeBreakfast.run((Some(RawEgg()), None, Some(CoffeeBeans()))))
// Failure(Missing water)
~~~~

The `Module` type can be generalized to work with all sorts of monads, in which case it is called a [Kleisli](http://typelevel.org/cats/datatypes/kleisli.html). Kleislis are a very convenient way of modularizing functional programs; they can be used to compose processing stages into complex data flows and pipelines.

At this point we conclude our little excursion into the world of functional programming with monads. Please feel free to use the comment section if you have any questions or remarks!

# Further Reading

* [A Fistful of Monads](http://learnyouahaskell.com/a-fistful-of-monads) in the ever-popular [Learn You A Haskell For Great Good](http://learnyouahaskell.com)
* [Demystifying the Monad in Scala](https://medium.com/@sinisalouc/demystifying-the-monad-in-scala-cc716bb6f534#.lgcmra7oh) by [Sinisa Louc](https://medium.com/@sinisalouc)

---

Cover image: [Two Sunny Side Up Eggs with Ham and Cilantro in a Small Pan](https://flic.kr/p/oc6Rwv) by [Nan Palmero](https://www.flickr.com/photos/nanpalmero/), licensed under [CC BY 2.0](http://creativecommons.org/licenses/by/2.0/)