Higher Kinds in C# with language-ext [Part 11- StateT monad transformer]

This is a multi-part series of articles – and you'll need to know much of what's in the earlier parts to follow along – so it's worth going back to the earlier episodes if you haven't read them already:

• Part 1 - Introduction, traits, semigroups, and monoids
• Part 2 - Functors
• Part 3 - Foldables
• Part 4 - Applicatives
• Part 5 - Validation
• Part 6 - Traversables
• Part 7 - Monads
• Part 8 - Monads (continued)
• Part 9 - Monad Transformers
• Part 10 - ReaderT monad transformer

In the last article we went into quite some depth, covering the ReaderT monad-transformer and the Readable trait (that provides access to an environment value from a structure), meaning we can generalise the idea of monads with environments.

In this article we'll cover a close relative of ReaderT, namely StateT. Where ReaderT provides access to a fixed environment value, StateT allows the mutation of that value.

"Mutation", you say?! Isn't that frowned upon in pure functional programming? Yes, it is, however StateT doesn't mutate a value in-place, it propagates modifications through the pure computation, giving us the best of both worlds.

Because many of the concepts of StateT are similar to ReaderT I'll try to make this article a little more focused on the differences, rather than rehash everything from the last article. By now you should know what traits are, monads, and monad-transformers. We're going to implement another monad-transformer...

You may remember that the core of the ReaderT implementation looks like this:

public record ReaderT<Env, M, A>(Func<Env, K<M, A>> runReader) : K<ReaderT<Env, M>, A>
    where M : Monad<M>, SemiAlternative<M>
{
    public K<M, A> Run(Env env) => 
        this.runReader(env);   

   ...    
}

The runReader function, that is its only property, takes an Env value, which is the environment that gets threaded through the Bind function:

public ReaderT<Env, M, B> Bind<B>(Func<A, ReaderT<Env, M, B>> f) =>
    new(env => M.Bind(runReader(env), x => f(x).runReader(env)));

The reason, for looking at these again, is that with a few changes in these two functions, we will have a state-monad rather than a reader-monad.

It should be fairly obvious from these declarations that the ReaderT can't modify its environment (and return the result). That's because the runReader function doesn't have an Env in its return-type: Func<Env, K<M, A>> – the return-type is K<M, A>, so no changes to Env can be made.

If, instead, we return K<M, (A Value, Env NewEnvironment)>, then we have a way of changing the environment being threaded through the computation. Let's expand it out:

public record StateT<S, M, A>(Func<S, K<M, (A Value, S State)>> runState) : K<StateT<S, M>, A>
    where M : Monad<M>, SemiAlternative<M>
{
    public K<M, (A Value, S State)> Run(S state) =>
        runState(state);

   ...
}

I know I said in the last article I'd talk about SemiAlternative later. Well, that's still the case... until a future article!

So, we've:

• Renamed ReaderT to StateT
• Renamed runReader to runState
• Changed the Env generic argument to S (for 'state')
• Updated the runReader function to return a monad M with a tuple of (A, S) instead of just A.
• Updated the Run function accordingly

We also need to provide an updated Bind function:

public StateT<S, M, B> Bind<B>(Func<A, StateT<S, M, B>> f) =>
    new(state => M.Bind(runState(state), tup => f(tup.Value).runState(tup.State)));

This is where the key difference between the ReaderT and StateT manifests: instead of using the same Env value twice, note how tup.State is passed to the second call to runState.

Let's walk through it:

• A state value is provided by the delegate
• We pass that to this.runState – which is a function that returns K<M, (A, S)>
  • That is, we are returned an M monad with a bound value that is an (A, S) tuple
  • The S in the tuple is the updated state
• Because M is a monad, we can pass the result of the first runState invocation to M.Bind
• In the bind-delegate we get a new value: tup which is the (A, S) tuple
  • This tuple has the updated state in it
• We pass tup.State to the second runState – completing the process of threading the mutated state through the computation.
  • The second runState will also return an updated state

This is how the S state value is returned and threaded through the computations that are chained by the monad-bind operation. Note, from the outside: StateT<S, M, A>, we never see the tuple (except as a result of Run). It's a hidden context that you never have to worry about.

This happens for every single bind operation, so we can mutate the state on every line of a LINQ expression if we wanted to.

But, can't we modify the environment in a ReaderT monad-transformer using with and local? What's special here?

To see the difference here, let's create a real-world example: a simple deck of cards that depletes as we deal them.

First, let's create a type that represents a single playing-card:

