State Monad in C# and F#

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#.

C# implementation

First off, here’s an OO random number generator:

clip_image00125255B425255D

It is easy to add three random numbers together using an instance of the generator.

clip_image00225255B525255D

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:

clip_image00325255B525255D

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.

clip_image00425255B425255D-1

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:

clip_image00525255B425255D-1

 

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.

clip_image00625255B425255D-1

I created a non-generic State class as somewhere convenient to put the Get and Set methods:

clip_image00725255B425255D

The meat of the monad lives in extension methods in a StateEx class:

clip_image00825255B625255D

and SelectMany is implemented in terms of Bind the same as in Mike Hadlow’s example for the Identity and Maybe monads:

clip_image00925255B425255D

The computation to compose can be expressed in the GetRandom method:

clip_image01025255B425255D

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:

clip_image01125255B425255D

F# implementation

The code for the random number generator and composed operation look similar to the C#:

clip_image012_thumb25255B125255D

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:

clip_image01325255B425255D

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/

clip_image014_thumb25255B125255D

The Haskell example also had the >> operator, but of course F# uses that as the forward composition operator J

Instead I’ve implemented:

clip_image015_thumb25255B125255D

getRandom looks pretty much identical to the Haskell example:

clip_image016_thumb25255B125255D

 

The composed version using the StateBuilder is shown above, but here’s the desugared version:

clip_image01725255B425255D

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.

1 thought on “State Monad in C# and F#”

  1. A good article. I also used the State Monad recently in a C# project, to implement an error handling pipeline where the cumulative result of the errors handled could be threaded discreetly through the computation. As Mike Hadlow says in his blog series on Monads, it's not too difficult to implement a Monad using LINQ once you learn how to 'follow the types'.

Comments are closed.