Transformers

In the last post, I mentioned monad transformers but didn’t explain them. So the let’s correct that.

m-bind the hard way

When implementing the DSL defined last time, we needed a monad that combined the behavior of the state monad and the maybe monad. We used the state-t monad transformer to create that monad. But now, we’re going to create that monad the hard way to illustrate what a monad transformer is and how it works.

The first thing we should do is implement m-result and m-bind. First up, m-bind. This should be almost identical to m-bind for state-m:

(defn m-bind [mv mf]
   (fn [state]
      (let [[temp-v temp-state] (mv state)]
         ((mf temp-v) temp-state))))

(refer back to here for a reminder of how the state monad works.)

The difference is we only want to call the monadic function mf if the result of (mv state) is not nil.

(defn composed-bind [mv mf]
   (fn [state]
       (let [result (mv state)]
          (if (nil? result)
             nil
             (let [[v new-state] result]
                 ((mf v) new-state))))))

m-bind: finding an easier way

Now, if we take a look at the m-bind function of the maybe monad, we see:

(defn maybe-bind [maybe-v maybe-f]
   (if (nil? maybe-v)
      nil
      (maybe-f maybe-v)))

The two if expressions look pretty similar and with a little refactoring we could use maybe-bind to write composed-bind. For a first step, see that maybe-v could be replaced by result, so that’s easy. Then all we have to do is create a function to drop in for maybe-f that contains the let statement from composed-bind:

(fn maybe-f [result]
   (let [[v new-state] result]
      ((mf v) new-state)))

With that piece, we can rewrite composed-bind like:

(defn composed-bind [mv mf]
   (fn [state]
      (let [result (mv state)]
         (maybe-bind result
                     (fn maybe-f [result]
                        (let [[v new-state] result]
                           ((mf v) new-state)))))))

And with some simple refactoring to clean it up, we end up with:

(defn composed-bind [mv mf]
   (fn [state]
      (maybe-bind (mv state)
                  (fn [[v new-state]]
                     ((mf v) new-state)))))

But that’s not all we can do. What if we wanted to make a composed-bind that used m-bind from a monad other than maybe-m? All we have to do is replace maybe-bind with m-bind and wrap the whole function in a with-monad.

(with-monad any-monad
   (defn composed-bind [mv mf]
      (fn [state]
         (m-bind (mv state)
                 (fn [[v new-state]]
                     ((mf v) new-state))))))

And now we can create a composed-bind that combines the m-bind from the state monad with the m-bind from any other monad.

m-result the not so hard way

The other half of the composed monad, m-result, is much simpler. Since we’re composing the state and maybe monads. And the m-result function for the maybe monad is just identity, the composed m-result function is the same as the m-result function for the state monad.

(defn composed-result [x]
   (fn [state]
      [x state]))

But suppose we wanted to compose the state monad with some other monad. Here’s what that looks like combined with the composed-result function.

(with-monad any-monad
   (defn composed-result [x]
      (fn [state]
         (m-result [x state])))

   (defn composed-bind [mv mf]
      (fn [state]
         (m-bind (mv state)
                 (fn [[v new-state]]
                     ((mf v) new-state))))))

And that is a primitive state monad transformer. The actual state-t monad transformer in clojure.algo.monads has some additional pieces to handle m-zero and m-plus. It also wraps everything in a function that accepts any monad to be composed with the state monad and returns the composed monad. This new monad can be used just like any other monad, including being passed to other monad transformers.

The big picture

Monad transformers can be summed up like this; they are functions that accept a monad as a parameter and return a monad composed of the parameter monad and the base monad. There is a different monad transformer for each base monad. And if you pass the identity monad to any monad transformer, the monad returned will be the base monad.

Jim Duey 05 March 2012
blog comments powered by Disqus