The State monad by Mark Seemann
Stateful computations as a monad. An example for object-oriented programmers.
This article is an instalment in an article series about monads. A previous article described the State functor. As is the case with many (but not all) functors, this one also forms a monad.
This article continues where the State functor article stopped. It uses the same code base.
SelectMany #
A monad must define either a bind or join function. In C#, monadic bind is called SelectMany. Given the IState<S, T> interface defined in the State functor article, you can implement SelectMany like this:
public static IState<S, T1> SelectMany<S, T, T1>( this IState<S, T> source, Func<T, IState<S, T1>> selector) { return new SelectManyState<S, T, T1>(source, selector); } private class SelectManyState<S, T, T1> : IState<S, T1> { private readonly IState<S, T> source; private readonly Func<T, IState<S, T1>> selector; public SelectManyState( IState<S, T> source, Func<T, IState<S, T1>> selector) { this.source = source; this.selector = selector; } public Tuple<T1, S> Run(S state) { Tuple<T, S> tuple = source.Run(state); IState<S, T1> projection = selector(tuple.Item1); return projection.Run(tuple.Item2); } }
As SelectMany implementations go, this is easily the most complex so far in this article series. While it looks complex, it really isn't. It's only complicated.
The three lines of code in the Run method does most of the work. The rest is essentially ceremony required because C# doesn't have language features like object expressions.
To be fair, part of the boilerplate is also caused by using an interface instead of functions. In F# you could get by with as little as this:
let bind (f : 'a -> State<'b, 's>) (x : State<'a, 's>) state = let x', newState = run state x run newState (f x')
I found an F# State implementation on my hard drive that turned out to originate from this Code Review answer. You can go there to see it in context.
The SelectMany method first runs the source with the supplied state. This produces a tuple with a value and a new state. The value is tuple.Item1, which has the type T. The method proceeds to use that value to call the selector, which produces a new State value. Finally, the method runs the projection with the new state (tuple.Item2).
Monadic bind becomes useful when you have more than one function that returns a monadic value. Consider a code snippet like this:
IState<int, string> s = new Switch("foo", "bar").SelectMany(txt => new VowelExpander(txt));
This uses the silly VowelExpander class from the State functor article, as well as this new frivolous State implementation:
public sealed class Switch : IState<int, string> { private readonly string option1; private readonly string option2; public Switch(string option1, string option2) { this.option1 = option1; this.option2 = option2; } public Tuple<string, int> Run(int state) { if (0 <= state) return Tuple.Create(option1, state); var newState = 0; return Tuple.Create(option2, newState); } }
Both Switch and VowelExpander are State objects. If SelectMany didn't flatten as it goes, composition would have resulted in a nested State value. You'll see an example later in this article.
Query syntax #
Monads also enable query syntax in C# (just like they enable other kinds of syntactic sugar in languages like F# and Haskell). As outlined in the monad introduction, however, you must add a special SelectMany overload:
public static IState<S, T1> SelectMany<S, T, U, T1>( this IState<S, T> source, Func<T, IState<S, U>> k, Func<T, U, T1> s) { return source.SelectMany(x => k(x).Select(y => s(x, y))); }
As already predicted in the monad introduction, this boilerplate overload is always implemented in the same way. Only the signature changes. With it, you could instead write the above composition of Switch and VowelExpander like this:
IState<int, string> s = from txt in new Switch("foo", "bar") from txt1 in new VowelExpander(txt) select txt1;
That example requires a new variable (txt1). Given that it's often difficult to come up with good variable names, this doesn't look like much of an improvement. Still, it's possible.
Join #
In the introduction you learned that if you have a Flatten or Join function, you can implement SelectMany, and the other way around. Since we've already defined SelectMany for IState<S, T>, we can use that to implement Join. In this article I use the name Join rather than Flatten. This is an arbitrary choice that doesn't impact behaviour. Perhaps you find it confusing that I'm inconsistent, but I do it in order to demonstrate that the behaviour is the same even if the name is different.
The concept of a monad is universal, but the names used to describe its components differ from language to language. What C# calls SelectMany, Scala calls flatMap, and what Haskell calls join, other languages may call Flatten.
You can always implement Join by using SelectMany with the identity function.
public static IState<S, T> Join<S, T>(this IState<S, IState<S, T>> source) { return source.SelectMany(x => x); }
Here's a way you can use it:
IState<int, IState<int, string>> nested = new Switch("foo", "bar").Select(txt => (IState<int, string>)new VowelExpander(txt)); IState<int, string> flattened = nested.Join();
Of the three examples involving Switch and VowelExpander, this one most clearly emphasises the idea that a monad is a functor you can flatten. Using Select (instead of SelectMany) creates a nested State value when you try to compose the two together. With Join you can flatten them.
Not that doing it this way is better in any way. In practice, you'll mostly use either SelectMany or query syntax. It's a rare case when I use something like Join.
Return #
Apart from monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function return (because that's the name that Haskell uses):
public static IState<S, T> Return<S, T>(T x) { return new ReturnState<S, T>(x); } private class ReturnState<S, T> : IState<S, T> { private readonly T x; public ReturnState(T x) { this.x = x; } public Tuple<T, S> Run(S state) { return Tuple.Create(x, state); } }
Like the above SelectMany implementation, this is easily the most complicated Return implementation so far shown in this article series. Again, however, most of it is just boilerplate necessitated by C#'s lack of certain language features (most notably object expressions). And again, this is also somewhat unfair because I could have chosen to demonstrate the State monad using Func<S, Tuple<T, S>> instead of an interface. (This would actually be a good exercise; try it!)
If you strip away all the boilerplate, the implementation is a trivial one-liner (the Run method), as also witnessed by this equivalent F# function that just returns a tuple:
let lift x state = x, state
When partially applied (State.lift x) that function returns a State value (i.e. a 's -> 'a * 's function).
Again, you can see that F# code in context in this Code Review answer.
Left identity #
We need to identify the return function in order to examine the monad laws. Now that this is done, let's see what the laws look like for the State monad, starting with the left identity law.
[Theory] [InlineData(DayOfWeek.Monday, 2)] [InlineData(DayOfWeek.Tuesday, 0)] [InlineData(DayOfWeek.Wednesday, 19)] [InlineData(DayOfWeek.Thursday, 42)] [InlineData(DayOfWeek.Friday, 2112)] [InlineData(DayOfWeek.Saturday, 90)] [InlineData(DayOfWeek.Sunday, 210)] public void LeftIdentity(DayOfWeek a, int state) { Func<DayOfWeek, IState<int, DayOfWeek>> @return = State.Return<int, DayOfWeek>; Func<DayOfWeek, IState<int, string>> h = dow => new VowelExpander(dow.ToString()); Assert.Equal(@return(a).SelectMany(h).Run(state), h(a).Run(state)); }
In order to compare the two State values, the test has to Run them and then compare the return values.
Right identity #
In a similar manner, we can showcase the right identity law as a test.
[Theory] [InlineData( true, 0)] [InlineData( true, 1)] [InlineData( true, 8)] [InlineData(false, 0)] [InlineData(false, 2)] [InlineData(false, 7)] public void RightIdentity(bool a, int state) { Func<bool, IState<int, string>> f = b => new VowelExpander(b.ToString()); Func<string, IState<int, string>> @return = State.Return<int, string>; IState<int, string> m = f(a); Assert.Equal(m.SelectMany(@return).Run(state), m.Run(state)); }
As always, even a parametrised test constitutes no proof that the law holds. I show the tests to illustrate what the laws look like in 'real' code.
Associativity #
The last monad law is the associativity law that describes how (at least) three functions compose. We're going to need three functions. For the purpose of demonstrating the law, any three pure functions will do. While the following functions are silly and not at all 'realistic', they have the virtue of being as simple as they can be (while still providing a bit of variety). They don't 'mean' anything, so don't worry too much about their behaviour. It is, as far as I can tell, nonsensical. Later articles will show some more realistic examples of the State monad in action.
private sealed class F : IState<DateTime, int> { private readonly string s; public F(string s) { this.s = s; } public Tuple<int, DateTime> Run(DateTime state) { var i = s.Length; var newState = state.AddDays(i); var newValue = i + state.Month; return Tuple.Create(newValue, newState); } } private sealed class G : IState<DateTime, TimeSpan> { private readonly int i; public G(int i) { this.i = i; } public Tuple<TimeSpan, DateTime> Run(DateTime state) { var newState = state.AddYears(i - state.Year); var newValue = TimeSpan.FromMinutes(i); return Tuple.Create(newValue, newState); } } public sealed class H : IState<DateTime, bool> { private readonly TimeSpan duration; public H(TimeSpan duration) { this.duration = duration; } public Tuple<bool, DateTime> Run(DateTime state) { var newState = state - duration; bool newValue = newState.DayOfWeek == DayOfWeek.Saturday || newState.DayOfWeek == DayOfWeek.Sunday; return Tuple.Create(newValue, newState); } }
Armed with these three classes, we can now demonstrate the Associativity law:
[Theory] [InlineData("foo", "2022-03-23")] [InlineData("bar", "2021-12-23T18:05")] [InlineData("baz", "1984-01-06T00:33")] public void Associativity(string a, DateTime state) { Func<string, IState<DateTime, int>> f = s => new F(s); Func<int, IState<DateTime, TimeSpan>> g = i => new G(i); Func<TimeSpan, IState<DateTime, bool>> h = ts => new H(ts); IState<DateTime, int> m = f(a); Assert.Equal( m.SelectMany(g).SelectMany(h).Run(state), m.SelectMany(x => g(x).SelectMany(h)).Run(state)); }
The version of xUnit.net I'm using for these examples (xUnit.net 2.2.0 on .NET Framework 4.6.1 - I may already have hinted that this is an old code base I had lying around) comes with a converter between string and DateTime, which explains why the [InlineData] can supply DateTime values as strings.
Conclusion #
For people coming from an imperative or object-oriented background, it can often be difficult to learn how to think 'functionally'. It took me years before I felt that I was on firm ground, and even so, I'm still learning new techniques today. As an imperative programmer, one often thinks in terms of state mutation.
In Functional Programming, there are often other ways to solve problems than in object-oriented programming, but if you can't think of a way, you can often reach for the fairly blunt hammer than the State monad is. It enables you to implement ostensibly state-based algorithms in a functional way.
This article was abstract, because I wanted to focus on the monad nature itself, rather than on practical applications. Future articles will provide more useful examples.
Next: The Reader monad.
