Monads for Clojure Programmers
Monads for Clojure programmers

    
    
    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 monadAs 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 syntaxThere 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 stateLet'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 computationMonads 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.ConclusionThis 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.
