This post is strictly about the programming technique. There is no philosophy or category theory. If you're interested in a more in-depth explanation of all the concepts related to monad, I have a longer series on the subject.

My goal with this post is not to convince you to start using monads everywhere; I only aim to make the technique easy to understand, using Clojure notation to explain it.

What is it for?

Monads are good for reifying side-effects while keeping your code pure. A single monad can reify all possible side-effects (like the IO monad in Haskell), or you can make a small, bespoke monad to reify just the one side-effect you want to allow in a specific context.

When spelled-out, monadic values (concrete instances of a specific monad) will look like an imperative DSL, with each line binding the return value of a side-effecting "operation" to a variable name. When you define a monad, you define the set of valid operations (i.e. effects).

All monads need two "special" monadic values: one that represents no operation (i.e. no side-effect, i.e. a pure computation), usually called "pure" or "return", and one that represents the effect of chaining together two effects, usually called "bind" (written >>= in Haskell, in case you've ever looked that way).

A monad with just those two is (usually) not very useful, so in general you will add more.

What makes a monad

As promised, no category theory definition. For our purposes, a monad is made out of:

• A data type with multiple variants, amongst which at least :return and :bind. We will refer to values of this type as "monadic values".
• A function that can "run" monadic values, with well-defined semantics for :return and :bind, and pretty much arbitrary semantics for all of the other variants. In the rest of this post, we'll refer to this function as "the run function".

By variant here we mean vectors where the first element is a keyword, and where the number and types of the other elements are defined by that keyword.

The :return variant has one element of any type; the :bind variant has two elements, where the first one is a monadic value and the second one is a function that takes a "normal" (non-monadic) value and returns a monadic value.

The run function applied to :bind must have the semantics of "unwrapping" the monadic value and applying its function to it.

Because Clojure is a dynamic language, and because the run function will be written as a case analysis on the type of its argument(s), we can fully formalize a specific monad by just specifying its run function.

A bit of syntax

There is a reason why most monad tutorials use Haskell: without syntactic support, monads are pretty clunky to use. Clojure does not have syntactic support out of the box, but, being a lisp, it has macros. This means we can add syntactic support, in the form of two macros:

(defmacro match
  [expr & cases]
  (let [e (gensym)]
    `(let [~e ~expr]
       (case (first ~e)
         ~@(->> (partition 2 cases)
                (mapcat (fn [[pat body]]
                          [(first pat)
                           `(let [~(vec (cons '_ (rest pat))) ~e]
                              ~body)])))))))

