Monads for Software Engineers

Gottfried_Wilhelm_von_Leibniz
The term monad could sound weird to a software engineer because it comes from category theory. There’s plenty of related maths material around but let’s just forget about it and about the choice of that word (BTW am I the only one being triggered Leibniz memories from high-school philosophy classes?): I’m interested in a software engineering perspective on the topic and, since I couldn’t find an introductory one that was clear enough for me, I decided to take a dive in and build my own.

What is a monad?

Very, very shortly: a data structure implements a monad interface iff it defines some “lifted-up” functions sequencing operator (think of a functional “;“-like sequencing).
So a monad itself is basically an interface meant to chain calculations that maintains some kind of additional “out-of-band” stuff, while still carrying this “context” along the way (here’s why I talk about “lifted-up” sequencing). For example they can carry state, IO conditions, error conditions, data structure markers, tags… Whatever.
Every interface having (at least) two specific methods (I’ll call them buildMonad and passMonadThrough) and satisfying certain “carry on” rules (we’ll see them in a moment) can be called a “monad”.

What are they useful for?

Monads are useful because in some circumstances they simplify and clarify code. They let you focus on the main functional transformation flow without being distracted by “contextual” information. Think of a “nil-checking” monadic sequencing operator that will nil-check results for you at every function application step and will short-circuit the transformational pipeline if at some point a nil value is produced.
An implementation of monads for Clojure is available as algo.monads, while a tutorial and some neat examples in Clojure have been written by Konrad Hinsen.

Under a monad’s cover

Let’s have a look at the interface definition and then at the “monadic behaviour” rules: I’ll use a lisp-style notation, except for the infix passMonadThrough and the x -> body style for anonymous functions with a single x parameter. C1 === C2 means that the computation C1 behaves the same as computation C2.
  • (buildMonad v): adds some context to a value v, building a new monad m
  • (m passMonadThrough f): it takes a value already enriched with a context (i.e. the monad m), a valid transformation of a “naked” value into something else with the same kind of context (i.e. the function f) and hooks the two in some implementation-specific way, but still observing the following “carry on” rules:
    1. ((buildMonad v) passMonadThrough f) === (f v): passing a value just enriched with a context (so, a newly built monad) through a context-injecting transformation will behave like applying the function to the simple-value part. This is the first monad constructor “neutrality” rule, called “left identity” (buildMonad is on the left of passMonadThrough).
    2. (m passMonadThrough buildMonad) === m: a context-enriched value (i.e., the monad m) passed through buildMonad should stay unchanged both in value and context. This is the second monad constructor “neutrality” rule, called “right identity” (buildMonad is on the right of passMonadThrough).
    3. ((m passMonadThrough f) passMonadThrough g) === (m passMonadThrough (x -> ((f x) passMonadThrough g)): a context-enriched (i.e. monad m) value passed through some context-injecting transformation (i.e. function f), and then passed through some other context-injecting transformation (i.e. function g) will yield the same result as passing the initial context-enriched value m to the passMonadThrough-mediated composition of f and g (and NOW I realize it’s much more easily understood by reading it than by explaining it…). This is the rule implementing “chaining” and it is called “associativity” (we’ll see in a moment why).
Basically the “chaining” rule mandates that the passMonadThrough method smash an input monad into any monad-building function (i.e. context-injecting transformation) in such a way that the result is “flattened” and doesn’t change the structure of the input monad’s “context”. This ensures that it can “pile up” any number of monad-building calls in a “last applied, last written” order.
In addition, passMonadThrough must do so in an associative fashion, so that there’s no need to specify precedence about subsequent calls: this means they can just be written in a straightforward sequence.
The identity-related laws, finally, ensure that the monad constructor buildMonad is neutral w.r.t. to passMonadThrough both when it’s on the left side and when it’s on the right side, which completes the “smooth” sequential behaviour.
If the above starts feeling like re-building a sequential, imperative-style control flow from functional programming and these “monad” interfaces, you are on the right track.

Example: lists as monads

Here’s a nice example: the list data structure can be turned into a monad by providing adequate monadic operations on it.
In the following, l is a list, vs are values and both f and g build a list of some kind from a value. I’ll shorten buildMonad as build and passMonadThrough as through.
Let’s define:
(build v) = [v]
(l through f) = (concat (map f l))
Let’s now verify the 3 rules (being l = [v] and (f v) = l').

1) Left identity

[v] through f = (concat (map f [v])) = (concat [l']) = l' = (f v)

2) Right identity

[v] through [] = (concat (map [] [v])) = (concat [v]) = [v]

3) Associativity

(l through f) through g
= (concat (map f l)) through g
= (concat (map g (concat (map f l))))
= (concat (map g (concat [[v1'] ... [vn']])))
= (concat (map g [v1' ... vn']))
= (concat [[v1''] ... [vn'']])
= [v1'' ... vn'']
l through (y -> ((f y) through g))
= (concat (map (y -> ((f y) through g)) l))
= (concat (map (y -> (concat (map g (f y)))) l))
= (concat [((y -> (concat (map g (f y)))) v1)
  ... ((y -> (concat (map g (f y)))) vn)])
= (concat [(concat (map g (f v1))) ... (concat (map g (f vn)))])
= (concat [(concat (map g [v1'])) ... (concat (map g [vn']))])
= (concat [(concat [v1'']) ... (concat [vn''])]
= (concat [[v1''] ... [vn'']]) = [v1'' ... vn'']

Few more notes

Some languages have specific syntax to use monadic interfaces (e.g. Haskell) while others can build monadic DSLs quite easily (e.g. Clojure). Some languages with monad implementations have rigorous compile-time type-systems (e.g. again Haskell) and others are dynamic (Clojure).
Please note that the monadic behaviour rules are specified in terms of runtime behaviour, so typically the developer has to ensure that they hold with little or no compiler support.
I hope the above will help people (like me) looking for a less mathematical and a more computational perspective on monads!

Leave a Reply