You Could Have Invented The State Monad
I’m attempting NICTA/course a second time. I gave up the last time because none of the State exercises were making sense and I found myself leaning so heavily on the solutions that I wasn’t actually learning anything. This time I was much better prepared after watching lots of CanFPG talks, reading lots of blog posts and writing a little Haskell, and I easily cleared the State hurdle. In fact, I’m now going to demonstrate how you (yes, you) could have come up with it (with a little help).
The fundamental insight of state is that it can be represented by a function that takes a value of type
s and returns a tuple of some value
a and a new value of type
Given such a type, what would its
Functor instance look like?
Our implementation should be another State that takes a value
s0, passes it to the second argument
sa (resulting in
(a, s1)) and calls the function
This is a State that takes
s0 and returns
(b, s1), which is exactly what we wanted.
Let’s look at the
Applicative instance next:
The implementation for
pure explains where the
a in our State comes from. Given some
a, return a State that, when fed a value
s, results in
(a,s). It practically writes itself.
(<*>) is a bit trickier, because we’re dealing with both the State the function is in and the State its argument is in. The implementation should be a State that takes a value
s0, feeds it to
sa to get
(fn, s1), feeds
sb to get
(a, s2), and calls
The hardest thing is remembering to thread
sb so that we don’t lose any state on the way. We can usually follow the types but they don’t help in this specific case.
Finally, let’s look at the
As with all our previous implementations, it has the form:
We know that we need to feed
sa to get an
a to apply to
The result of
fn a is a
State sb but we need to return a tuple of
(b, s). We can obtain one by feeding
Let’s define a few functions to make our lives easier.
get returns a State that, when fed some
(s,s). This allows us to expose
s for direct modification:
put allows us to store a State that ignores the
s passed to it later:
Sometimes we want the
s and not the
At other times we want the
a and not the
With all this machinery in place, we can do this:
I still couldn’t believe that this worked the first time I tried it, so let’s desugar this:
Let’s simplify from the bottom up. By the definition of
Plugging that back in, we have
Which we can simplify in the same way:
Finally, we have
This is my favourite thing about Haskell: the fact that it is built on abstractions that can be reasoned about in such a rigorous manner.
In fact, with some inspired renaming, you too could have invented the continuation monad.