Today I'm going to dive into the deep end and take a look at the State monad, with an implementation in Clojure. This will be done using Konrad Hinsen's clojure.contrib.monads API, but I will be providing my own specific monad implementations for continuity. You should use the API versions of any of these monads in the real world however.

The first question to ask is “why use a State monad in Clojure; there is already great support for state management in the language”. My answer is “because the State Monad is the foundation of more interesting monads.” In particular we will be looking at Backtracking State and Nondeterministic State monads. You might use Backtracking to build a parser combinator library. The Nondeterministic state allows you to find all the solutions that fit some problem. A simple example might be an implementation of the Quadratic Formula.

We'll look at these monads in turn, and then wrap up with a quick high level look at the role Monad Transformers could play, and the relationships between these variations on State and some other monads you may have already encountered: Identity, Maybe and Set.

State

First thing to consider about the state monad is what it is. Ignore the more academic answers to that question, the state monad is a way of building a state machine. It does not hold some state in it, instead it is a series of functions which a state is threaded through. Haskell has a curious looking type for State

newtype State s a = State { runState :: (s -> (a,s)) }

State is a wrapper type that contains a single value. This value is a function from type s to a pair of type a and type s. The curious thing about this definition is it uses the record syntax in Haskell to call the value runState. It does this so that you can unpack the state and apply it to the initial state in one step. Eg:

(runState myStateMachine) initialState  --  parens are for clarity

In Clojure land, we are going to not concern ourselves with a concrete wrapping type. Instead our monad will just return a function. The last thing to think about is what s and a represent. s is the state, and a is the value that that function returns. In our clojure code this will look like a function of one argument (the initial state) that returns a vector of two items: the value and the new state.

Before we go any further, lets have a quick look at the code for this state-m monad. I've called it state-m1 to avoid clashing with the state-m in the monad library.

