State

In looking at the sequence monad and the set monad, we’ve seen that monads are partly determined by the container used to hold primitive values to make monadic values. So what other containers might we use? An obvious one is the hash-map and that can lead to some interesting monads like the probability monad. You can check out Konrad Hinsen’s monad tutorial for a look at that one. But we’ll turn our attention to a more interesting direction.

This post may be a bit long. The concepts here need to be broken into small steps using lots of words so that they can be internalized gradually.

Functions

Since Clojure is a functional language, that means that functions are first class. Which means that functions can be used as containers for other values. And how would we put a value into a function container?

(defn m-result [x]
   (fn []
      x))

That’s how. To get it out, all we have to do is call the newly created function.

((m-result 5))
=> 5

And the corresponding m-bind is not too complicated:

;; mv is a monadic value and
;; mf is a monadic function
(defn m-bind [mv mf]
   (let [new-v (mv)]
      (mf new-v)))

This m-bind simply takes the monadic value mv, gets the value it contains out by calling it and then calls the monadic function mf with that value to get a new monadic value. To find out what that new monadic value contains, all you have to do is call it. So if we define a simple monadic function:

(defn t [x]
   (fn []
      (inc x)))

And then use m-result and m-bind on it:

(def mv (m-bind (m-result 3) t))
=> #'user/mv

(mv)
=> 4

Something useful

All that is something of a curiosity, but pretty useless. How could we make something useful out it? What if instead of our monadic values (which are functions), accepting no arguments, we made them accept a single argument. So our m-result would look like:

(defn m-result [x]
   (fn [s]
      x))

Except that isn’t really any more useful than before. I suppose it would be possible to make the monadic values do something with their s argument combined with x. But we’re shooting for something bigger.

Suppose instead of returning x, we made our monadic value return x and s:

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

It may not be obvious, but now we have something quite powerful. Our monadic values now accept some kind of state value. Then they carry out some operation on x. And return a resulting value and an updated state value. In otherwords, our monadic values can now have side effects in addition to returning a value. Even more important, we’ve not given up our functional purity to do that. I’ll show this plays out in a little bit. But if you’ll bear with me a moment, I’ll show you the m-bind function first.

Binding state

To write an m-bind to match our m-result, we first have to realize that m-bind accepts a monadic value and a monadic function and returns a monadic value. So let’s lay down that skeleton first. Remember that a monadic value accepts a state value and returns a vector with a value and a new state value.

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

The first thing m-bind has to do is extract the value in mv by calling it with some state. The state value passed in will work beautifully for that.

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

When mv is called with the state value, it returns a vector with a value, captured by temp-v, and an update state value captured by temp-state. Then the monadic function originally passed into m-bind is called with temp-v to produce a new monadic value. And then that new monadic value is called with intermediate state value temp-state to produce the final return value from the monadic value returned from m-bind.

That’s all nested a bit deep to follow the first time through. The thing to see is that nothing really happens when m-bind is called except a new function is created which happens to be a monadic value. The real action happens when that monadic value is called with some state value as an argument.

What kind of state

We’ve been waving our hands about this state value that gets passed around without really saying what kind of value it is. And that’s the beauty of the state monad. The state value can be almost anything. To start with, we’ll work with state values that are simple vectors.

Doing it right

If you’ve been copying the code examples into your REPL, now would be a good time to start a fresh one. Rather than use the m-result and m-bind defined above, we’ll use the state monad defined in clojure.algo.monads/state-m which is identical.

So let’s create some monadic functions to work with. Remember, these are functions that accept a state value and return a monadic value, which is itself a function.

(use 'clojure.algo.monads)
(defn inc-s [x]
   (fn [state]
      [(inc x) (conj state :inc)]))

This function accepts an integer and returns a monadic value (a function). This monadic value accepts a state, then returns an incremented value of x and also adds :inc to the state value to indicate that it was executed. The following functions do similar operations:

(defn double-s [x]
   (fn [state]
      [(* 2 x) (conj state :double)]))

(defn dec-s [x]
   (fn [state]
      [(dec x) (conj state :dec)]))

And finally we can show the power of the state monad:

(defn do-things [x]
   (domonad state-m
      [a (inc-s x)
	   b (double-s a)
	   c (dec-s b)
	   d (dec-s c)]
	  d))
=> #'user/do-things

(def queued-up (do-things 7))
=> #'user/queued-up

(queued-up [])
=> [14 [:inc :double :dec :dec]]

So the answer produced by that sequence of operations on 7 is 14 and the final state value shows the order the operations where done in. Try calling queued-up with a hash-set or nil and see what you get.

(queued-up nil)
=> ??

(queued-up #{})
=> ??

Looking back at that domonad expression in do-things, notice how the threading of the state through the various stages is totally hidden. As programmer, you don’t have to worry about it. That code has already been written and debugged which frees you from having to reinvent the wheel. There are some other cool things to show about the state monad, and other monads too. But that will have to wait until next time.

Jim Duey 10 February 2012
blog comments powered by Disqus