Monads for functional programming – Wadler, 1992

There’s something about the word ‘monad’, and about the concept of monads, that people find off-putting. If this was a paper coming from an OO (e.g. Java) perspective it might have been titled something like “A principled approach for wrapper types” which doesn’t sound nearly so daunting does it?

Philip Wadler does a great job demystifying this concept and explaining why it’s sorely needed in a pure functional language.

Pure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit.

Some things that are really easy to do in your favourite statement-based language turn out to be really hard to do elegantly in a pure functional language. Everything involves trade-offs. Wadler sets out the problem so well that an extended quote is in order:

It is with regard to modularity that explicit data flow becomes both a blessing and a curse. On the one hand, it is the ultimate in modularity. All data in and data out are rendered manifest and accessible, providing a maximum of flexibility. The essence of an algorithm can become buried under the plumbing required to carry data from its point of creation to its point of use. Say I write an evaluator in a pure functional language….

• To add error handling to it, I need to modify each recursive call to check for and handle errors appropriately. Had I used an impure language with exceptions, no such restructuring would be needed.
• To add a count of operations performed to it, I need to modify each recursive call to pass around such counts appropriately. Had I used an impure language with a global variable that could be incremented, no such restructuring would be needed.
• To add an execution trace to it, I need to modify each recursive call to pass around such traces appropriatesy. Had I used an impure language that performed output as as side effect, no such restructuring would be needed.

Or I could use a monad.

There are some things for example that an OO language makes easy to do, such as encapsulating state. And there are some common situations that require a little more machinery. The Gang of Four introduced us to the world of patterns for these cases. If the Gang of Four had been writing about pure functional languages, they might have called monad ‘The Wrapper Pattern.’ As Wadler says:

It is doubtful if the structuring methods presented here would have been discovered without the insight afforded by category theory. But once discovered they are easily expressed without any reference to things categorical. No knowledge of category theory is required to read these notes.

(or to use this pattern).

To add error-handling to the functional evaluator, Wadler shows that you can introduce a new wrapper type that can encaspulate either the return value from a successful expression evaluation, or a string-based exception. To add a count of the number of divisions performed, Wadler shows that you can add a new wrapper type that encapulates both the result of the evaluation, and a counter. To add an execution trace, Wadler shows that you can introduce a new wrapper type that encapsulates both the result of the evaluation, and an accumulating string of output.

There’s a nice aside at this point:

From the discussion so far, it may appear that programs in impure languages are easier to modify than those in pure languages. But sometimes the reverse is true. … displaying the execution trace in reverse order … is simplicity itself to achieve with the pure functional program. It is not so easy to modify the impure program to achieve this effect.

By looking at what’s common to these cases, we can extract a general pattern. Let’s call that ‘monad.’

In each variation, we introduced a type of computations. Respectively, M represented computations that could raise exceptions, act on state, and generate output. By now the reader will have guessed that M stands for monad. The original evaluator has the type Term -> Int, while in each variation its type took the form Term -> M Int. In general, a function of type a -> b is replaced by a function of type a -> M b. This can be read as a function that accepts an argument of type a and returns a result of type b, with a possible side effect captured by M.

Wadler then goes on to show the laws for monads, and give two other extended examples – one showing how to do efficient array indexing, and the other showing how the monad pattern can be applied to the creation of parsers. The evaluator example is the easiest to read and grok quickly, the parser example shows the power that comes when you start building on top of this new abstraction. I found chapter 8, “Functional Parsers” of Graham Hutton’s “Programming in Haskell” book an easier introduction to the parsing case.

I’ll leave the summary to Wadler:

Monads provide a convenient framework for simulating effects found in other languages such as global state, exception handling, output, or non-determinism.