On 3/8/06, Jared Updike
I suspect you guys are right. I had always thought of states as being "isomorphic" to integers (i.e. you can be in state 0, state 1, ... state n), not as contexts (you have this input, that output, and this token stack), am I wrong?
You're thinking of a state machine, I think, which is not quite what a state monad would do here. (I have nightmares of writing a state-machine parser in assembly like I did in an EE class once... ouch).
I suspect I need to spend more time trying to understand the state monad. I must admit that I baulked the last time I tried to squeeze it into my head. I'll just need to try again ;)
Here's the way I like to think about state in imperative programs---it's hard because it's not something you can get far away from enough to see, usually.
In imperative programs, the value of a variable 'a' at one point is not always the value of the variable 'a' at another point later in the code. In some sense, each statement that gets executed is passed the entire state of the machine (the world) implicitly, and then when the statement ends, it passes the state of the world on to the next statement. If you want to access the value of the variable 'a', then 'a' gets looked up in the environment/state. In C/C++/Java/C#/Python/Perl, etc. this is done for you automatically and efficiently. It's just the way the machine works. But you don't have the choice to change this or, as someone put it, "overload the semicolon".
In Haskell none of this variable-mutating, state-passing **can** occur, so it gets created from scratch, and voila, we have the State Monad. It makes it sound like a lot more work than it should be just to do something that comes for free in most other languages, but in these languages, you can't overload the semicolon! And if you could, who knows what could go wrong at runtime (imagine Perl with semicolon overloading... I bet some day they will do this just because they can...). In Haskell, everything is watched over by the type system, so the parts of your program that explicitly need to munge state are isolated with the some type tag, e.g. ParseContext, while the rest of your program is "normal" and pure and functional.
The problem with monads is not that they are "advanced" but that they are so painfully and subtly abstract (I was going to say "subtly simple" but maybe they aren't for most working non-Haskell programmers...). (It just so happens that you **can** do amazing, convenient, efficient, magic and otherwise advanced things with them, especially with the libraries.) Another problem is that everyone has different ways of explaining them or trying to define what they are (a way of sequencing computation? or a type constructor? or a type class?). Of course, they are all those things, which makes it even more confusing. At a certain point, though, I think they just subconciously click and boom, now you get it.
Anyway, if your goal is to get people to understand Haskell, then see if you can use monads to simplify things. If your goal is to do a straight translation of the C code, don't worry about monads.
Dude, that was a friggin' awesome email! I'm trying to figure out how I can just copy it wholesale into the article ;) I've been struggling with Haskell for long enough that my knowledge is now snowballing downhill. Everything you said made sense 100%. Nice! -jj