[lincolnq]

Ugh. The nuclear waste metaphor is really lame.

Try this: My goal is to perform an inorder traversal of a binary search tree which stores integers. I wish to multiply each value in the tree by its index in the inorder traversal, so the min item is multiplied by zero and the maximum item by n-1.

How would you write this algorithm? In most languages, you can use mutable state as you are traversing the tree: create a variable called, say, 'i' which is multiplied by the current node, added to the current sum, and incremented after visiting each node.

In a pure functional language, you can't do this. Now imagine how you would implement it: you write a recursive function which accepts the current value of 'i', calls the left subtree, visits the node, increments i, calls the right subtree and returns the sum. But wait: you don't know how many elements were in the subtree, so each recursive call has to return the new value of i. Now you have the problem of "threading" the state of i properly through the different calls, and this is error-prone.

Monads help. You can think of a monad as passing an invisible argument to every function call, and then when that returns, doing something with it. In the case of the State monad, the invisible argument is the current state. The way it is threaded is as follows: when the previous function returns, take its state and execute the next function.

The exciting part about monads is that there are other possible threadings. The Reader monad, for instance, says the following: when the previous function returns, execute the next function. (Throw away the state.) This allows, for instance, read-only configuration data to be passed through your program without specifying it in every argument to every function that might need it. Functions can locally change the configuration data for their subfunctions, but they can't change it for their parents.

Was this helpful? I can continue, if you wish.

[gaius]

I would like continuation please (pun intended :-) )

[lincolnq]

Okay, then.

A monad is fundamentally a data structure -- an abstract data structure, with a known set of operations. With the State monad above, the data structure is a tuple (s, v) -- the 's' is the state, and the 'v' is the value. The whole thing is what the monadic function returns. The set of operations includes 'bind', which defines the sequencing logic, and 'return', which defines how to insert a value into the data structure (for State, 'return' just leaves the state untouched and puts the value into the monad).

One could think of some different data structures, and see whether they lead themselves to interesting monads. I like the Maybe data type. If you're used to OCaml, this is called Option. It is a variant type: either it contains a value (Just v) or it doesn't (Nothing). So how can this be thought of as a monad?

Here's one proposal: if the previous function returned a value, execute the next function. If it returned Nothing, then return Nothing. (i.e., don't execute the next function at all.)

Is this useful? Potentially. Let's say we want to look up a value in a map, and if it is found, then take some action. If it wasn't found, then don't take any action. The lookup function returns a Maybe value, which you can then sequence (using monadic bind) to the rest of the actions -- the sequencing operation takes care of the "did it succeed?" logic. If the next action doesn't return a Maybe value, then our code must use 'return' to insert its value back into the monad.

There's more. The List monad sequences by passing EACH value in the list to the next operation, and concatenating the results into a new list. The Continuation monad sequences just by executing the next operation, but it provides 'callcc,' which passes the given operation a closure which, when executed, executes the operation following 'callcc'.

Sorry for the brief explanation, I have to run. Ask me questions if you want more.

Lincoln

[gaius]

Thanks :-)

I'm going to have to do a bit more reading on this and try some experiments I think. Can't wait for Real World Haskell to ship!

[bkudria]

That was actually understandable! I've run into this "problem" before when playing around with FP, and I never quite knew how to solve it without ugly hacks. Now I know - thanks!