Monads In Clojure

This blog is obviously about Clojure. I’m going to start off talking about Domain Specific Languages. But some foundations need to be laid first.

Monads are design patterns for writing DSL’s. They can help you write your DSL quickly and correctly. There are already a ton of monad tutorials out there, but I wanted to provide one-stop-shopping. If you really want to grok monads, type the code examples in at the REPL and see how the functions behave.

Monadic Motivation

Suppose you had a function that accepted an integer and returned a list containing that integer doubled and halved:

(defn half-double [n]
   [(/ n 2) (* 2 n)])

(half-double 10)
=> [5 20]

And suppose you had another function that accepted an int and returned a list with it incremented by 5 and by 10:

(defn inc-int [n]
   [(+ 5 n) (+ 10 n)])

(inc-int 3)
=> [8 13]

Now write a function that accepts an integer, calls half-double on it and then calls inc-int on each of the numbers produced by half-double. But you can’t use Clojure’s ‘for’ function because that would be cheating. Take a crack at it your self before continuing.

Did you come up with something like:

(defn do-both [n]
   (apply concat
      (map inc-int
         (half-double n))))

(do-both 8)
=> (9 14 21 26)

Using the technique of (apply concat (map ... )), it is possible to compose any function that takes an integer and returns a list of integers. So lets factor that pattern out into something generally useful.

Binding

(Totally unrelated to Clojure’s binding form.)

Since functions are first class entities, you could write a function that accepts two functions and returns the composed function. Except that’s not general enough. What do you do in the case where you want to compose 3, 4, or 5 functions?

A better way is to write a function that will take a list of ints and a function, and map the function over the ints and concat the results. We’ll call this function m-bind.

(defn m-bind [ns int-fn]
   (apply concat
      (map int-fn ns)))

(defn do-both [n]
   (m-bind (half-double n) inc-int))

(do-both 8)
=> (9 14 21 26)

That m-bind is one-half of the sequence monad in Clojure.

Results

For the other half, a little contrivance is required, but first some terminology.

For the sequence monad, a list of values (in this case integers) is a monadic value. And the functions half-double, inc-int and do-both are examples of monadic functions. A monadic function is a function that accepts a value and returns a monadic value. For the sequence monad, you can think of the list as a container that holds primitive values.

Notice that m-bind’s first argument must be a monadic value (a list of integers). So how do you take an ordinary integer and convert it into a monadic value? The simple answer is the list function, which we’ll rename to a standard name.

(def m-result list)

That definition of m-result is the other half of the sequence monad in clojure. The names m-result and m-bind are standard names and all monads must have those functions defined at a minimum. Furthermore, those functions can’t just be any old functions. They have to be defined to work together according to the 3 monad laws. Those laws will be the subject of a future post.

Jim Duey 02 February 2012
blog comments powered by Disqus