Why are there so many of these "I finally understand [cloures | pointers | misc CS concept]" posts? I mean these are pretty fundamental concepts that any first year CS student should be able to grasp pretty quickly.
I think it's interesting to see how other people solve problems.
If you haven't found an application for such-and-such basic programming concept yet, chances are that's because your experience is so limited that you should probably spend more time coding instead of writing ejaculatory blog posts.
(not directed at the parent directly, more at the article, which wasted a minute of my precious life)
Pointers are easy if you understand the basics of how a computer works and know a language like C.
Likewise, closures are easy when you know a little about functional programming and understand first class functions.
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.
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
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!