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.
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.
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.
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.
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.
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.
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 unit3.
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.
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.
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.
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.
Next that function in can be reduced down. This time the string "state" has moved to the end of the first line.
And again. Note that the function producing the pair has been replaced with the specific pair.
Now we can reduce down function. Recall that this function was introduced by the first m-bind.
This time we can increment 1 and replace the m-result with the result of that function.
The reduction should be starting to look familiar. "state" will be used to reduce the result of that m-result.
And finally reduce that down.
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.
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 state5. 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.
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.
I'll leave reductions of this to the more eager reader.
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.
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.