Peeking Into State Monads

Posted on June 20, 2018 by Kendrick tan

Prelude

State monads, introduced to me during the data61 functional programming course was one of my most memorable encounter with a monad. This was mainly because things only started to clicked and made a tiny bit of sense after a couple of weeks of frustration.

This article is my attempt to explain the underlying mechanics of the State Monad to try and relief the frustration of whomever who was in my position.

This is also my first post on functional concepts, any feedback would be greatly appreciated.

You can grab the complete code below:

Introduction & Motivation

State monads were created to represent stateful computations in pure languages like Haskell. Stateful computations are computations which mutates the state of a non-local variable upon certain conditions.

Pure vs stateful functions

In functional programming, we like having our cake and eating it too - we want a pure function that is capable of embedding arbitrary state. When I first started functional programming I often got around this by adding an additional parameter to represent the current ‘state’ the function was in. E.g.

But this creates a lot of redundency and we can abstract this messy structure using State Monads. The definition of a State Monad is like so:

Which is just a more general form for stringOdd:

Peeking Into State Monads

runState

The definition of the State Monad: State (\s -> (a, s)) implies that the constructor State accepts a function which accepts something of type s and returns a tuple containing type a and s. As State accepts a function, we can’t just run it on its own as it is lacking its initial state of type s (which will be supplied by us). This is done using runState:

Constrasted with the less general format:

The only difference between the two is that runState unpacks the function f from the data constructor State before applying it to the variable of type s.

Functor, Applicative, Monad Instance

We know that Monads are a subset of Functors (specifically Applicative Functors), and as such we need to define State monad’s instance for Functor, Applicative, and Monad and the definitions of which can be seen below:

*Should you get stuck, try imagining it as a high school algebra test where you have to rearrange an equation (e.g. x = 10y + 5 -> y = (x - 5)/10) to solve for x/y. Match up all the types!

Functor Instance

Being a functor instance, we can now compose our function in construct State with any arbitrary function that takes an a and spits out a b. E.g:

Applicative Instance

Being a Applicative instance, we now have a more powerful tool for function composition. We can now compose the State Monad that returns a partial functions with a regular State Monad. This way, we are able to compose both the state (type s), and the output (type a)

Monad Instance

I’m not going to explain Monads, primarily because I don’t think I understand it enough to explain in a way that doesn’t fall into the “Monad Tutorial Fallacy” zone. So other than giving you an analogue of how Monads are like containers or a burrito, I’m simply going to tell you that we are defining the Monad instance in order to ultilize the do notation to have a higher level understanding of how to use the State Monad and why does it even work.

Put & Get

Before we proceed any further, we will define two helper functions - get and put.

It might not make sense now, but get allows us to extract the current state from the State Monad, whereas put allows us to ‘update’ the value of s in the State Monad (State s a).

Just keep that concept in the back of your head while we move onto the next section.

Usage

So, now that we have defined the foundation of our State Monad, we are ready to use it!

Wait, what? How does it do that? How does get extract the value from the State Monad and assign it to x? How does put update the state value?

Explanation

Lets start off by de-sugarizing the syntax.

Example 1

To understand what is going on behind the scenes in get, we need to take off our imperative programming hat and start thinking in terms of function composition. If we look back to the definition of (>>=):

Replacing

from example 1 yields:

Now, if we apply it to runState and supply it with an initial value of 10:

Therefore,

Example 2

To get a grasp of how put :: a -> (State (\_ -> ((), a))) works, we apply same technique from the previous example to obtain a better sense of what’s going on behind the hood. Recall that (>>) a b = a >>= \_ -> b. The function \_ -> b just means that our function ignores the input and just returns us b.

We can now replace

this yields us:

Now if we apply runState and supplying it with an initial value of 20, we’ll get:

Therefore,

And that is why get >>= (\x -> ..) will bind the current value (a from (a, s) to x), and put x will update the s in (a, s) to be the value x.

Conclusion & Summary

All in all, the State Monad is just an abstraction to impose State into pure functions (as the name suggests), and there exists a set of rules (e.g. Functor, Applicative, Monad) that states how these components compose together.

Should you get confused on why/how a certain component works, I suggest writing it down on paper and try figuring it out from there. If you are still stumped, there’s lots of helpful people on the #haskell IRC channel!