Mmm... sweet tasty state monads December 12, 2011
One of the really challenging things about Haskell is the lack of state... or more specifically, the lack of global state.
In Scala there are a ton of places you can put state (stuff that's mutated across method invocations.) You can use globals, thread-local variables (something that Lift makes heavy use of), and instance variables. Here are some examples:
Global:
object MyState {
private var cnt = 0
def inc = synchronized {cnt += 1}
def dec = synchronized {cnt -= 1}
def getCnt = synchronized {cnt}
}
Instance variables are pretty much the same, except you have to pass the instance around:
class MyState {
private var cnt = 0
def inc = synchronized {cnt += 1}
def dec = synchronized {cnt -= 1}
def getCnt = synchronized {cnt}
}
In Haskell, there's no mutability, so if you have a reference to a chunk of data, the data will never change. In order to change the state, you must create a new instance, but any holder of the old reference see the old data. In general, this is a GoodThing™ because you don't have to worry about state changing out from under you, but it makes accumulating state pretty difficult. For example, if we want to count the number of hellos and goodbyes and accumulate the names of the people who said Hello or Goodbye, it's easy to do:
val state = new MyState
val greeters = List(("David", "Hello"), ("Archer", "Woof"), ("Annette", "Bye")).flatMap {
case (name, "Hello") => state.inc ; List(name)
case (name, "Bye") => state.dec ; List(name)
case _ => Nil
}
At the end of the above execution, we have a list of people who have made greetings and the side effect of updating the state object with the net Hello/Bye count.
In Haskell, without the State monad, we'd have to accumulate both the count and the names and then fold across them:
list = [("David", "Hello"), ("Archer", "Woof"), ("Annette", "Bye")]
gTest (name, "Hello") = (1, [name])
gTest (name, "Bye") = (-1, [name])
gTest _ = (0, [])
acc = map gTest list
sumIt (i1, n1) (i2, n2) = (i1 + i2, n1 ++ n2)
summed = foldr1 sumIt acc
As the state that we carry around becomes more complex, it. Further, having to fold our result in sumIt is counterintuitive. We've already done the calculation, why do we have to fold the pairs into the final result?
There's a simpler way to carry state around in Haskell. Here's an example:
-- the stateful test
sTest v =
do
i <- get -- get the current state
case v of
-- update the state and then return the value
(name, "Hello") -> put (i + 1) >> return [name]
(name, "Bye") -> put (i - 1) >> return [name]
_ -> return []
sAcc = (mapM sTest list)
sSummed = mapFst concat $ runState sAcc 0
In the above code, we're separating the state from the core name calculation. The get function get the state into the variable i. Depending on the greeting, we increment, decrement or ignore the state.
Now, the thing that confused me for years about the State monad was where "get" was getting from and where "put" was putting it. Well, it's like this, the State Monad is actually some accumulated functions that are "played" by the runState function. sAcc function returns a bunch of functions. The runState function takes that function and a seed value (in this case, 0), and plays the function to get the resulting information and the resulting state.
The State Monad makes stuff like parsing and keeping state while parsing (e.g., the current count of AST elements we've encountered) is very powerful and makes Haskell code that is in effect imperative a lot easier to write.
I recently tried to implement Hindley-Milner type inferencing without the State Monad and the code was nasty and complex with lots of state being returned all over the place (see https://github.com/visi-lang/visi/commit/cfe7d6fe5a6b25795a1c32ab2f18cfcbad1f9b54#diff-1 and all the atv, atv', etc. state) and then https://github.com/visi-lang/visi/blob/b8f06c73f66596af8333ab09d9528bada068a188/core/src/Visi/Typer.hs Note that all the state stuff is handled in the State Monad rather than cluttering up the logic of the code. I've come to really like the State Monad a lot... it makes me feel somewhat imperative while being functional. ;-)