© 12 June 2014 Luther Tychonievich
Licensed under Creative Commons: CC BY-NC-ND 3.0
other posts

The worst-described part of computing I’ve yet encountered.


Monads are a powerful idea in programming theory, but they are not part of most programmer’s skill set. There are myriad monads introductions out there, but I read a dozen before I felt like I had any real idea what they were talking about. Here’s my stab at recording how I’ve come to think of monads. Hopefully it will help others too.

A simple type describes some kind of data. int is a common simple type, usually describing a particular family of integer numbers.

A function type describes an action: given some values with given input types, produce values with given output types. int × intint is a common function type, describing functions that take two Haskell, the most popular language to use monads, does not let functions take several values in; instead, it types + with int → (intint): + applied to 3 yields a function which can be applied to 2 to yield 5. ints in and produce one int out, which is what basic operators like + and × do.

A decorated type is like some simple type, but more fancy. [int] is a decorated version of int: instead of being just one number a value of type [int] is a list of zero or more numbers. int × Log is another decorated version of int used in paper-tape calculators: it’s a single number fancified by having a log file where it can record steps taken. We can decorate types however we wish; conceptually the decorated type is mostly like the undecorated but it has some extra information as well.

A decorating function has normal, simple types as inputs but decorated types as outputs. Square root might be a list-decorating function int[int]: sqrt(4) = [2, –2]. A paper-tape calculator might have a Log-decorating function int × intint × Log: add(2, 3) = (5, "2 + 3 = 5"). And so on. Again, there is no real limit to what the decoration can be as long as we think of the decoration as “‍extra‍”, not part of the main purpose.

There are two bits of plumbing that will make using decorations easier.

First, for each decoration we need to define a wrapping function that just adds “‍minimal‍” decoration; so for lists we might have wrap(3) = [3], for logs we might have wrap(3) = (3, ""), etc. An unwrapping function is sometimes nice too, though not as often as you might think.

Second, for each decoration we want a way of turning a decorating function into an decoration-preserving function that has decorated input and output. I’ll call this “‍redecorate‍”. Redecorate is a higher-order function: its input is a function and so is its output. The list redecorator has type (int[int]) → ([int][int]): it takes a list-decorating function in and produces a list-to-list function out. So redecorator(sqrt)([4, 9]) = [2, –2, 3, –3]. A log redecorator has type (int × intint × Log) → ((int × Log) × (int × Log) → int × Log): it takes a two log-decorated numbers and produces another log-decorated number. So redecorator(+)((2, "hi"), (5,"there")) = (7, "hi;there;2 + 3 = 5"). Defining redecorators is the trickiest part of making new monads.

These functions, assuming they meet a few basic properties such as redecorator(f)(wrap(x)) = redecorator(wrap)(f(x)), together form a “‍monad‍” Formally: let a be a simple type and T(a) be the decorated version of that type; then (T, wrap, redecorator) is a monad iff the monad coherence conditions hold. .

The theorems proven about monads in category theory are nice, I suppose, but the main reason we use monads is not because they are monads, per se, but because decorating values is a useful thing to do. Haskell, the most popular language to use monads Haskell has a slightly different version of redecorator it calls >>=; it calls wrap return; and it also has two other functions as well: >> combines two decorated values into one, and fail turns arbitrary text into a decorated value. , uses them for handling the possibility of execution failure, for variable-length results (like we did for square-root above), for the internal state of random number generators, for reading from input sources, for writing to output sources (similar to what we did for logs above), for interacting input/output communication (which is more involved than just input and output individually), and several other less common purposes as well. In most of these cases monads show up as a way of decorating values with “‍state‍”: sometimes same kinds of state we’d store with global variables in other languages, sometimes an internal representation of the state of things external to our program like a disk or network or user. And the really nice thing from Haskell’s point of view is that the monads naturally convert mutable state and causality restrictions into immutable values and dataflow restrictions.

I’m not sure why I found the first dozen monads writeups I read hard to follow. Partly it is my difficulty enjoying Haskell syntax, I suppose; partly because I mixed up the monads themselves for the purposes for which they were being used; and perhaps partly because I am not used to wrapping paper being the point. But in the end they are not complicated: a function that adds wrapping paper and a function that helps other functions work inside the wrapping paper.

Looking for comments…

Loading user comment form…