The State functor by Mark Seemann
Stateful computations as a functor. An example for object-oriented programmers.
This article is an instalment in an article series about functors. In a previous article, you saw how to implement the Maybe functor in C#. In this article, you'll see another functor example: State.
In functional programming, sooner or later a particular question comes up: How do you implement a stateful computation without mutating state?
You use a polymorphic function that takes the current state as input and returns the new state and a result as output. In a C-based language like C#, you can model it as an interface:
public interface IState<S, T> { Tuple<T, S> Run(S state); }
The interface is generic in both the type of state and the type of return value. Notice that the type declaration lists the state type S before the type of the value T, whereas the returned tuple lists T before S. This is quite confusing, but is how Haskell does it. Not ideal, but I've chosen to keep that convention for the benefit of readers who'd like to compare the various implementations.
This article introduces the implementation and machinery of the type. In a later article I'll show an example.
A nonsense example #
You can implement the interface by doing something useful, or, as in the following example, something fatuous like expanding (or contracting) all vowels in a word according to an integer state:
private class VowelExpander : IState<int, string> { private readonly string text; public VowelExpander(string text) { this.text = text; } public Tuple<string, int> Run(int state) { const string vowels = "aeiouy"; var expanded = text.SelectMany(c => vowels.Contains(c) ? Enumerable.Repeat(c, state) : new[] { c }); var newState = state + 1; return Tuple.Create(new string(expanded.ToArray()), newState); } }
This class repeats each vowel in a string by the number indicated by the current state. It also increments the state. Here's a parametrised test that shows how various input produces different outputs:
[Theory] [InlineData("foo", 0, "f")] [InlineData("foo", 1, "foo")] [InlineData("foo", 2, "foooo")] [InlineData("bar", 0, "br")] [InlineData("bar", 1, "bar")] [InlineData("bar", 2, "baar")] public void BasicUsageExample(string txt, int count, string expected) { IState<int, string> s = new VowelExpander(txt); Tuple<string, int> t = s.Run(count); Assert.Equal(Tuple.Create(expected, count + 1), t); }
That's just one, simple stateful computation. It's a silly example, but it's referentially transparent.
Functor #
You can turn the IState interface into a functor by adding an appropriate Select method:
public static IState<S, T1> Select<S, T, T1>( this IState<S, T> source, Func<T, T1> selector) { return new SelectState<S, T, T1>(source, selector); } private class SelectState<S, T, T1> : IState<S, T1> { private IState<S, T> source; private Func<T, T1> selector; public SelectState(IState<S, T> source, Func<T, T1> selector) { this.source = source; this.selector = selector; } public Tuple<T1, S> Run(S state) { Tuple<T, S> tuple = source.Run(state); T1 projection = selector(tuple.Item1); return Tuple.Create(projection, tuple.Item2); } }
A functor maps from one contained type to another, in this case from T to T1, while the state type S remains the same. Notice that it's possible to change the value of the state, but not the type. Even though the State functor has two generic type arguments, it's not a bifunctor. You can pick any type you'd like for S, such as int in the above VowelExpander, but once you've picked a type for the state, you can't project it. It's possible to prove that you can't implement a lawful mapping for the S dimension of State, but if you'd like to understand it intuitively, it's a great exercise to try to implement a function from IState<S, T> to IState<S1, T>. Try it, and you'll soon learn why this is impossible.
Here's an example of using the Select method to project an IState<int, string> to IState<int, int>:
[Fact] public void BasicSelectExample() { IState<int, string> s = new VowelExpander("bar"); IState<int, int> projection = s.Select(x => x.Length); Tuple<int, int> t = projection.Run(2); Assert.Equal(Tuple.Create(4, 3), t); }
As usual, you can also use query syntax:
[Fact] public void QuerySyntaxExample() { IState<int, string> s = new VowelExpander("baz"); IState<int, DayOfWeek> projection = from txt in s select txt.Length % 2 == 0 ? DayOfWeek.Friday : DayOfWeek.Sunday; Tuple<DayOfWeek, int> t = projection.Run(3); Assert.Equal(Tuple.Create(DayOfWeek.Sunday, 4), t); }
This is, once again, a nonsensical function that only exists to show that arbitrary projections are possible.
First functor law #
The Select method obeys the first functor law. As usual, it's proper computer-science work to actually prove this, but you can write some tests to demonstrate the first functor law for the IState<S, T> interface. In this article, you'll see parametrised tests written with xUnit.net. First, the first functor law:
[Theory] [InlineData(DayOfWeek.Monday)] [InlineData(DayOfWeek.Tuesday)] [InlineData(DayOfWeek.Wednesday)] [InlineData(DayOfWeek.Thursday)] [InlineData(DayOfWeek.Friday)] [InlineData(DayOfWeek.Saturday)] [InlineData(DayOfWeek.Sunday)] public void FirstFunctorLaw(DayOfWeek day) { Func<Guid, Guid> id = g => g; IState<DayOfWeek, Guid> s = new DayIdentifier(); Assert.Equal(s.Run(day), s.Select(id).Run(day)); }
This test uses another frivolous IState implementation:
private class DayIdentifier : IState<DayOfWeek, Guid> { public static readonly Guid Monday = new Guid("5AB18569-29C7-4041-9719-5255266B808D"); public static readonly Guid OtherDays = new Guid("00553FC8-82C9-40B2-9FAA-F9ADFFD4EE66"); public Tuple<Guid, DayOfWeek> Run(DayOfWeek state) { if (state == DayOfWeek.Monday) return Tuple.Create(Monday, DayOfWeek.Tuesday); return Tuple.Create(OtherDays, DayOfWeek.Monday); } }
I only chose to write another implementation of IState to show a bit of variation, and to demonstrate that both S and T can be whichever type you need them to be.
The above test cases pass.
Second functor law #
Like the above example, you can also write a parametrised test that demonstrates that IState obeys the second functor law:
[Theory] [InlineData( "foo", 0)] [InlineData( "bar", 1)] [InlineData( "baz", 2)] [InlineData("quux", 3)] public void SecondFunctorLaw(string txt, int i) { Func<string, int> g = x => x.Length; Func<int, bool> f = x => x % 2 == 0; var s = new VowelExpander(txt); Assert.Equal( s.Select(g).Select(f).Run(i), s.Select(x => f(g(x))).Run(i)); }
This test defines two local functions, f and g. Instead of explicitly declaring the functions as
Func variables, this test uses a (relatively) new C# feature called local functions.
You can't easily compare two different functions for equality, so this test defines equality as the functions producing the same result when you Run them.
Again, while the test doesn't prove anything, it demonstrates that for the five test cases, it doesn't matter if you project the state s in one or two steps.
Haskell #
In Haskell, State is available in the mtl package. You can implement the behaviour from VowelExpander like this:
expandVowels :: String -> Int -> (String, Int) expandVowels text s = let vowels = "aeiouy" expanded = text >>= (\c -> if c `elem` vowels then replicate s c else [c]) newState = s + 1 in (expanded, newState)
Instead of defining an interface, you can use any function s -> (a, s), which you can elevate to the State functor using a function called state. You can then use fmap or <$> to map the value:
> runState (length <$> state (expandVowels "bar")) 2 (4,3)
You can see a more useful example of the Haskell State functor in use in the article An example of state-based testing in Haskell.
Conclusion #
A function that takes a state value as input and returns a value and a (potentially new) state value as output is a functor known as State. It can be used as a convenient way to express stateful computations as pure functions.
Next: The Reader functor.
