More monads

As Pascal Costanza pointed out in a comment from yesterday, monadic style isn't just used for sequencing and stringing together I/O. The key notion is that if your language can't do X directly (for whatever X is), you can do it indirectly by piecing together little program fragments into a program that does X and then running that. Monadic style has the added advantage that you can separate the program fragments from the `plumbing' to keep the abstraction nice and clean.

So what's this `unit' and `bind' stuff that monad tutorials go on about? These are the two primitive elements that you need to bootstrap yourself into monad land. (Actually, monad tutorials tend to skip over the fact that you'll probably want to extract the data at the other end. `Unit' and `bind' will get you into monad land, but you're on your own if you want to get back.) `Unit' is the function that stuffs something into the chained return value that passes through the plumbing. It's easy to understand `unit' — that chained return value has to carry your data around and someone has to be able to construct them. `Bind' is the function you write that adds a new program fragment to the `plumbing'. `Bind' is nasty beast, though.

Bind is hard to understand because it has a strange type signature. If you're new to monads, you'll want to take a close look at this. Bind extends the plumbing, so the first argument to bind is the output of a piece of plumbing, that is, one of our chained return values. The second argument to bind is one of our program fragments. Now this is weird: we'll let our program fragment take whatever sort of arguments it wants, but we'll require it to return a chained return value. That's right — bind is only going to handle the input, but it is up to the program fragment to construct a chained return value on the output.

Let's take a look at a bind programs. Remember that the magic behavior of the monadic style is due to how the bind function is coded, so different monads will have different bind functions.

The `state' monad allows you to pretend that there is a location that holds some mutable state. The bind program looks like this:

(define (bind plumbing fragment)
  (lambda (chained-return-value)
    (let* ((intermediate-chained-return-value (plumbing chained-return-value))
           (intermediate-state (get-state intermediate-chained-return-value))
           (prior-fragment-return-value (get-return-value intermediate-chained-return-value))
           (next-computation (fragment prior-fragment-return-value)))
        (next-computation intermediate-state))))

.
Recall that the plumbing is going to be a program that consumes an initial state value and produces a final chained return value. Bind has to return a new piece of plumbing, so we return a lambda expression that takes the initial chained return value. When we get passed that value, the first thing we do is send it through the existing plumbing. But we grab the resulting output. The chained return value has to contain two things: the return value of the last fragment in the plumbing pipeline and the value of the intermediate `state'. We separate these components. We pass the return value of the previous fragment in to the fragment we are binding. It will return the final piece of plumbing to which we can pass the intermediate state.

This is a bit messy and confusing, so I'll try to restate it again in a simpler manner. To extend the plumbing with a fragment, we return a new piece of plumbing that works by first dropping the chained value through the old plumbing then capturing the output and sending it to the fragment (in two separate phases).

There's something about this that bothers me, but I'll save that for tomorrow.