Sunday, January 20, 2019

Monad in imperative languages

TLDR: Monad is a design pattern to encapsulate a complicated sequence of actions. A monad M has two main attributes: a constructor to wrap a value of type T into a monadic value of type M<T>, and a function that takes a monadic function which transforms a value of type T into a monadic value of type M<U>, which is of the same monadic type M.

Introduction

Most articles about monads are illustrated with functional languages such as Haskell. Yet, most programmers are probably coming from imperative background. This mismatch creates an extra burden for the developers to learn the syntax and semantic of such functional languages to understand a simpler concept of a monad. This post is going to look at monad from an imperative/object oriented vantage.

What is a monad?

According to Wikipedia,

In functional programming, a monad is a design pattern that allows structuring programs generically while automating away bookkeeping code needed by the program logic.

The emphasis here is that a monad is a design pattern in the same Gang of Four sense. More specifically, a monad is a structural design pattern, the same category that adapter, composite, or decorator, for example, are in.

Why use a monad?

As with any design pattern, monad has a purpose.

With a monad, a programmer can turn a complicated sequence of functions into a succinct pipeline that abstracts away additional data management, control flow, or side-effects.

The main keyword in that sentence is sequence. Monad is most often used to chain a sequence of functions together. In other words, the main use of monad is in function composition.

This allows monads to simplify a wide range of problems, like handling potential undefined values (with the Maybe monad), or keeping values within a flexible, well-formed list (using the List monad)

Construction

Let us now dissect the components that make up a monad. As a whole, this is what Wikipedia says:

Given any well-defined, basic types T, and U, a monad consists of three parts:

  1. A type constructor M that builds up a monadic type M T

  2. A type converter, often called unit or return, that embeds an object x in the monad:

    unit(x) : T → M T
    
  3. A combinator, typically called bind (as in binding a variable) and represented with an infix operator >>=, that unwraps a monadic variable, then inserts it into a monadic function/expression, resulting in a new monadic value:

    (mx >>= f) : (M T, T → M U) → M U
    

Some of us might be scared away by the sheer number of jargons used in the above description. But read slowly, and we will find that they are pretty simple. A point by point translation is as followed.

  1. M is a generic type so that M<T> is also a type.

  2. M has a constructor that can take an argument of type T and return an object of type M<T>. This object is a monadic value. The signature of such a constructor could be:

    public static <T> M<T> unit(T value);
    

    Other common names are return, result, of.

  3. There is a method in type M that takes a function which takes a value of type T and returns a monadic value of type M<U>. This function is called monadic function. Below is one possible declaration:

    public <U> M<U> bind(java.util.function.Function<? super T, M<U>> f);
    

    Other common names are then, flatMap. It is important to note that the returned monadic value is of the same monadic type M. The parameter type U could be the same as T.

It can be seen that the constructor in the second bullet is also a monadic function. This repetitiveness allows us to sequence monadic functions.

                                    bind                      bind
T --monadic function-> M<T> --monadic function-> M<U> --monadic function-> M<Z>...

One more point to note here is the evaluation of f does not have to be immediate. In other words, bind may return a lazy monadic value that encapsulates both the current monadic value, and the passed-in monadic function for on-demand evaluation.

Example use case

This section looks at one example use of a very popular monad, the Maybe monad. We will start out with the problem statement and look at how it helps with code structure. We will be illustrating this example in Java.

Binary tree is a common data structure where one node has links to at most two children (named left and right), and at most one parent (named parent). Our example is a method that returns the sibling node to the current node, or null if the current node does not have any sibling.

/** Returns the sibling of this, or null if there is no sibling. */
public Node getSibling() {
  if (parent == null) {
    return null
  }
  return (this == parent.left) ? parent.right : parent.left;
}

With java.util.Optional, the above code could be written as followed.

/** Returns the sibling of this, or null if there is no sibling. */
public Node getSibling() {
  return Optional.ofNullable(parent)
      .flatMap(p -> Optional.ofNullable((this == p.left) ? p.right : p.left))
      .orElse(null);
}

Comparing the two versions, we can see that:

  1. The second version abstracts away the null check. The fact that parent, parent.left, and parent.right might be undefined is handled uniformly by Optional.
  2. The above behavior allows us to express the whole method as a sequence of actions: First go up to the parent, then go down to the appropriate branch.

If you have guessed that Optional is a monad, you are right! Optional is Java's equivalence of Haskell's Maybe. Line 3 shows the construction of an Optional object via its static factory method ofNullable. Line 4 demonstrates how one Optional is chained to another via the flatMap method.

And that is practically all there is to a monad.

Summary

The concept of monad is often illustrated and explained with a functional language and mathematical rigor. This post dissects the same concept in a more familiar imperative setting and simplified analysis.

At a high level, a monad is a structural design pattern that hides additional control flow, and state management from a complicated sequence of actions. At a low level, a monad is a generic type with 1) a constructor that wraps a plain value into a monadic value, and 2) a method that unwraps and feeds the plain value into a passed-in monadic function.

The real advantage of monads is that you can do use the do notation. That's all there is to it.

—Erik Meijer, from his FP101x class

No comments:

Post a Comment