(use 'clojure.contrib.monads)

(defmonad state-m1 
    [m-result (fn [value]
                  (fn [state]
                      [value state]))

     m-bind (fn [computation func]
                (fn [state]
                    (let [[value new-state] (computation state)]
                         ((func value) new-state))))])

While all the interesting behavior happens inside m-bind, m-result is indicative of the nature of the monad. Haskell calls this function return which sufficiently confuses many people, and I like to call it introduce because it introduces a new value into the computation. As is mentioned above, the State is a function from initial state to a value and new state, and as you can see m-result takes a value and returns a function. In this function, the value is constant, and the state is whatever state that gets passed through it.

m-bind provides the guts of the monad. And, because it does a whole lot of function wrangling, it can be a little difficult to wrap your brain around at first. Because this is key to understanding the rest of the monad, and the derivative monads, we will examine this one slowly.

First thing to notice is that like m-result, m-bind returns a new function that takes a state and returns a value-state pair. Second thing is the names of the arguments to m-bind. I have called them computation and func. computation is the existing state-machine and func is the function to use as the next step in the state-machine. In the same way that a linked list is a head and tail, and cons stitches them together, m-bind stitches together func and computation, the big difference is the facing. computation is the many unit, and func is the singular unit³.

Lets look at a very simple (and contrived) example. We'll look at how you set would write some code to use it, and then have a look at what that transforms into. This is going to introduce a value into the computation, increment it, and return that new value, all the while ignoring the state that the caller has specified.

 (def my-state-machine (domonad state-m1 
      [my-val (m-result 1)
       my-val2 (m-result (inc my-val))]
       my-val2)) 

 (my-state-machine "state") ;; -> [2 "state"]

If this looks like a strange way to write a let form to you, you would be right. We currently have no easy way to deal with the state in our state machine, we can only thread the value through. Before we do that though, lets unwind that expression.

First up is (m-result 1). This creates a function as we can see from the definition of state-m1. Specifically it produces

(fn [state] [1 state])

This becomes our computation for the first bind⁴:

(m-bind (fn [state] [1 state]) 
        (fn [my-val] (m-result (inc my-val))))

Lets do a straight forward reduction here to see what we get. I've copied the body of m-bind from above, and where it says computation I'm replacing it with (fn [state] [1 state]) and whenever it says func I'm replacing it with (fn [my-val] (m-result (inc my-val))):

(fn [state]
    (let [[value new-state] ((fn [state] [1 state]) state)]
         (((fn [my-val] (m-result (inc my-val))) value) new-state)))

Lastly we have a bind to get my-val2 out of the big computation. This is once again a fairly straight forward reduction, only with a larger computation.

(fn [state]
    (let [[value new-state] ((fn [state]
                                 (let [[value new-state] ((fn [state] [1 state]) state)]
                                      (((fn [my-val] (m-result (inc my-val))) value) 
                                       new-state))) state)]
         (((fn [my-val2] (m-result my-val2)) value) new-state)))

So thats the basic transformation from the domonad notation. You can see how the various expressions have been stitched into the state-machine. Next we'll do another set of reductions so you can see how the state is threaded through the stages of the machine. As above the string "state" be passed through.

Reducing the state-machine

Note: If you are comfortable with how this reduces down, skip on to the next section

First the argument to the machine is replaced (see the end of the second last line):

(let [[value new-state] ((fn [state]
                             (let [[value new-state] ((fn [state] [1 state]) state)]
                                  (((fn [my-val] (m-result (inc my-val))) value) 
                                   new-state))) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

Next that function in can be reduced down. This time the string "state" has moved to the end of the first line.

(let [[value new-state] (let [[value new-state] ((fn [state] [1 state]) "state")]
                            (((fn [my-val] (m-result (inc my-val))) value) new-state))]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

And again. Note that the function producing the pair has been replaced with the specific pair.

(let [[value new-state] (let [[value new-state] [1 "state"]]
                            (((fn [my-val] (m-result (inc my-val))) value) new-state))]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

At this point we can remove the top let, destructuring the pair we just created into value and new-state:

(let [[value new-state] (((fn [my-val] (m-result (inc my-val))) 1) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

Now we can reduce down function. Recall that this function was introduced by the first m-bind.

(let [[value new-state] (((m-result (inc 1))) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

This time we can increment 1 and replace the m-result with the result of that function.

(let [[value new-state] ((fn [state] [2 state]) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

The reduction should be starting to look familiar. "state" will be used to reduce the result of that m-result.

(let [[value new-state] [2 "state"]]
     (((fn [my-val2] (m-result my-val2)) value) new-state)))

Once more destructuring out the let form

(((fn [my-val2] (m-result my-val2)) 2) "state")

Reduce the inter function

((m-result 2) "state")

Expand out m-result

((fn [state] [2 state]) "state")

And finally reduce that down.

[2 "state"]

That looks like a lot of work, but it is actually straight forward. Still, its not very useful if it just provides a complicated version of the let form.

Manipulating the state

The most obvious state managing functions will be two primitives get-state which returns the current value of the state, and put-state which updates the current state⁵. To get handle on whats going on at this stage, I like think of the value as something like a register in the state-machine, and state as the sole memory location.

(defn get-state [] 
    (fn [state] [state state]))

(defn put-state [new-state]
    (fn [_] [nil new-state]))

These functions follow the familiar form indicated by m-result. The return a function that takes an initial state and returns a pair of value and current state.

get-state returns a function that takes the state value and places it in the value 'register', and leaves it in the state as well. In contrast, put-state takes a new state as its argument and the returns a function that ignores the current state, obliterates the value 'register' and updates the state.

So how would you go about using these two functions? Here is another contrived example that increments the current state, and returns the original value:

((domonad state-m1
    [v (get-state)
     _ (put-state (inc v))]
    v) 1) ;; -> [1 2]

I'll leave reductions of this to the more eager reader.

Wrapping up

So that's the basic State monad. It's likely you won't use this very often (ever?) in Clojure, but understanding it is very useful.

In the second (and final) part we'll take a look at a couple of variations on this concept, including looking at some small example programs that make use of them.

1. This is actually a simplification. In reality it might could be considered closer to two trees being joined as the leaves of a new tree.
2. I am assuming you understand how bind is rewritten into nested function application from its domonad form.
3. Once you are comfortable with how this simplistic implementation works, I would urge you to explore the code in clojure.contrib.monads.clj as it provides a much more sophisticated API, and uses some nice tricks. In contrast I have chosen to implement the canonical get and put.