(defmacro mdo
  [bindings]
  (if (#{0 1} (count bindings))
    (throw
      (RuntimeException. "invalid number of elements in mdo bindings"))
    (let [[n v & r] bindings]
      (if (empty? r)
        v
        [:bind v `(fn [~n] (mdo ~r))]))))

Why we might want them will be clarified soon enough; for now, let's look at what they do.

First, the match macro will allow us to choose between a number of alternatives based on the first element of a vector. Here is an example expansion:

t.core=> (macroexpand-1 '(match expr
                           [:lit v] [v env]
                           [:var idx] [(get env idx) env]
                           [:set idx e] (let [[v env] (h e env)]
                                          [v (assoc env idx v)])))
(clojure.core/let [G__2018 expr]
  (clojure.core/case (clojure.core/first G__2018)
    :lit (clojure.core/let [[_ v] G__2018]
           [v env])
    :var (clojure.core/let [[_ idx] G__2018]
           [(get env idx) env])
    :set (clojure.core/let [[_ idx e] G__2018]
           (let [[v env] (h e env)]
             [v (assoc env idx v)]))))
t.core=>

We match on the first element of a vector, and bind the other elements to the symbols we give. In other words, this is a specialized, poor man's core.match. We could of course also just use core.match, but because we don't need its full power here, I don't want to import its full complexity.

This will be very useful in writing the run function, as the core of what it does is dispatching on its first argument.

Next, let's take a look at mdo. Here is an example use:

t.core=> (macroexpand-1 '(mdo [a [:return 5]
                               b [:return 3]
                               c [:return (+ a b)]
                               _ [:set 0 c]
                               v [:get 2]
                               _ [:return (+ v c)]]))
[:bind [:return 5] (clojure.core/fn [a]
                     (t.core/mdo (b [:return 3]
                                  c [:return (+ a b)]
                                  _ [:set 0 c]
                                  v [:get 2]
                                  _ [:return (+ v c)])))]
t.core=>

macroexpand-1 only does one round of macro expansion, so it's not all that useful for a recursive macro. Unfortunately, a full macroexpand is not a whole lot more useful:

t.core=> (macroexpand (mdo [a [:return 5]
                          b [:return 3]
                          c [:return (+ a b)]
                          _ [:set 0 c]
                          v [:lookup 2]
                          _ [:return (+ v c)]]))
[:bind
 [:return 5]
 #object[t.core$eval1756$fn__1757 0x2910aca
         "t.core$eval1756$fn__1757@2910aca"]]
t.core=>

So, you'll have to trust me a bit on this one, but here's the result of a manual recursive expansion of the macro:

[:bind [:return 5]
 (fn [a]
   [:bind [:return 3]
    (fn [b]
      [:bind [:return (+ a b)]
       (fn [c]
         [:bind [:set 0 c]
          (fn [_]
            [:bind [:lookup 2]
             (fn [v]
               [:return (+ v c)])])])])])]

The semantics we want here is that the run function will, when running on a [:bind ma f] value, first fully evaluate ma, then run the function f with the result of evaluating ma as the argument. This may be a bit clearer with an example.

A first example: ambient state

Let's make all of that a little bit more concrete. We start by defining an "ambient state" monad, one in which you can, at any point, reach out to a "global variable" that maintains some piece of state.

Specifically, we want to reify two effects:

• [:get k] will return the value associated to the key k.
• [:set k v] will set the value associated to key k to value v.

Here is the definition of this monad, in the form of a run function:

(defn run-ambient
  ([m] (run-ambient m {}))
  ([m env]
   (match m
     [:return v] [v env]
     [:bind ma f] (let [[v env] (run-ambient ma env)]
                    (run-ambient (f v) env))
     [:set k v] [v (assoc env k v)]
     [:get k] [(get env k) env])))

There's nothing very complicated about this code: we just keep around some state, in this case a map that represents our ambient state.

Applying that function to our earlier example of a monadic value yields:

t.core=> (run-ambient
           (mdo [a [:return 5]
                 b [:return 3]
                 c [:return (+ a b)]
                 _ [:set 0 c]
                 v [:get 2]
                 _ [:return (+ v c)]])
           {2 3})
[11 {2 3, 0 8}]
t.core=>

That's not very interesting, though. A more realistic use-case would involve calling functions on the right-hand side of these assignments. That would showcase a bit more of the power of this approach: our ambient state would still be available in those subfunctions.

As a more complex example, here is a bit of code that counts, for each type of expression, the number of times it appears in a program, for a simple AST. It also returns the total number of expression nodes in the program.

(defn sequenceM
  "Takes a list of monadic values ms, and returns
   a single monadic value that wraps a list."
  [ms]
  (if (empty? ms)
    [:return ()]
    (mdo [a (first ms)
          r (sequenceM (rest ms))
          _ [:return (cons a r)]])))

(defn update
  [k f]
  (mdo [v [:get k]
        _ [:set k (f v)]]))

(defn count-exprs
  [expr]
  (let [finc (fnil inc 0)]
    (match expr
      [:lit e] (mdo [_ (update :lit finc)
                     _ [:return 1]])
      [:var _] (mdo [_ (update :var finc)
                     _ [:return 1]])
      [:set _ e] (mdo [c (count-exprs e)
                       _ (update :set finc)
                       _ [:return (inc c)]])
      [:bin _ e1 e2] (mdo [c1 (count-exprs e1)
                           c2 (count-exprs e2)
                           _ (update :bin finc)
                           _ [:return (+ c1 c2 1)]])
      [:while e-cond e-body] (mdo [c1 (count-exprs e-cond)
                                   c2 (count-exprs e-body)
                                   _ (update :while finc)
                                   _ [:return (+ c1 c2 1)]])
      [:do & exprs] (mdo [counts (sequenceM (mapv count-exprs exprs))
                          _ (update :do finc)
                          _ [:return (reduce + 1 counts)]]))))

Note that sequenceM will work with any monad, while update is more specific to this one.

Running this yields:

t.core=> (run-ambient
           (count-exprs
             [:do
              [:set 0 [:lit 100]]
              [:set 1 [:lit 1000]]
              [:while
               [:bin :not= [:lit 0] [:var 1]]
               [:do
                [:set 0 [:bin :add [:bin :add [:bin :add [:var 0] [:lit 4]]
                                    [:var 0]]
                         [:lit 3]]]
                [:set 0 [:bin :add [:bin :add [:var 0] [:lit 2]]
                         [:lit 4]]]
                [:set 1 [:bin :add [:lit -1] [:var 1]]]]]
              [:var 0]]))
[29 {:lit 8, :set 5, :var 6, :bin 7, :do 2, :while 1}]
t.core=>

An interesting note to make about count-exprs is that there is no explicit threading of state through the recursive calls. The code reads as imperative, mutable code, while there is in fact no mutation going on.

Second example: non-deterministic computation

Monads are not just about state management: they can also be used to change the computation model. As a simple example, here is a monad that allows every (non-pure) computation to return multiple results, and runs all the results through the rest of the computation:

(defn run-nd
  ([ma] (run-nd ma []))
  ([ma s]
   (match ma
     [:return a] [a]
     [:bind ma f] (mapcat (comp run-nd f) (run-nd ma))
     [:multi ls] ls)))

Here is an example run, where we compute all four possible permutations:

t.core=> (run-nd (mdo [a [:multi [1 2]]
                       b [:multi [3 4]]
                       _ [:return (+ a b)]]))
(4 5 5 6)
t.core=>

We can make special operators for this monad. For example, we could make a filter that only returns positive values:

(defn filter-pos
  [a]
  [:multi (if (pos? a) [a] [])])

We can run that filter like this:

t.core=> (run-nd (mdo [a [:multi [-1 2]]
                       b [:multi [3 4]]
                       c [:return (* a b)]
                       d (filter-pos c)
                       _ [:return d]]))
(6 8)
t.core=>

A simple possible use-case would be the computation of the solution of quadratic equations:

(defn sqrt
  [x]
  (cond (neg? x)  [:multi []]
        (zero? x) [:return 0]
        (pos? x)  (mdo [sign [:multi [1 -1]]
                        _    [:return (* sign (Math/sqrt x))]])))

(defn div
  [a b]
  (if (zero? b)
    [:multi []]
    [:return (/ a b)]))

(defn solve-2nd
  [a b c]
  (mdo [d (sqrt (- (* b b) (* 4 a c)))
        x (div (- d b)
               (* 2 a))]))

where we define sqrt as a function that returns both roots for positive numbers, and none for negative ones. Similarly, div will return no solution for division by 0. This propagates directly to our solver, which will return zero, one or two answers:

t.core=> (run-nd (solve-2nd 1 2 1))
(-1)
t.core=> (run-nd (solve-2nd 1 3 1))
(-0.3819660112501051 -2.618033988749895)
t.core=> (run-nd (solve-2nd -2 0 -1))
()

Just like there was no explicit threading of state through the body of count-exprs, there is no explicit handling of multiple values in the body of solve-2nd.

What about category theory?

In order for a monad to be useful, the behaviour of :return and :bind need to follow a set of rules, generally known as "the monad laws" (sometimes "monadic" laws). In practice, it's pretty hard to violate the laws and still end up with something useful. Expressed in Clojure (and using the conventions described in this post), the laws would be:

(and
  (= (run [:bind [:return a] f])
     (run (f a)))
  (= (run [:bind m (fn [x] [:return x])])
     (run m))
  (= (run [:bind [:bind m g] f])
     (run [:bind m (fn [x] [:bind (g x) f])])))

Category theory gives a mathematical justification for those laws. That's it.

Conclusion

This only scratched the surface. Similarly to the first example, you could define a monad that represents the effect of interacting with your database. You could then define two run functions for it: one that actually interacts with the database, and one, used for testing, that only simulates those interactions. Your production code would still be the exact same mdo expression. You could define a monad where the run function is expected to receive multiple monadic values, and runs them concurrently, one :bind step at a time. This could give you green threads, possible with some synchronization mechanism à la core.async channels, in surprisingly little code.

Despite their power, monads are not used very much in Clojure. This is mainly because we have other, more familiar alternatives. The kind of state management presented in the first example can easily be achieved through passing around an atom, or actually using mutable ambient state in the form of a dynamic variable. The database use-case can be achieved through passing around an instance of a protocol, for which you'd have two implementations. Changing the computational model can be done through macros, as done in core.async and core.logic.

Ultimately, how much monads seem appealing to you will depend on how much you care about avoiding mutable state. I believe there is a place for mutable state, but there are cases where it's better to avoid it, and knowing about monads gives you one more technique for that.