/// <summary>
/// Simple card type. Contains an index that can be converted to a textual
/// representation of the card.
/// </summary>
public record Card(int Index)
{
    public string Name =>
        (Index % 13) switch
        {
            0      => "Ace",
            10     => "Jack",
            11     => "Queen",
            12     => "King",
            var ix => $"{ix + 1}"
        };
    
    public string Suit =>
        Index switch
        {
            < 13 => "Hearts",
            < 26 => "Clubs",
            < 39 => "Spades",
            < 52 => "Diamonds",
            _    => throw new NotSupportedException()
        };

    public override string ToString() =>
        $"{Name} of {Suit}";
}

Next, we'll create a Deck of cards with a generate computation that creates a randomly shuffled set of 52 cards:

/// <summary>
/// Deck of cards
/// </summary>
public record Deck(Seq<Card> Cards)
{
    public static Deck Empty = new ([]);
   
    public override string ToString() =>
        Cards.ToFullArrayString();
 
    static IO<Deck> generate =>
        IO.lift(() =>
        {
            var random = new Random((int)DateTime.Now.Ticks);
            var array  = LanguageExt.List.generate(52, ix => new Card(ix)).ToArray();
            random.Shuffle(array);
            return new Deck(array.ToSeqUnsafe());
        });

    ...
}

We wrap that with IO.lift because of the use of the Random type, which is, by definition, not pure – so the IO monad captures the fact that each usage of generate should produce a different result.

We haven't used the StateT transformer yet, so let's start...

public record Deck(Seq<Card> Cards)
{
    ...
    
    public static StateT<Deck, OptionT<IO>, Deck> deck =>
        StateT.get<OptionT<IO>, Deck>();

    public static StateT<Deck, OptionT<IO>, Unit> update(Deck deck) =>
        StateT.put<OptionT<IO>, Deck>(deck);

    public static StateT<Deck, OptionT<IO>, Unit> shuffle =>
        from deck in generate
        from _    in update(deck)
        select unit;

    ...
}

This transformer-stack has more levels than we've used before, we have:

• StateT – for managing the Deck embedded state
• OptionT – to allow us to short-cut an operation and exit
• IO – so we can use the generate function and write to the console

So, we have three monad effects composed into a single type.

NOTE: I know the generics are a little unwieldy. Stick with it, later on we will encapsulate all of them!

The first two computations, deck and update, read and write to the StateT transformer state respectively. We wrap up the StateT.get and StateT.put functions to make them slightly easier to use and more descriptive for this type.

The shuffle computation first generates the deck of cards using the IO generate operation; it then calls update which writes the deck-of-cards state-value into the StateT monad-transformer. The state will be propagated forward automatically. When, we return from the shuffle computation, that Deck state will still be in the StateT monad-transformer.

This is the big difference between ReaderT and StateT: ReaderT can only create locally scoped changes to its environment (that it threads through the monadic computations). Whereas StateT can propagate a changed state outside the scope of the change.

Now that we can read and write the state of the Deck, we can deal some cards!

public record Deck(Seq<Card> Cards)
{
    ...
    
    public static StateT<Deck, OptionT<IO>, Card> deal =>
        from d in deck
        from c in OptionT<IO>.lift(d.Cards.Head)
        from _ in update(new Deck(d.Cards.Tail))
        select c;
        
    ...
}

Let's walk through this:

• We read the Deck state into d from within the StateT transformer
• We then lift into the OptionT transformer d.Cards.Head
  • d.Cards is the Seq<Card> structure that we're dealing from and d.Cards.Head returns an Option<Card>. None if there are no cards left, Some(Card) if there are.
  • So, if the sequence is empty, that means we'd lift None into the transformer, short-cutting the operation and ending the game. If, the sequence has cards remaining, then c will be assigned the first card of the sequence.
• The very next line will only be called if there are some cards in the deck and so we update the deck to remove the first card.
• Finally, we return the Card that was at the head of the list.

Let's add one more computation that allows us to see how many cards are remaining in the deck:

public record Deck(Seq<Card> Cards)
{
    ...

    public static StateT<Deck, OptionT<IO>, int> cardsRemaining =>
        StateT.gets<OptionT<IO>, Deck, int>(d => d.Cards.Count);
        
    ...
}

This uses the StateT.gets function, which is similar to StateT.get in that it accesses the state-value that is being managed by the StateT transformer; but it applies a mapping function before returning. It's good practice to wrap up access to various properties of the internal state like this. It means if we refactor the Deck type in the future, we only need to update those properties.

You could also map from the deck state:

public static StateT<Deck, OptionT<IO>, int> cardsRemaining =>
    deck.Map(d => d.Cards.Count);

