Monads

Nov 03, 2019
#cs


Introduction

For the past few months, I've been trying to write a blog post about monads, but every time I start writing I get stuck. At this point I'm pretty frustrated, so I'm scrapping my original idea. Instead of giving a coherent explanation of monads, which I'm not qualified to do, I'm going to try* to describe the intuition behind them. Hopefully after reading this, you'll be able to:

*no guarantees of success

Here Goes Nothing

Monads are parametrized data types. A parametrized data type is a data type that accepts another data type as an argument. For example, vectors in C++ are parametrized data types: 

std::vector<int> my_vector;

In this case, we are passing the int data type as an argument to the vector data type, which essentially means that we are creating a vector of integers.

There are many different monads, so we'll use the option monad in our example. Since monads are parametrized data types, an option is actually an option of t, where t is any type, such as an integer. Therefore, you can think of a option<int> as a integer, wrapped in the context of an option.

Monads must provide a way to interact with the underlying type. In other words, given a function f that takes integers as input, there must be some way to apply that function to a option<int> as well. The extra context provided by the monad, however, can affect the output of the function. This is what makes monads so powerful.

Specifically in the case of a option monad, the context specifies whether the data actually exists or not. For example, a option<int> could be Some(1), or it could be None. You can think of Some and None as two sub-classes of options. Now, given a function f acting on an object x with type option<int>, the output should be f(a) if x = Some(a) and None if x = None.

This is all fine and dandy but the explanation so far probably doesn't make any sense so I'm going to try to write some pseudocode to give you the idea. Let's say we had some functions with integer inputs that either returned a new value if the input passes a check or None if it fails: 

def f(x):
  if x < 5:
    return None
  else:
    return 2*x + 1

def g(x):
  if x % 2 == 1:
    return None
  else:
    return x / 2

def h(x):
  if x == 3:
    return None
  else:
    return x * 3

Then, if we wanted to compose the two functions, we'd have to write the following ugly code: 

def hgf(x):
  t = f(x)
  if t is None:
    return None
  else:
    t = g(t)
    if t is None:
      return None
    else:
      return h(t)

This code is ugly because we have to check at each stage whether the previously computed result was invalid, and if so terminate the computation. How could we rewrite this with monads? First, let's set up the code for the option monad. Note that the following is python pseudocode: 

class Option:
  """Abstract supertype representing option<int>"""

  def __>>=__(self, f):
    """
    The infix left-associative 'bind' operator.
    f: int -> Option
    x >>= f :=
      match x with
      | Some(a) -> f(a)
      | None() -> None()
    """

    if type(self) == Some:
      return f(self.x)
    else:
      return None()

class Some(Option):
  def __init__(self, x):
    self.x = x

class None(Option):
  """Note that this is different from the None keyword in python"""
  def __init__(self):
    pass

In this code, we introduce the made up python infix operator >>=, which is technically called bind. You can think of x >>= f as equivalent to what we described earlier: f(a) if x == Some(a) else None. We also have to slightly rewrite our functions to satisfy the type signature int -> Option: 

def f(x):
  if x < 5:
    return None()
  else:
    return Some(2*x + 1)

def g(x):
  if x % 2 == 1:
    return None()
  else:
    return Some(x / 2)

def h(x):
  if x == 3:
    return None()
  else:
    return Some(x * 3)

Now that we've set everything up, how do we compose the functions together? Well, it becomes amazingly simple: 

def hgf(x):
   return Some(x) >>= f >>= g >>= h

It's practically a one-liner!

Intuition

To summarize, monads are software patterns that allow programmers to write clean code to handle chained computations by specifying default behavior in the "error" case, where the specific behavior and error case depends on the monad in use. This way, the programmer does not have to check for the error case explicitly at each step in the computation. In addition to Option, another common monad is Deferred, which represents the result of an asynchronous computation (the error case is when we have not finished computing the result). As you can imagine, the Deferred monad turns callback hell into callback heaven: 

// this is sad
AsyncGetX(function (x) {
  AsyncGetY(x, function (y) {
    AsyncGetZ(y, function (z) {
      console.log(z);
    }
  }
}

// this is nice
x >>= AsyncGetX >>= AsyncGetY >>= AsyncGetZ >>= console.log

Disclaimer

I have not provided a formal definition of a monad, nor enumerated all of their use cases. These are simply my observations of where monads come most in handy.

Further Reading





Comment