Welcome to the machine
Today I'm going to dive into the deep end and take a look at the State monad^{1}, 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^{2}. 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 statem monad. I've called it statem1
to avoid clashing with the statem in the monad library.
(use 'clojure.contrib.monads)
(defmonad statem1
[mresult (fn [value]
(fn [state]
[value state]))
mbind (fn [computation func]
(fn [state]
(let [[value newstate] (computation state)]
((func value) newstate))))])
While all the interesting behavior happens inside mbind
, mresult
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 mresult
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.
mbind
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 mresult
, mbind
returns a new function that takes a state and returns a valuestate pair. Second thing is the names of the arguments to mbind
. I have called them computation
and func
. computation
is the existing statemachine and func
is the function to use as the next step in the statemachine. In the same way that a linked list is a head and tail, and cons stitches them together, mbind
stitches together func
and computation
, the big difference is the facing. computation
is the many unit, and func
is the singular unit^{3}.
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 mystatemachine (domonad statem1
[myval (mresult 1)
myval2 (mresult (inc myval))]
myval2))
(mystatemachine "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 (mresult 1)
. This creates a function as we can see from the definition of statem1
. Specifically it produces
(fn [state] [1 state])
This becomes our computation for the first bind^{4}:
(mbind (fn [state] [1 state])
(fn [myval] (mresult (inc myval))))
Lets do a straight forward reduction here to see what we get. I've copied the body of mbind
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 [myval] (mresult (inc myval)))
:
(fn [state]
(let [[value newstate] ((fn [state] [1 state]) state)]
(((fn [myval] (mresult (inc myval))) value) newstate)))
Lastly we have a bind to get myval2
out of the big computation. This is once again a fairly straight forward reduction, only with a larger computation
.
(fn [state]
(let [[value newstate] ((fn [state]
(let [[value newstate] ((fn [state] [1 state]) state)]
(((fn [myval] (mresult (inc myval))) value)
newstate))) state)]
(((fn [myval2] (mresult myval2)) value) newstate)))
So thats the basic transformation from the domonad
notation. You can see how the various expressions have been stitched into the statemachine. 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 statemachine
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 newstate] ((fn [state]
(let [[value newstate] ((fn [state] [1 state]) state)]
(((fn [myval] (mresult (inc myval))) value)
newstate))) "state")]
(((fn [myval2] (mresult myval2)) value) newstate))
Next that function in can be reduced down. This time the string "state" has moved to the end of the first line.
(let [[value newstate] (let [[value newstate] ((fn [state] [1 state]) "state")]
(((fn [myval] (mresult (inc myval))) value) newstate))]
(((fn [myval2] (mresult myval2)) value) newstate))
And again. Note that the function producing the pair has been replaced with the specific pair.
(let [[value newstate] (let [[value newstate] [1 "state"]]
(((fn [myval] (mresult (inc myval))) value) newstate))]
(((fn [myval2] (mresult myval2)) value) newstate))
At this point we can remove the top let, destructuring the pair we just created into value
and newstate
:
(let [[value newstate] (((fn [myval] (mresult (inc myval))) 1) "state")]
(((fn [myval2] (mresult myval2)) value) newstate))
Now we can reduce down function. Recall that this function was introduced by the first mbind
.
(let [[value newstate] (((mresult (inc 1))) "state")]
(((fn [myval2] (mresult myval2)) value) newstate))
This time we can increment 1
and replace the mresult
with the result of that function.
(let [[value newstate] ((fn [state] [2 state]) "state")]
(((fn [myval2] (mresult myval2)) value) newstate))
The reduction should be starting to look familiar. "state" will be used to reduce the result of that mresult
.
(let [[value newstate] [2 "state"]]
(((fn [myval2] (mresult myval2)) value) newstate)))
Once more destructuring out the let
form
(((fn [myval2] (mresult myval2)) 2) "state")
Reduce the inter function
((mresult 2) "state")
Expand out mresult
((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 getstate
which returns the current value of the state, and putstate
which updates the current state^{5}. To get handle on whats going on at this stage, I like think of the value
as something like a register in the statemachine, and state
as the sole memory location.
(defn getstate []
(fn [state] [state state]))
(defn putstate [newstate]
(fn [_] [nil newstate]))
These functions follow the familiar form indicated by mresult
. The return a function that takes an initial state and returns a pair of value and current state.
getstate
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, putstate
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 statem1
[v (getstate)
_ (putstate (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.
 If you are unfamiliar with monads I would suggest you look else where. The api documentation provides links to a set of tutorials that are a good resource for Clojure programmers. You might also find my post Functions of functions useful.
 Parser Combinators are a way of describing a recursive decent parser using combinations of functions. These parsers can trivially have infinite lookahead, and the full expressive power of the host language. The canonical example of this idea is Parsec in Haskell, but the concept has been ported to many languages. In languages other than Haskell, they are often implemented using tricks other than monads, but Parsec is still the most elegant example.
 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.

I am assuming you understand how bind is rewritten into nested function application from its
domonad
form. 
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.