They're isomorphic to each other.

With that, we've now used all of the effects of the transformer stack: state-management, optional results, and IO side-effects.

Let's make a game...

Before we make the game, let's make sure we can communicate with the user:

// Simple IO wrappers of System.Console 
public static class Console
{
    public static IO<Unit> writeLine(string line) =>
        lift(() => System.Console.WriteLine(line));

    public static IO<ConsoleKeyInfo> readKey =>
        lift(System.Console.ReadKey);
}

We're wrapping up the side-effecting System.Console into some IO monadic functions. The StateT and OptionT transformers both know how to work with IO monads – so this makes building a simple UI easy.

Onto the game...

public static class Game
{
    public static StateT<Deck, OptionT<IO>, Unit> play =>
        from _0 in Console.writeLine("First let's shuffle the cards (press a key)")
        from _1 in Console.readKey
        from _2 in Deck.shuffle
        from _4 in Console.writeLine("\nShuffle done, let's play...")
        from _5 in Console.writeLine("Dealer is waiting (press a key)")
        from _6 in deal
        select unit;
        
    public static StateT<Deck, OptionT<IO>, Unit> deal =>
        from _0   in Console.readKey
        from card in Deck.deal
        from rem  in Deck.cardsRemaining
        from _1   in Console.writeLine($"\nCard dealt: {card} - {rem} cards remaining (press a key)")
        from _2   in deal
        select unit;
}

Yes, those _1, _2, _3, discards are hella-annoying. For the love of god csharplang team, please give us wildcards in LINQ, like with lambdas! Or, even better, allow us to just write in ... instead of from ... in ... for discards. Each time I write these things I feel like I'm back in 1985 writing BBC BASIC!

OK, OK, it's not the most enthralling of games ever made. Simply shuffle the pack, then keep pressing a key to get the next card until they run out! Amazing!

More seriously, it's worth thinking about what we have here:

• No manual passing of state values as arguments – it's handled magically
• The recursive call to deal within the deal computation should be an infinite-loop. But, it isn't, because we have OptionT in our transformer stack. Meaning None lifted into the computation will exit this loop. This happens when the cards run out.
• We're mixing IO with our logic...
  • This isn't always a good idea (in fact you really should try to keep them separate); but it shows that combining IO (including asynchronous IO) with other complex logic like state-management and optional results is now possible.
  • In the past I would have had to build a bespoke StateOptionAsync type to get these combined behaviours. Now you can build them yourself.

I really want a game!

