My colleagues and I recently have been trying to gain a deeper understanding of monads, other than using LINQ and RX. Watching all the channel9 videos on monads, the concept on the surface seemed quite simple, but we were felt that we were somehow missing some key point. After reading various blog posts, the penny is finally dropping.
Some post I read somewhere (I can’t remember where) said that it’s easier to understand the individual monads before trying to understand the whole generalised concept. Mike Hadlow’s blog series (http://mikehadlow.blogspot.co.uk/2011/01/monads-in-c1-introduction.html) really explain well the identity and maybe monads (which we already understood, which is just as well as we’re using the maybe monad in our codebase). Unfortunately he didn’t explain the state monad.
The only information we could find on the state monad in C# was Brian Beckman’s Channel 9 video: http://channel9.msdn.com/Shows/Going+Deep/Brian-Beckman-The-Zen-of-Expressing-State-The-State-Monad
We found Brian Beckman’s example overly complex, there’s quite a lot going on in that video (and the code needed de-obfuscating to read more like idiomatic C#), but it’s probably a good second or third example once the basics are understood. I wanted to look at a simpler example, and found this article: http://ertes.de/articles/monads.html#section-6 the explanation of the get and put methods show pretty clearly how the state monad works, and you should probably read and understand that section before carrying on here, as I’m going to jump straight on to show how the random number generator example looks in F# and C#.
First off, here’s an OO random number generator:
It is easy to add three random numbers together using an instance of the generator.
We can make NextShort purely functional, so that calling it has no side-effects, by passing the current state in, and returning the new state back out, along with the result:
To add three numbers, the state has to be kept around, and passed to each of the calls in turn. This obfuscates the main business logic.
Jumping straight to the punch line, using a state monad means that the boilerplate state management can be hidden away so that the algorithm reads as clearly as it did before:
This is a trivial example, but hopefully it makes the point. The rest of this blog post will show the implementation, along with the same in F#.
First off, we have a state class, which holds a Func that given a state, returns a tuple of the state and value. The F# example doesn’t bother with the State class, and I could have made the C# version simply use the Func everywhere, but it seemed clearer to me to have the wrapper object just to get a bit of context.
I created a non-generic State class as somewhere convenient to put the Get and Set methods:
The meat of the monad lives in extension methods in a StateEx class:
and SelectMany is implemented in terms of Bind the same as in Mike Hadlow’s example for the Identity and Maybe monads:
The computation to compose can be expressed in the GetRandom method:
This returns an operation (a Func in the State container) that invokes NextShort with the old state, and returns a computation with the new state and value.
The resulting composed operation using LINQ is described above, but this is what it looks like desugared:
The code for the random number generator and composed operation look similar to the C#:
This has the same problem of explicitly passing the state around. I can ruin the surprise again and show how using monads hides the explicit state passing:
This code makes use of F#’s support for monads via Computation Expressions. The code for the state builder is from here: http://www.navision-blog.de/2009/10/23/using-monads-in-fsharp-part-i-the-state-monad/
The Haskell example also had the >> operator, but of course F# uses that as the forward composition operator J
Instead I’ve implemented:
getRandom looks pretty much identical to the Haskell example:
The composed version using the StateBuilder is shown above, but here’s the desugared version:
The F# version is much clearer to read than the C#, in part due to the type inference meaning that the code has less pointless fluff. Having functions live in the module and not as part of a class aids that too (can simply call setState instead of State.Set in the C#)
Following through the simpler example really helped my understanding, and hopefully will see examples in the future where it will be sensible to use the state monad in my coding.