Doing Things

Easy composition

So far, we’ve looked at the sequence monad and the set monad. Hopefully by now you’ve gotten a feel for how m-result and m-bind work for those two examples. Obviously, working with just m-result and m-bind is cumbersome and doesn’t offer much improvement over more commonly used Clojure idioms. So lets change that.

Suppose you had the two functions we’ve been working with: (These are the set-m variants.)

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

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

If we compose them as before using m-bind,

(require 'clojure.set)
(defn m-result [n]
      #{n})

(defn m-bind [ns int-fn]
   (apply clojure.set/union
      (map int-fn ns)))

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

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

Capturing more info

Which is fine if all you want is the answers. But suppose that you’d like to know which value returned from half-double was responsible for which values returned from inc-int. You would want the result to be something like:

(do-both 8)
=> #{[4 9] [4 14] [16 21] [16 26]}

To accomplish this, we need to rewrite do-both. Starting with what we want to output, it’s obvious we need an expression that builds a vector:

(defn do-both [n]
... [x y])

That vector can’t just stand alone. It’s going to have be put into the proper container for our monad. In this case a set. This is easily done using m-result.

(defn do-both [n]
   ...
   (m-result [x y]))

Now the trick is to get the proper values of x and y. If we focus on y first, we see that it’s going to have to come from the primitive values inside the monadic values returned from inc-int. Remember, the way we unwrap monadic values is with m-bind. And m-bind takes two arguments, an expression that evaluates to a monadic value and a monadic function (a function that takes a primitive value and produces a monadic value). So adding a partial attempt at our m-bind expression:

(defn do-both [n]
   ...
   (m-bind (inc-int x)
           (fn fn-of-y [y]
               (m-result [x y]))))

The only way to assign a value to a symbol is through a function call. So we had to create fn-of-y as a monadic function so that m-bind could unpack the value returned by inc-int and assign it to y so it could be included in the final answer. And it’s paired with whatever value of x was passed to inc-int in order to produce that particular value of y.

Now where does x come from? If we wrap that m-bind expression in another anonymous function with x as a parameter, we’d have it:

(defn do-both [n]
   ...
   (fn fn-of-x [x]
       (m-bind (inc-int x)
               (fn fn-of-y [y]
                   (m-result [x y])))))

And since the value returned by a call to m-bind is a monadic value, the function fn-of-x is a mondic function because it accepts x (a primitive value) and returns a monadic value. And what do we do with monadic functions? We m-bind them. In this case to the value returned from half-double.

(defn do-both [n]
   (m-bind (half-double n)
           (fn fn-of-x [x]
               (m-bind (inc-int x)
                       (fn fn-of-y [y]
                           (m-result [x y]))))))

(do-both 8)
=> #{[4 9] [16 21] [4 14] [16 26]}

Generalizing

This is a lot of work just to compose two functions and capture the output of each stage. But notice that most of the code is boilerplate.

(defn do-both [n]
    (m-bind ...
        (fn [...]
            (m-bind ...
                (fn [...]
                    (m-result ...))))))

so it could be written as a macro once and used over and over. And since it’s written in terms of m-result and m-bind that macro would work for any monad and could compose any two functions to generate any resulting expression to produce a mondic value.

Also there’s no limit to the level of nesting you could do with m-bind, so you could write your macro to compose as many monadic functions as you wished. What you would need for each stage is the monadic function and the symbol that would catch the primitive values returned from it.

(defn do-both [n]
   (domonad
      [x (half-double n)
       y (inc-int x)]
      [x y]))

Where domonad is our magic macro. This form of composing monadic functions is call ‘monad comprehension’ and was first described in a classic paper, Comprehending Monads by Phillip Wadler. The syntax of that expression is referred to as ‘do-notation’.

Return of the familiar

That domonad expression should look awfully familiar.

(defn do-both [n]
   (for
      [x (half-double n)
       y (inc-int x)]
      [x y]))

In fact, Clojure’s for statement is exactly monad comprehension over the sequence monad we explained a couple of posts ago. As is doseq. Not only that, but

(let
   [x 10
    y 15]
   [x y])

Clojure’s let statement is monad comprehension over the identity monad which is defined as:

(def m-result identity)

(defn m-bind [x f]
    (f x))

So you’re already using monads! Clojure’s monad support comes from the clojure.algo.monads namespace written by Konrad Hinsen. It’s a great piece of code and well worth studying and using.

Finally (for now)

So far, we’ve been wading around in the shallow end of the monad pool. Next time, we jump into the deep end.

Jim Duey 08 February 2012
blog comments powered by Disqus