I wanted to keep this article more concise. But, during the writing of it, I ended up expanding on the card-game idea and made a fully-fledged version of Pontoon (or 21, or Vingt-Un, whatever it's called where you live)!

As mentioned earlier, the generics of 3-deep transformers should be encapsulated in a bespoke type. So, here is Game<A>, which encapsulates StateT<GameState, OptionT<IO>, A>.

The state we're managing, GameState, contains the players, the deck, and a 'current player' – which allows for contextual blocks of code where we are dealing with a single player:

public record GameState(
    HashMap<Player, PlayerState> State, 
    Deck Deck, 
    Option<Player> CurrentPlayer)
{
    public static readonly GameState Zero = new ([], Deck.Empty, None);
}

All of the methods in Game<A> defer to the trait implementations in Game:

• Game implements Monad<Game>, SemiAlternative<Game>, and Stateful<Game, GameState> traits.
• Stateful is the state-equivalent of Readable from the last article – it generalises the idea of reading and writing state for a structure and is equivalent to MonadState in Haskell.
• The trait implementations are simply wrappers around the StateT implementations and so, by now, you should be getting the idea of how to manually encapsulate these transformer types. We don't do anything ourselves, we just pass through to the encapsulated transformer.

By encapsulating the monad-transformer stack into a new type like this, we get much more elegant code. Here's the entry point to the game:

// Play the game!
public static Game<Unit> play =>
    from _0 in Display.askPlayerNames
    from _1 in enterPlayerNames
    from _2 in Display.introduction
    from _3 in Deck.shuffle
    from _4 in playHands
    select unit;

We then keep looping, playing many hands until either the deck runs out of cards, or the users quit:

// Play many hands until the players decide to quit
static Game<Unit> playHands =>
    from _0  in resetPlayers
    from _1  in playHand
    from _2  in Display.askPlayAgain
    from key in Console.readKey
    from _3  in when(key.Key == ConsoleKey.Y, playHands)
    select unit;

A hand starts with two cards being dealt to the players (dealHands), then a loop of sticking or twisting by the users (playRound), followed by a end-of-game winner announcement (gameOver) and deck status:

// Play a single hand
static Game<Unit> playHand =>
    from _1     in dealHands
    from _2     in playRound
    from _3     in gameOver
    from remain in Deck.cardsRemaining
    from _4     in Display.cardsRemaining(remain)
    select unit;

The playRound operation leverages the Prelude.when function that evaluates a monad with a bound bool value, if it's true then the operation passed to it is evaluated too:

static Game<Unit> playRound =>
    when(isGameActive,
         from _ in Players.with(activePlayers, stickOrTwist) 
         from r in playRound
         select r)
        .As();

isGameActive checks various facts (in the GameState) to see if the game is finished (have the players all bust, or stuck, or are at 21, ...). Pontoon is quite complex, because a player can have multiple possible scores if they're holding aces and so this check needs to take that into account.

Players.with evaluates activePlayers which returns the players still in the game and then traverses each player, setting the CurrentPlayer property in the GameState, and then invokes the provided operation stickOrTwist with the current-player context set:

Players.with:

public static Game<Unit> with<A>(GameM<Seq<Player>> playersM, Game<A> ma) =>
    playersM.Bind(ps => with(ps, ma))
            .Map(_ => unit);

public static Game<Unit> with<A>(Seq<Player> players, Game<A> ma) =>
    players.Traverse(p => Player.with(p, ma)).
            Map(_ => unit)
           .As();

Player.with

public static Game<A> with<A>(Player player, Game<A> ma) =>
    Stateful.bracket<Game, GameState, A>(setCurrent(player), ma).As();

Note the use of Stateful.bracket in Player.with. It creates a local state with which to run the ma operation. The state is automatically reset once the ma operation has completed. This is similar to Readable.local.

Then we move on to the per-player querying of whether they want to stick or twist (whether they want a new card or not). We check again if the game is still active as turns by other players may have put the game into a 'game over' state.

static Game<Unit> stickOrTwist =>
    when(isGameActive,
         from player in Player.current
         from _0     in Display.askStickOrTwist(player)
         from _1     in Player.showCards
         from key    in Console.readKey
         from _2     in key.Key switch
                        {
                            ConsoleKey.S => Player.stick,
                            ConsoleKey.T => twist,
                            _            => stickOrTwistBerate
                        }
         select unit)
       .As();

So, we get the current player (which is in the GameState), ask them whether they want to stick or twist, show them their cards, and then wait for them to press S or T on the keyboard. We then either run Player.stick (which updates a flag in the PlayerState within the GameState), or twist, which will deal a new card...

static Game<Unit> twist =>
    from card in Deck.deal
    from _1   in Player.addCard(card)
    from _2   in Display.showCard(card)
    from _3   in when(Player.isBust, Display.bust)
    select unit;

In this short function we update the state of the deck by dealing a new card (Deck.deal), we update the state of the player to register the card they have been dealt (Player.addCard), we do some IO to show the card (Display.showCard), and then we look at the player's state to see if they're bust, and if so, tell them.

Finally, here's the gameOver operation:

static Game<Unit> gameOver =>
    from ws in winners
    from ps in playersState
    from _1 in Display.winners(ws)
    from _2 in Display.playerStates(ps)
    select unit;

We get the state of all of the players and the winner(s), and then display them. Simple! But, behind the scenes there's lots of state-querying going on, yet we don't see that.

What I really like about this approach is how most of the clutter just disappears. It can make the code extremely clear and declarative. It should also be clear why it makes sense to encapsulate the transformer into a new type. If we decide to change the transformer, the game code doesn't need to change, that means we have super-refactoring opportunities. Either for performance or to add new capabilities to the Game<A> monad.

Here's some example output from a game:

Enter a player name, or just press enter complete
Paul
'Paul' added to the game
Adam
'Adam' added to the game
Orla
'Orla' added to the game

Let's play...
Paul [2 of Hearts, Jack of Spades], possible scores [12]
Orla [4 of Diamonds, 10 of Clubs], possible scores [14]
Adam [6 of Spades, 2 of Diamonds], possible scores [8]
Paul, stick or twist? (S/T)
        [2 of Hearts, Jack of Spades], possible scores [12], high-score: 14
t
        8 of Clubs
Orla, stick or twist? (S/T)
        [4 of Diamonds, 10 of Clubs], possible scores [14], high-score: 20
t
        9 of Clubs
        Bust!
Adam, stick or twist? (S/T)
        [6 of Spades, 2 of Diamonds], possible scores [8], high-score: 20
t
        9 of Hearts
Paul, stick or twist? (S/T)
        [2 of Hearts, Jack of Spades, 8 of Clubs], possible scores [20], high-score: 20
s
Adam, stick or twist? (S/T)
        [6 of Spades, 2 of Diamonds, 9 of Hearts], possible scores [17], high-score: 20
t
        Ace of Clubs
Adam, stick or twist? (S/T)
        [6 of Spades, 2 of Diamonds, 9 of Hearts, Ace of Clubs], possible scores [18, 28], high-score: 20
t
        6 of Diamonds
        Bust!
Paul is the winner with 20!
Paul [2 of Hearts, Jack of Spades, 8 of Clubs], possible scores [20] [STICK]
Orla [4 of Diamonds, 10 of Clubs, 9 of Clubs], possible scores [23]
Adam [6 of Spades, 2 of Diamonds, 9 of Hearts, Ace of Clubs, 6 of Diamonds], possible scores [24, 34]
41 cards remaining in the deck
Play again (Y/N)

Note of caution

One note of caution though. Although this leads to quite terse code, the state (other than its type) is a little opaque. We could easily modify some state within one of these functions and the caller wouldn't know. So, the state-monad approach could be problematic application-wide if not managed correctly (they act like global variables to a certain extent).

Asynchrony

One useful side-effect of managing state like this is that if you have an IO monad in your StateT transformer stack (as we have in these examples) then if you call fork to do some parallel processing (or use some of the auto-parallel processing, like Traverse) then, because of the pure nature of these expressions, each fork would get their own branched state that would be managed without effecting each other. So, even though this sometimes feels like global-variables, they are in fact pure expressions and updates are done immutably.

Here's a quick example:

public static class StateForkIO
{
    public static StateT<int, IO, Unit> forkTest =>
        from p1 in showState("parent")
        from f1 in fork(countTo10("fst"))
        from f2 in fork(countTo10("snd"))
        from r1 in f1.Await
        from r2 in f2.Await
        from p2 in showState("parent")
        select unit;

    static StateT<int, IO, Unit> countTo10(string branch) =>
        from _1 in addToState
        from st in showState(branch)
        from _2 in when(st < 10, countTo10(branch))
        select unit;

    static StateT<int, IO, Unit> addToState =>
        StateT.modify<IO, int>(x => x + 1);
    
    static StateT<int, IO, int> showState(string branch) =>
        from s in StateT.get<IO, int>()
        from _ in Console.writeLine($"{branch}: {s}")
        select s;
}

The forkTest operation displays the current-state (an int) and then forks two countTo10 operations. They run independently. The forkTest operation then awaits the completion of those forked operations.

The countTo10 operation keeps looping, adding 1 to its state, until it gets to 10, it then exits. On each iteration it writes its state value to the console.

Once both operations have completed, the forkTest operation writes its state to the console.

If we run it with an initial state of 0:

StateForkIO.forkTest
           .Run(0)
           .Run()
           .Ignore();

Then we get the following output:

parent: 0
fst: 1
snd: 1
fst: 2
snd: 2
fst: 3
fst: 4
snd: 3
snd: 4
fst: 5
snd: 5
fst: 6
snd: 6
fst: 7
snd: 7
fst: 8
snd: 8
fst: 9
snd: 9
fst: 10
snd: 10
parent: 0

So you can see the two countTo10 operations are running in parallel. But it's also clear they have their own local state. They each start at 1 and finish at 10. And the parent thread, that created the two forks, hasn't had its state changed at all.

And, just in case you're thinking that the forks are not inheriting the parent's state. Let's run the forkTest with an initial value of 5:

parent: 5
fst: 6
snd: 6
fst: 7
snd: 7
fst: 8
fst: 9
snd: 8
snd: 9
fst: 10
snd: 10
parent: 5

This stateful thread-safety can be leveraged and depending on the use case could be quite powerful. For example, let's say the card-game wasn't just a simple console app, but was a networked game. We could fork our network communications code, setting the CurrentPlayer state for each fork. So, we'd have multiple current-players all interacting with their own state independently.

If you want to bring stateful changes back to the parent, then you need to bring a result value back via forkedOp.Await and then set it in the parent context. Which is quite a nice synchronisation technique in its own right.

I hope that gives you a bit more insight into how the state isn't really a global variable. It's much more powerful than that. But still, it's always worth considering how you propagate state through an application.

Conclusion

So, my desire for something more concise got out of hand. My bad. But, with the fully worked out Pontoon application, you can dig into how I've made the game-logic terse and elegant. Real-world examples always tend to be a bit more inspiring, I think. Make sure to look at the support functions to see how everything's been encapsulated.

The full game source-code can be found here.

Next up, WriterT, coming soon...