Paul Louth

Higher Kinds in C# with language-ext [Part 12- WriterT monad transformer]

Paul Louth — Sun, 13 Oct 2024 10:29:13 GMT

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:

In the last article we covered the StateT monad-transformer, which is a close relative to the ReaderT monad-transformer from the article before that. The WriterT monad-transformer is implemented in exactly the same way as the StateT monad-transformer. The only difference is that the state type (S in the StateT transformer, renamed to W in the WriterT) is constrained to be a Monoid.

That means we can create an 'empty' W and we can 'append'/'combine' values to W. So, WriterT is good for logging multiple outputs, or aggregating an output value over the course of a monadic expression.

The classic way to implement a Writer monad (not transformer), is like so:

public record Writer(Func<(W Output, A Value)> runWriter)
    where W : Monoid
{
    public Writer Bind(Func> f) =>
        new (() =>
        {
            var (output1, value1) = runWriter();
            var (output2, value2) = f(value1).runWriter();
            return (output1.Combine(output2), value2);
        });
}

This example is not using traits, just so I can show you just the raw components of a Writer monad

The interesting thing here is that the runWriter property doesn't have an input state as part of its Func delegate. It simply combines the outputs of two invocations of runWriter in the Bind method (output1.Combine(output2)).

That allows for a very simple tell function that we use to aggregate our output:

public static class Writer
{
    public static Writer tell(W output)
        where W : Monoid =>
        new (() => (output, unit));
}

We simply return the output value as-is, without doing any extra processing. We can then use that to log individual elements to the monoidal output-state:

static Writer, Unit> example =>
  from _1 in tell(Seq("Hello"))
  from _2 in tell(Seq("World"))
  select unit;

The problem with this approach is that we call tell much less than we call Bind. And in the Bind function we call Monoid.Combine every single time. This is problematic for two reasons:

Most of the time the outputs will be empty, so this is wasted work
When they're not empty, the outputs could need to perform significant work to Combine the two states.
Imagine concatenating two (immutable) linked-lists that are 100 items long each, that would require a 100 item loop to build a new list! You can easily get into a problem of exponential monoidal combines.

So, to get around this, we want to remove the Combine from the Bind function and find another way to aggregate the output. Really, we want the work to happen in the tell function, because that is explicitly doing the work of outputting data.

To achieve this, we must first update the Func<(W Output, A Value)> runWriter to take a W input:

Func runWriter

Then update our Bind function to remove the Monoid.Combine and to pass the initial output0 value through the expression:

public Writer Bind(Func> f) =>
    new (output0 =>
    {
        var (output1, value1) = runWriter(output0);
        var (output2, value2) = f(value1).runWriter(output1);
        return (output2, value2);
    });

The eagle-eyed among you will realise that this is exactly the same as the State monad. It threads a state through the computation, returning the updated value.

Now we can update the tell function:

 public static Writer tell(W value)
      where W : Monoid =>
      new (output => (output.Combine(value), unit));

Most of the time when using Writer our output is a collection of some flavour. And so, this tell function, usually, is just appending or consing a single item to the collection. And so, the risk of exponential concatenation issues goes away (as long as the monoid is implemented efficiently, something to take care with). This is much more efficient, generally.

The thing is, if we look at the implementation of Writer, we can now drop the Monoid constraint:

public record Writer(Func runWriter)
{
    public Writer Bind(Func> f) =>
        new (output0 =>
        {
            var (output1, value1) = runWriter(output0);
            var (output2, value2) = f(value1).runWriter(output1);
            return (output2, value2);
        });
}

We only need it for the tell function. The rest of the implementation is exactly the same as State. So, we don't actually need to implement WriterT. We can simply write a tell function for StateT:

public static StateT tell(W value)
    where W : Monoid
    where M : Monad =>
    StateT.modify(output => output.Combine(value));

Or even, generalise it over all Stateful types:

public static K tell(W value)
    where W : Monoid
    where M : Stateful =>
    Stateful.modify(output => output.Combine(value));

That means anything that implements Stateful can now aggregate an output state using the Monoid trait.

So, why would we ever implement WriterT if StateT is good enough? Well, I've asked myself that question a few times. I've considered dropping the Writer and WriterT types altogether. But, have decided to keep them because they are declarative – they tell the reader of your code that you're aggregating an output, not merely carrying some state. Communication with the reader of your code (including yourself) is important and this seems like a good distinction, even if – at a fundamental level – the types are the same.

What that does mean is that I can keep this episode short and say:

"WriterT is the same as StateT, we just have a Monoid constraint on the state". So, if you grokked the last article, then you're all good.

RWST

Now that we've defined ReaderT, WriterT, and StateT, we can finally implement RWST:

public record RWST(ReaderT>, A> runRWS) 
    : K, A>
    where M : Monad
    where W : Monoid;

Reader, Writer, State, Transformer. This type is a combination of the ReaderT transformer, the WriterT transformer, the StateT transformer, and an M monad. So, four stacked behaviours. It is especially good for defining your 'application monad', i.e. the one that carries configuration, state, and needs to log as it goes, as well as being able to lift an M monad (IO, Option, etc.).

We will cover this in detail in the next article. But if you want some homework, see if you can implement the RWST traits:

public class RWST : 
    MonadT, M>, 
    Readable, R>,
    Writable, W>,
    Stateful, S>
    where M : Monad
    where W : Monoid
{
   // Implementation goes here!
}

Remember that all of the behaviours already exist in the wrapped types, you don't need to implement them yourself, you simply need to lift them into the wrapper-transformer.

Until next time...

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

Paul Louth — Sat, 03 Aug 2024 11:23:32 GMT

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(Func> runReader) : K, A> where M : Monad { public K 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 Bind(Func> 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> – the return-type is K, so no changes to Env can be made.
If, instead, we return K, then we have a way of changing the environment being threaded through the computation. Let's expand it out:
public record StateT(Func> runState) : K, A> where M : Monad { public K Run(S state) => runState(state); ... }
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 Bind(Func> 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
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, 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 Readable.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:
/// /// Simple card type. Contains an index that can be converted to a textual /// representation of the card. /// 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:
/// /// Deck of cards /// public record Deck(Seq Cards) { public static Deck Empty = new ([]); public override string ToString() => Cards.ToFullArrayString(); static IO 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 Cards) { ... public static StateT, Deck> deck => StateT.get, Deck>(); public static StateT, Unit> update(Deck deck) => StateT.put, Deck>(deck); public static StateT, 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 Cards) { ... public static StateT, Card> deal => from d in deck from c in OptionT.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 structure that we're dealing from and d.Cards.Head returns an Option. 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 Cards) { ... public static StateT, int> cardsRemaining => StateT.gets, 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, 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 writeLine(string line) => lift(() => System.Console.WriteLine(line)); public static IO 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, 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, 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!
In many of the language-ext monadic-types we have an overloaded >> operator. Which takes monads ma >> mb and binds them: ma.Bind(_ => mb). What that means is: if you don't care about the result of ma then you can just chain the monadic computations using >>, so we can rewrite play (above) to not use LINQ at all:
public static class Game { public static StateT, Unit> play => Console.writeLine("First let's shuffle the cards (press a key)") >> Console.readKey >> Deck.shuffle >> Console.writeLine("\nShuffle done, let's play...") >> Console.writeLine("Dealer is waiting (press a key)") >> deal; }
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.
You may think that even if we can exit the recursion, we run the risk that someone would play a game so long that we'd get a stack-overflow. However, that can't happen, because the IO monad supports infinite recursion (without building up space leaks from an expanding stack).
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.
What is really interesting about the code above (in my humble opinion) is how minimal and uncluttered this is. We are really getting down to the essence of function rather than having to wade through boilerplate. But we can go even further...
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, which encapsulates StateT, 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 State, Deck Deck, Option CurrentPlayer) { public static readonly GameState Zero = new ([], Deck.Empty, None); }
All of the methods in Game defer to the trait implementations in Game:
public partial class Game : Deriving.MonadIO>>, Deriving.Choice>>, Deriving.Stateful>, GameState> { public static K>, A> Transform(K fa) => fa.As().runGame; public static K CoTransform(K>, A> fa) => new Game(fa.As()); }
Game implements MonadIO, Stateful, and Choice traits leveraging the Deriving automatic trait-implementations that defer to the wrapped transformer.
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.
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 play => Display.askPlayerNames >> enterPlayerNames >> Display.introduction >> Deck.shuffle >> playHands;
Note how we're now using the Game monad that wraps the StateT, A> transformer-stack. Also note, we have encapsulated the Console.writeLine operations into specific Display computations (the thinking here is that you'd want to localise the text, so wrapping up the UI functionality would make sense).
Again, this is now really at the essence of the functionality. We are almost at zero boilerplate.
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 playHands => from _ in initPlayers >> playHand >> Display.askPlayAgain from key in Console.readKey from __ 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 an end-of-game winner announcement (gameOver) and showing of the current deck status:
// Play a single hand static Game playHand => dealHands >> playRound >> gameOver >> Display.cardsRemaining;
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 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 with(GameM> playersM, Game ma) => playersM.Bind(ps => with(ps, ma)) .Map(_ => unit); public static Game with(Seq players, Game ma) => players.Traverse(p => Player.with(p, ma)). Map(_ => unit) .As();
Player.with
public static Gamewith(Player player, Game ma) => Stateful.local(setCurrent(player), ma).As();
Note the use of Stateful.local 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 stickOrTwist => when(isGameActive, from _ in Display.askStickOrTwist >> Player.showCards from key in Console.readKey from __ 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 twist => from card in Deck.deal from _ in Player.addCard(card) >> Display.showCard(card) >> 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 gameOver => from ws in winners from ps in playersState from _ in Display.winners(ws) >> 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 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).
Also, in a real-world application, you'd want to separate the game-logic by partitioning it into pure functions that work over the GameState and keep it away from the IO code (separation of concerns). This interleaving of logic and IO works at this small scale but is problematic for a fully-fledged application. It does however show how we can get down to the essence of the underlying logic.
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 forkIO 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 affecting each other. So, even though this approach sometimes feels like we're using global-variables, the 'stateful expressions' are in fact pure expressions and updates are done immutably.
Here's a quick example:
public static class StateForkIO { public static StateT forkTest => from p1 in showState("parent") from f1 in fork(countTo10("fst")) from f2 in fork(countTo10("snd")) from _ in awaitAll(f1, f2) from p2 in showState("parent") select unit; static StateT countTo10(string branch) => from _1 in addToState from st in showState(branch) from _2 in when(st < 10, countTo10(branch)) select unit; static StateT addToState => StateT.modify(x => x + 1); static StateT showState(string branch) => from s in StateT.get() 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
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 has been encapsulated.
The full game source-code can be found here.
Next up: Part 12, the WriterT monad-transformer

Higher Kinds in C# with language-ext [Part 10- ReaderT monad transformer]

Paul Louth — Wed, 26 Jun 2024 11:40:17 GMT

This is a multi-part series of articles – and you'll need to know much of what's in the earlier parts to follow this – 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
In the last article we started looking into monad transformers. We mostly focused on the MaybeT transformer (OptionT in language-ext), lifting the IO monad into it to create an optional side-effect.
Later in the article I did a quick overview of a project (that I am working on) that creates 'domain monads' by wrapping monad-transformer stacks into new types that are then further composed with free-monads to create a small application architecture.
There is never a 'right way' to structure an application and I think it's risky to use blogs, or other short-form methods to share coding advice on the 'one true way', because it doesn't exist. However, I think when you see how domains, layers, components, and structure in-general, evolves out of compositional types (like monads and monad-transformers) then that light-bulb moment will happen where you can suddenly 'see' the structure of your architecture from 10,000 feet.
These moments of clarity were always missing for me in my former OOP life, whereas with the pure functional programming approach I feel I have total clarity, but also it feels like the architecture is fluid and malleable (it can change with requirements) in a way that just isn't there in the object-oriented world. This may well be a personal thing, so please don't take this as me saying "there's exactly one way to write code" – because all self-appointed internet experts really should be taken with a handful of salt!
Even though the architecture example (from the last article) was a small example, I hope that it whetted your appetite when thinking about how to use pure functional programming techniques to create structure in your programs!
To really benefit the most from this approach we should aim to make our entire code-base pure and getting the architecture right is part of that story. What I find valuable about this approach is that the architecture itself becomes composable. That's quite profound when you think about it and it certainly changes the way I write code now.
It was quite a lot to take in, of course, and I certainly wouldn't expect novice FP devs to get it straight-away. But, one of the biggest issues I've had with building language-ext has been how to put control of building functional types into the hands of the users of the library. Before the higher-kinds approach (demonstrated in this series) there was no way to write code that worked for all monads, or all functors, etc. Now you can.
And before we had monad-transformers there was no way to compose the monads that already existed into new 'super monads', which meant I was stuck writing OptionAsync, EitherAsync, TryOption, and other combination-monads. And you were stuck waiting for me to build various pre-combined monads. This issue no longer exists.
These abstractions now exist. And many of the core types needed for you to build your own functional stacks now exist. The days of waiting for me to build ValidationAsync are over, just use the ValidationT monad transformer stack.
It may take a little while for the implications of the changes in v5 of language-ext to really materialise as opportunities for you. It's a style of programming and an approach to composition that just hasn't existed in C# to-date. So, unless you've come from a Haskell background, this might not seem to be quite as profound as it really is.
C# isn't Haskell of course, but the reason for all of this isn't to make C# into Haskell, it's to make the inertia of the C# developer track in the direction of pure functional programming. And it just so happens that Haskell (as a pure functional programming language) has solved many patterns we need and so the inspiration often comes from that language.
Let's take a look at another monad-transformer...
ReaderT
The ReaderT monad-transformer adds a static environment, Env, to a given monad M. We briefly covered the Reader monad in the Monads Continued article – this generalises the idea into a monad-transformer. So, for example, let's say we had some application configuration in a simple record type:
public record MyConfig(string SourceFolder);
We want to write pure code, so we can't just stick this in a global static variable.
One option is to pass it as an argument to every function that needs the configuration settings:
public static IO readSourceText(string file, MyConfig config) { var path = Path.Combine(config.SourceFolder, file); return IO.liftAsync(e => File.ReadAllTextAsync(path, e.Token)); }
This is perfectly valid, but it can start to get a bit messy and annoying. And, aside from the name of the type, it's not very declarative. If MyConfig had a less descriptive name then it might make the interface to the function more confusing.
Instead, we drop the MyConfig argument and use the ReaderT monad-transformer. We can stack it with the IO monad to get both a static environment and side-effects.
ReaderT will automatically thread the MyConfig value through the computation for us and do so declaratively:
public static ReaderT readSourceText(string file) => from config in ReaderT.ask() let path = Path.Combine(config.SourceFolder, file) from text in IO.liftAsync(e => File.ReadAllTextAsync(path, e.Token)) select text;
Notice how there isn't a MyConfig value passed as an argument to readSourceText. It somehow magics the configuration out of thin air!
The key to this is on the first line in the LINQ expression:
ReaderT.ask()
This static function: ask, somehow gets the MyConfig structure and loads it into the config variable. How can a static function retrieve a non-global state?
If we look at the definition of ReaderT we'll get some clues:
public record ReaderT(Func> runReader) : K, A> where M : Monad { public K Run(Env env) => this.runReader(env); ... }
Internally, ReaderT is a Func>. If we provide an Env then we get a K back (which is constrained to be a Monad).
This follows the transformer pattern. Except this is a little different to MaybeT and OptionT in that K is the inner type, whereas with MaybeT and OptionT it was the outer type: K>.
This difference in implementation is all to do with what is best for the particular transformer. It makes sense to provide an environment for the inner monad to run in. Whereas, for the optional types, it makes sense for the result to be optional! In general, optional types are wrapped by the lifted monad, and stateful-computation types wrap the lifted monad.
When we come to run the ReaderT transformer, we must pass the configuration value to it, so it can be passed through the computation:
// Create the application configuration object. // Typically you would do this once var configObj = new MyConfig("c:\\folder"); // Run the ReaderT. This returns an IO var configTextIO = readSourceText("test.cs").Run(configObj);
The result is an IO. The IO monad being that which was lifted into the transformer.
If we run the IO value then we get the raw text:
var configText = configTextIO.Run();
Reminder: You shouldn't exit the IO monad unless you're at the very edge of your application.
That doesn't explain how ask works from earlier. It somehow magicked the configuration out of thin air. Remember, we're working with a wrapped function here, which means we can defer the gathering of the configuration (make it lazy):
new ReaderT(env => M.Pure(env));
So, we don't need to know the environment to implement ask, we just need to know we will be given it at some point. Here we take the env input and simply lift it into the M monad which exposes it as the bound value. Extremely simple, but also extremely effective.
It can be simplified further to:
new ReaderT(M.Pure);
And even further when it's part of a function that can infer the return type:
public static ReaderT ask() where M : Monad => new (M.Pure);
Everything in ReaderT therefore is lazy. We know the Run method will provide an Env value which we can use to invoke the encapsulated delegate and realise a concrete result. But, every other (non-Run) method on ReaderT must use standard function composition to achieve its behaviours.
For example, the Bind function:
public ReaderT Bind(Func> f) => new(env => M.Bind(runReader(env), x => f(x).runReader(env)));
We create a new Func that provides us with an Env env, we invoke our runReader function with the env value. It gives us the wrapped K which we can M.Bind because it's constrained to be a Monad. That gets us the A value from within the M monad (assigned to x). We pass the A to the f function provided. It returns a new ReaderT which we then invoke (with the same env). It returns a K which is what M.Bind expects as a result!
This is how the environment is threaded through the monad-transformer and how it can be made available for use in the LINQ expression. The env is always available because every ReaderT has it given when invoked.
Readable
So, that's all awesome and everything, but when we use transformers it's often good to wrap up the stack into a new type for encapsulation reasons. The eagle eyed among you may realise that ReaderT is essentially Eff from previous versions of language-ext. The Eff monad was designed to be an IO monad with a 'runtime' that allowed for injectable side-effects.
So, let's wrap it up and create our own simplified Eff monad. First, let's create the Eff type:
public record Eff(ReaderT runEff) : K, A>;
This simply wraps the ReaderT monad transformer.
Next, let's make Eff into a monad by implementing the Monad trait:
public class Eff : Monad> { public static K, B> Bind(K, A> ma, Func, B>> f) => new Eff(ma.As().runEff.Bind(x => f(x).As().runEff)); public static K, B> Map(Func f, K, A> ma) => new Eff(ma.As().runEff.Map(f)); public static K, A> Pure(A value) => new Eff(ReaderT.Pure(value)); public static K, B> Apply(K, Func> mf, K, A> ma) => new Eff(mf.As().runEff.Apply(ma.As().runEff).As()); public static K, A> LiftIO(IO ma) => new Eff(ReaderT.liftIO(ma)); }
Note how every method is just a wrapper around the calls to the ReaderT implementations (runEff is a ReaderT). Also note that we have implemented LiftIO which isn't enforced (there's a default implementation) but this allows us to use IO operations in our LINQ expressions directly (we covered this in the last article).
Next, create our As and Run extensions and add some constructors:
public static class Eff { public static Eff As(this K, A> ma) => (Eff)ma; public static IORun(this K, A> ma, RT runtime) => ma.As().runEff.Run(runtime).As(); public static Eff Pure(A value) => new (ReaderT.Pure(value)); public static Eff Fail(Error error) => new (ReaderT.liftIO(IO.Fail(error))); }
And that's it!
Of course, the real Eff monad comes with lots of helper functions that make working with effects easier. But pretty much everything is just lifting the existing functionality from the transformers into the Eff type. For example, to access the runtime is simply a ReaderT.ask:
public static Eff runtime() => new (ReaderT.ask());
You should be getting the idea now that this is just a wrapper around the transformer stack. We could extend the capabilities by stacking more transformers if necessary.
The real reason I wanted to demonstrate this is because there is another trait-type especially for readers. It's called: Readable and any type that implements it becomes 'readable':
public interface Readable where M : Readable { public static abstract K Asks(Func f); public static virtual K Ask => M.Asks(Prelude.identity); public static abstract K Local( Func f, K ma); }
For those who know Haskell, this is essentially MonadReader without inheriting the Monad constraint!
We can add it to the traits that Eff implements:
public class Eff : Monad>, Readable, RT> { // ... implementations from earlier ... public static K, A> Asks(Func f) => new Eff(ReaderT.Asks(f)); public static K, A> Local(Func f, K, A> ma) => new Eff(ma.As().runEff.Local(f)); }
Readable just abstracts the idea of accessing a static environment away from the monad. It means we can write code that accepts any 'readable' type, whether it's Eff, ReaderT, Reader, or whatever bespoke type we have built.
Readeable also comes with some static functions that makes readable types easy to work with:
public static class Readable { public static K ask() where M : Readable => M.Ask; public static K asks(Func f) where M : Readable => M.Asks(f); public static K asksM(Func> f) where M : Readable, Monad => M.Flatten(M.Asks(f)); public static K local(Func f, K ma) where M : Readable => M.Local(f, ma); }
Let's say our 'runtime' was just an int and we want to write a function that takes two Eff monads with int as their bound-values and then sum those values with the int that's in the runtime (the environment).
public static K, int> addEff(Eff mx, Eff my) => from x in mx from y in my from z in Eff.runtime() select x + y + z;
This works just fine, we can access the runtime value via the Eff.runtime function. However, this function only works with one monadic type: Eff.
We can generalise it even further:
public static K addRdr(K mx, K my) where M : Readable, Monad => from x in mx from y in my from z in Readable.ask() select x + y + z;
Note how M is not only constrained to be a Monad but it is also constrained to be a Readable. So, it's bindable and readable! Let's try running it with some Eff monads:
var compute = addRdr(Eff.Pure(100), Eff.Pure(200)); var result = compute.Run(300).Run(); // 600
addRdr has no idea what monad we're running and it has no idea how we're managing our static environment. It is a complete abstraction away from the internals. The Eff monad supports IO side-effects, parallelism, resource tracking and auto-cleanup, error tracking, retries, repeats, ..., and a static environment. All of which could happen in the addRdr function (because mx and my are computations) – but the implementation doesn't care, it is abstracted away. All it cares about is that the values are bindable and readable!
This is the path to true abstraction – where everything is pure. We can safely abstract, because we know all of the components are playing by the rules!
You may think this kind of abstraction isn't that valuable. But, if you remember the real-world domain-monads example from the previous article – where I created a Db monad, a Service monad, and an Api monad – then it's not a massive stretch to imagine writing some very general support functions that work with all of those monads (using the Monad constraint) and accessing their configuration (using the Readable constraint).
For example, you could imagine a User value being in the environment and a getLoggedInUser function to access it from any monad that supports it:
public record User(string Id); public record Session(User LoggedIn, DateTime LastAccess); public static K getSession() where M : ReaderM => ReaderM.ask(); public static K getLoggedInUser() where M : ReaderM => ReaderM.asks(s => s.LoggedIn);
We could expand that out to embed security roles and rights so we could do inline assertions throughout our code-base:
// Simple User type with list of roles it's a member of public record User(string Id, Seq Memberships); // Union type of rights public abstract record Right; public record CanViewDemographic : Right; public record CanSendInvoice : Right; // Role with its allowed rights public record Role(Seq Rights);
Next we can write the function exactly once to deal with access-rights:
public static K assertHasRight() where R : Right where M : Readable, Functor => getLoggedInUser().Map( u => u.Memberships.Exists( role => role.Rights.Exists( right => right is R)) ? Prelude.unit : throw new SecurityException("Access denied"));
Then at the start of an API call, for example, you could setup the User in a Session environment (pre-populating the rights and roles once per request). That Session can then be passed to the computation that represents the API request (via Run(session)) which will then automatically thread the session, user, and rights through your monadic stack.
The (read-only) user, security rights, and roles will automatically propagate through your code. Each monad that wants to have access to security credentials could just expose them via a Readable trait implementation.
We can then write our security assertions code in any monad that supports them:
public static Eff sendInvoice() => from _ in assertHasRight, CanSendInvoice>() from r in doSendInvoice() select r;
Being able to write security code once and keep it tightly audited is the mark of a professional approach to software development. So these abstractions are not just academic examples of what can be done with pure functional programming, they're very real examples of how you can make your code more robust and more secure. You'll be the auditors best friend – although I'm not sure that's a good thing!
Local environments
Having a fixed static environment for your entire code-base is of course possible, but that will tend to expose more 'environment' than is necessary for any subsystem. And so, it would be good if we could swap out our larger environments for something smaller on-the-fly. This is where ReaderT.local(f, ma) and ReaderT.with(f, ma) comes in:
local maps an Env to an Env – this allows simple mutation of the environment. The ma computation is then run in that locally mutated environment. By the end of the call the environment is reset.
with maps an Env to an alternative type which can be any other value you like, but often it is derived from Env. For example, you may have an AppConfig which contains a DbConfig – it could make sense to only expose the DbConfig to your data-layer by mapping from AppConfig -> DbConfig.
Note that with is not available in the Readable trait and so you must use Reader.with and ReaderT.with to map the environment to a different type (meaning we can't fully generalise the environment mapping). For any type that encapsulates ReaderT or Reader it is worth adding your own equivalent of with to do environment mapping (if that makes sense for your type, some wrappers might have a fixed environment). This is a limitation brought about by how the higher-kinds are implemented (the Env is baked into the trait implementation) – I haven't thought of an easy solution to this yet!
Conclusion
I often show (and will continue to show) the IO monad being the monad that is lifted into the transformer. I'm mostly doing this because it's easier to see tangible examples of what it means to compose monads with transformers. Just remember that any monad can be lifted into ReaderT – it could be a Validation to have an environment for your validators (for example).
One other thing to note is that ReaderT would usually be the outermost type in the transformer stack. This is usually because you want the inner monad(s) in the transformer stack to have access to the environment. This isn't a rule, it's just usually the most effective position.
The ReaderT transformer really is the first 'control' transformer that shows how capabilities can be 'bolted on' to existing monads in a way that starts to break away from the relatively 'small thinking' of optional types and other common FP topics. Being able to carry a – pure – environment through your code really is the first part of building a pure architecture.
In previous versions of language-ext we only have Reader which was just an environment carrying monad – nothing else, it didn't compose with anything and that meant it was probably never used (I certainly never used it). Now we have the ability to augment with readable traits and that is extremely powerful!
Next up will be the StateT transformer. Very much like the ReaderT transformer except the environment can be modified. Pure mutation? You bet!
Part 11 - StateT monad transformer

Higher Kinds in C# with language-ext [Part 9- monad transformers]

Paul Louth — Mon, 27 May 2024 09:34:56 GMT

This is a multi-part series of articles – and you'll need to know much of what's in the earlier parts to follow this – 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)
In the last two episodes we covered monads: the philosophy behind them and some practical examples. However, anyone who's used monads (either the new trait-based monads or the implementations from earlier versions of language-ext) will know that they don't compose with each other. We get 'colouring' of our functions and it's extremely cumbersome to use different colours together.
For example, let's create two functions that return different monadic 'colours':
static IO> readAllLines(string path) => liftIO(env => File.ReadAllLinesAsync(path, env.Token)) .Map(toSeq); static Option validatePath(string path) => Path.IsPathRooted(path) && Path.IsPathFullyQualified(path) ? Some(path) : None;
One function returns the IO monad, which represents side-effects. The other returns an Option – the optional result monad which has a value of None to represent failure.
Ideally, we'd like to validate our path before we try to read the lines from the file it represents. The problem is that we can't combine monads in a single expression:
var computation = from p in validatePath(path) from r in readAllLines(p) select r;
And that's because the the Bind function expects to return the same monad it is chaining from:
K Bind(K ma, Func> f); ^ ^ ^ | | | +------------------+-------------------+
Because, all of the K types have the same M baked in, we are unable to switch monadic types mid-expression. Well, technically we are able to, but not generally – i.e. the trait doesn't allow it, but we could write bespoke implementations for complimentary monads.
We're specifically talking about the generalisation of monads here though and they only compose with themselves, not other monadic types. So, if we take that as a given, what do we do about it?
Well, one technique is to nest the regular monadic types. Instead of working with IO or Option we could work with IO>:
var computation = from op in IO.pure(validatePath(path)) from r in op.Match(Some: readAllLines, None: () => IO.Fail>(Errors.None)) select r;
By lifting the Option returning validatePath into the IO monad we get a IO>, but that just means op is a Option and it all gets very messy, very quickly – we're effectively manually implementing the bind function for Option. It compiles and runs though! So, that hints at a possible approach if we can encapsulate that nested monadic type behaviour.
This is where monad transformers come in!
Monad transformers allow 'stacking' of different monad types into 'super monads' that aggregate all of the features of the stacked elements.
What follows will be quite hard going if you're new to monads or monad transformers. So, I'll give you a sneak preview of where we're going to be at the end of this article. Hopefully you won't lose the will to live halfway through!
By the end of this article you'll be able to compose monads into monad transformer stacks. These compositions aggregate all of the abilities of each monad 'colour' into one type.
The example above – of trying to mix IO and Option – can be achieved (in language-ext) using the OptionT monad transformer stack. It lifts the regular IO monad into the OptionT monad transformer which creates a new monad that is the sum of its parts.
The functions readAllLines and validatePath can stay exactly as they are above. We just need to update the LINQ expression:
var computation = from p in OptionT.lift(validatePath(path)) from r in readAllLines(path) select r; var result = computation.Run(); // Option
The reason readAllLines doesn't need lifting is because it returns the IO monad and the OptionT monad-transformer supports liftIO – which allows any IO computation to be lifted into a monad-transformer stack of any depth as long as it has the IO monad at the bottom of the stack (and because there are special SelectMany extensions for doing this liftIO work).
If you wanted to be completely explicit about it, you could write the readAllLines(path) expression as:
MonadIO.liftIO, Seq>(readAllLines(path))
Obviously there's more overhead to writing that! But, that's what Bind and SelectMany do automatically for you when using IO based monads in a LINQ expression.
What we have just done by using OptionT is recreate OptionAsync (now removed from language-ext) without writing any new code. We could also use OptionT to have a more advanced version with proper error handling, or ValidationT if we wanted IO and validation... this is a very powerful!
OK, hopefully you've seen enough to make you want to read on, so let's take a look at the monad-transformer trait: MonadT
public interface MonadT : Monad where T : MonadT where M : Monad { public static abstract K Lift(K ma); }
Notice the constraints on T and M:
T is constrained to be itself like all traits. Itself is also a Monad
M is constrained to be a Monad
We inherit Monad which means the eventual trait implementation is both a monad-transformer and a monad. This is important when stacking monad-transformers, because a monad-transformer is also just a monad that can be stacked inside other monad-transformers.
So, T is considered the 'outer' monad and M is the 'inner' monad. If C# had first-class support for higher-kinds the type would be: T> – but in our world we're working with the following type: K>
The single function that the trait supports is Lift – for lifting an inner monad into an outer monad transformer.
The important thing to note is that you don't get to make a regular monad into a monad-transformer. You have to write a bespoke monad-transformer type. However, you can create any regular monad from a monad-transformer by lifting the Identity monad into the transformer.
What that means is you can create Reader from ReaderT and Option from OptionT, etc. Practically though, that isn't always how it's done, mostly for performance reasons. But it's good to know that any regular monad can be made by composing its transformer and Identity.
Our next example will go the other way by creating a transformer from its monad.
By convention anything relating to transformers (or nested types) in language-ext has a T suffix. So, if we want to make a transformer version of the Maybe type, from the last article, then we'd create a new type called MaybeT – the transformer provides the standard optional behaviour of Maybe but augments it with the M monad that is lifted into it.
public record MaybeT(K> runMaybeT) : K, A> where M : Monad { // members to come... } public static class MaybeTExtensions { // Standard downcast but with Monad constraint on M public static MaybeT As(this K, A> ma) where M : Monad => (MaybeT)ma; }
This is our starting point for MaybeT. Note how the runMaybeT member is a nested monad. We only know the type of one of the monads, the Maybe – but that's enough – we know how Maybe works, so we can 'see inside' whereas M is opaque and we must rely on only what we know about it: it's a Functor, Applicative, and a Monad. So, we can access its Map, Pure, and Bind functions.
NOTE: The nesting order isn't fixed. Sometimes the 'known' monad is the inner monad and sometimes its the outer monad. So, just be aware that stacking transformers can sometimes be a little bit confusing.
Now, let's start creating the MaybeT trait implementation:
public class MaybeT : MonadT, M>, MonadIO> where M : Monad { // to be filled in !! }
This works the same way to all our other HKT traits, just this time we're working with the MonadT trait. MonadT has its own method (Lift) but it also inherits: Monad, Applicative, and Functor so we have to implement them all!
We are also inheriting MonadIO. MonadIO is a special-case trait that needs some serious explanation, which I'll do a little later. Just for now, make sure you inherit MonadIO on any transformer type you make, unless you very specifically want it to not support composition with IO types.
First, Functor:
public partial class MaybeT : MonadT, M> MonadT, M>, MonadIO> where M : Monad { static K, B> Functor>.Map(Func f, K, A> ma) => new MaybeT( ma.As() .runMaybeT .Map(mx => mx.Map(f).As())); // to be filled in !! }
If you look closely at the implementation you'll notice it has two nested calls to Map. We get the runMaybeT property from the transformer (which is two nested monads), we call Map on it, which makes the inner monad available to us (mx) – we then call Map on mx with the f function to do the actual mapping. The two Map functions will automatically re-wrap the values in their nested monads, leaving us with a K> which we can use to construct a new MaybeT.
You should start to see what we're doing here: we're unwrapping the layers of the two nested containers (M and Maybe) so that we can work on the values contained within.
What's most important here is that we're using Map from M and Map from Maybe, which means we're using their inbuilt behaviours – one of which we know is to give optional results, but the other totally depends on the implementation of M.
Next, Applicative:
static K, A> Applicative>.Pure(A value) => new MaybeT(M.Pure(Maybe.Just(value))); static K, B> Applicative>.Apply(K, Func> mf, K, A> ma) => mf.As().Bind(f => ma.As().Map(f));
Pure is the most interesting implementation. We use the outer monad's Pure function to lift the Maybe into it. This gives us the nested K>.
We're seeing that monad-transformers aren't particularly special when you look inside they're just doing the same work I did in the very first example where I manually matched on the Option so I could use it with the IO monad. The monad-transformer merely encapsulates that messiness. The result will be a new monad that has captured the complexity of working with two nested types and captures the two distinct monad effects.
By the way, I've left the Apply function to a default that uses Bind and Map – there are avenues for more specific applicative behaviour, but not with this type. Why? Because the way the types are nested in a transformer means we can only really run Apply on the inner-types. For example, take a look at a more complete implementation for MaybeT:
new MaybeT(mf.As().runMaybeT.Bind(maybeF => ma.As().runMaybeT.Map(maybeA => maybeF.Apply(maybeA))));
As you can see, we need to run Bind and Map on the outer-types so that we can get access to the inner Maybe values before then calling Apply on them. So, only the inner-types have their applicative behaviour invoked and because the inner-type is a Maybe, which doesn't have any interesting applicative behaviour – like say Validation – we instead use a simpler implementation that only uses Bind and Map.
Now, Monad:
static K, B> Monad>.Bind(K, A> ma, Func, B>> f) => new MaybeT( ma.As().runMaybeT.Bind(mx => mx switch { Just(var x) => f(x).As().runMaybeT, Nothing => M.Pure(Maybe.Nothing()) }));
This is a little bit more complex. The reason for the complexity is that the f argument returns a MaybeT – this is problematic, because it's the outer-outer wrapper and we're unwrapping our monadic types to get at the A value to pass to f. The last thing we need when we're in the middle of the tree rings is to have some bark returned!
This is where our knowledge of the inner Maybe monad comes in useful. Because, not only do we know that it's a monad, but we know we can pattern-match on it and just make it evaporate!
So, we run Bind on the outer monad, it unwraps the inner monad (which is a Maybe), we then pattern-match on the Maybe, if the result is a Just we get the A value and pass it to the bind function: f - which returns a MaybeT. We know that MaybeT has a property which is a K type and that's what the bind function wants in return! If the result is Nothing then we can lift a new Nothing into the M monad using M.Pure – which also satisfies the Bind requirements.
Phew!
You might want to read and re-read that a number of times to really grok what's happening here. But the crux of it is that we're nesting the bind behaviours of each monad: M and Maybe. So, the result is a new type, MaybeT, which has optional behaviour and M behaviour – whatever that is!
We're not done yet. We still need to implement the MonadT interface:
static K, A> MonadT, M>.Lift(K ma) => new MaybeT(ma.Map(Maybe.Just));
That's it! So, although it took a fair amount of work to make the transformer into a valid monad, applicative, and functor; the actual work of making a monad transformer is simply lifting a generic monad type 'into' it.
Lift lets us take a monad M and lift it into the transformer. Because we're using M as the outer monad we need to call Map on it and map the A to a Maybe. This creates the nested type we need.
OK, so that's everything from the MonadT trait implemented. It is usable as-is, but any transformer you implement will always benefit from some convenience functions. The functions will depend entirely on the transformer, just as it does with any other monad.
So, for MaybeT we might add:
public partial class MaybeT { public static MaybeT lift(Maybe ma) => new(M.Pure(ma)); public static MaybeT Just(A value) => lift(Maybe.Just(value)); public static MaybeT Nothing() => lift(Maybe.Nothing()); }
As well as:
public class MaybeT { public static MaybeT lift(K ma) where M : Monad => new (ma.Map(Maybe.Just)); }
Those will give us the ability to lift either an M or a Maybe into the transformer as well as to construct a Just or Nothing state transformer.
Lifting can be done with the generic MonadT.lift(...) function. So, technically you don't need to implement lift functions. But, I find it's often easier to create some bespoke lifting functions as it often requires fewer generic arguments.
Let's go back to our example from the start of this article and rework the readAllLines and validatePath functions:
static MaybeT> readAllLines(string path) => MaybeT.lift( liftIO(async env => await File.ReadAllLinesAsync(path, env.Token)) .Map(toSeq)); static MaybeT validatePath(string path) => Path.IsPathRooted(path) && Path.IsPathFullyQualified(path) ? MaybeT.Just(path) : MaybeT.Nothing();
You can see now that we're returning a common type for both. We have lifted the IO monad into the MaybeT transformer: giving the IO monad optional behaviour.
In readAllLines we're calling MaybeT.lift to lift the IO into the transformer
In validatePath we're using the new MaybeT.Just and MaybeT.Nothing functions.
This gives us a common type that we know will work together in monad-bind expressions. So, we can now use them together in a LINQ expression:
var computation = from p in validatePath(path) from r in readAllLines(path) select r;
The other approach is to leave the functions as they are ...
static IO> readAllLines(string path) => liftIO(async env => await File.ReadAllLinesAsync(path, env.Token)) .Map(toSeq); static Maybe validatePath(string path) => Path.IsPathRooted(path) && Path.IsPathFullyQualified(path) ? Maybe.Just(path) : Maybe.Nothing();
... and lift them ad-hoc:
var computation = from p in MaybeT.lift(validatePath(path)) from r in MaybeT.lift(readAllLines(path)) select r;
IO
Because lifting the IO monad into a transformer-stack is so common there's some special functionality that makes this easy. In Haskell there's a trait called MonadIO that gives the type implementing it a function called liftIO.
There is no transformer version of IO, it is expected that it will always be the innermost monad in any, IO based, transformer stack and therefore can't ever be a transformer itself.
Because, you may have a number of transformers in your stack, calling lift(lift(lift(io))) is an inconvenience. So, liftIO does that work for you. It does this by calling M.LiftIO for the transformed monad M. M may also be a transformer and so it will call its M.LiftIO, etc. this continues until the innermost monad of the transformer stack is reached, which should be an IO monad. To do this we need a new trait called MonadIO that has a LiftIO method.
We can't however create a general MonadIO trait in C#. The problem is that we don't have ad-hoc traits... each higher-kinded type we implement has a single trait-implementation class, which means your type either always supports IO or it never does. So, if you create a transformer type like MaybeT then you either enable liftIO for MaybeT and MaybeT or for none of them. Clearly, in the second example with Identity there isn't an IO monad in the stack, so which option do we pick?
To get around this Monad inherits a 'partial interface', called Maybe.MonadIO:
public static class Maybe { public interface MonadIO where M : MonadIO, Monad { public static virtual K LiftIO(K ma) => M.LiftIO(ma.As()); public static virtual K LiftIO(IO ma) => throw new ExceptionalException(Errors.LiftIONotSupported); public static virtual K> ToIO(K ma) => throw new ExceptionalException(Errors.ToIONotSupported); public static virtual K MapIO(K ma, Func, IO> f) => M.ToIO(ma).Bind(io => M.LiftIO(f(io))); } }
These are the minimum set of methods that are needed to support IO operations and especially the stacking of transformers and monads in such a way that the IO monad is sitting at the innermost stack position. The type is called Maybe.MonadIO to indicate that maybe the IO behaviours have been implemented, but also, maybe not. This isn't ideal, but at least it's clear that it's unsure!
Overriding and implementing LiftIO and ToIO gives IO functionality to your stack. And so, in theory that's all we need to implement.
However, on top of that, we want to be able to mark functions, classes, etc. as constrained to need IO. For example, this shows that the readAllBytes function works with monads that are constrained to support IO:
public static K> readAllBytes(string path) where M : MonadIO => ...;
We can't really do this effectively if all Monad types inherit Maybe.MonadIO. where M : Maybe.MonadIO will be true for all monad or monad-transformers, regardless of whether they implemented LiftIO and ToIO or not.
So, we have a second MonadIO trait, which is not nested inside a Maybe type, that is the real 'this type definitely supports IO' declaration.
The IO type derives from MonadIO, the Eff type derives from MonadIO, as expected, because they both are IO side-effects types. But also, every transformer type inherits MonadIO because they support the 'pass along' process of calling the Maybe.MonadIO behaviours of the type they have lifted (the M in MonadT).
This all sounds crazily complicated, I realise, but it effectively allows for us to create IO implementations and constraints that work generally for monads, but also work optionally for monad-transformers. Just remember that monad-transformers should almost always implement MonadIO – the only reason not to is if you very specifically want to bar IO from a stack (which is rare, but also valid).
Let's now discuss the interface itself:
LiftIO is a function in the Maybe.Monad trait that has a default implementation which throws an exception.
This is the default implementation:
public static virtual K LiftIO(IO ma) => throw new ExceptionalException(Errors.IONotInTransformerStack);
If we implement that for our MaybeT transformer then we'll get liftIO support:
static K, A> Maybe.Monad>.LiftIO(IO ma) => new MaybeT(M.LiftIO(ma.Map(Maybe.Just)));
It takes an IO to lift. First we map the result of the IO to IO>. And then we pass it along to the M monad – which, if it's not the IO monad, will also pass it along... this will continue until it reaches the IO monad in the stack.
The IO monad can then just return the IO because it is the IO monad!
static K Maybe.Monad.LiftIO(IO ma) => ma;
And so, this 'opens up' the stack, injects the IO monad into it and then returns a newly constructed stack. Very cool.
Let's update our earlier example:
static IO writeAllLines(string path, Seq lines) => liftIO(async env => await File.WriteAllLinesAsync(path, lines, env.Token)); static IO> readAllLines(string path) => liftIO(async env => await File.ReadAllLinesAsync(path, env.Token)) .Map(toSeq); static MaybeT validatePath(string path) => Path.IsPathRooted(path) && Path.IsPathFullyQualified(path) ? MaybeT.Just(path) : MaybeT.Nothing();
I've now got two IO functions and one MaybeT function:
We can now write the LINQ expression without manually lifting any of the IO functions:
var computation = from p in validatePath(path) from l in readAllLines(path) from _ in writeAllLines(path, l) select unit;
Which is very elegant.
The reason this works (with different monadic types in the same expression) is because there are bespoke extension-methods for Bind and SelectMany that know how to work with the IO monad:
public static K Bind( this K ma, Func> f) where M : MonadIO => M.Bind(ma, x => M.LiftIO(f(x).As()));
You can see the call to LiftIO that makes the IO into a K (as long as M has implemented LiftIO).
So, the IO monad is the monad that does IO. It might seem obvious, but if you're building anything else that does IO then you want the IO monad internally.
Invoking the transformer
OK, that's all great, how do we run these things?
Ultimately, it depends on the transformer, some of them you'll be able to 'realise' an underlying concrete value, others not. But a good convention is to add a Run extension to extract the underlying monad-stack:
public static K> Run(this K, A> ma) where M : Monad => ma.As().runMaybeT;
In that abstract form it's not that useful, but when it's used concretely then the consumer of the transformer can work with the stack:
var computation = from p in validatePath(path) from l in readAllLines(path) from _ in writeAllLines(path, l) select unit; var result = computation.Run().Run(); // Maybe
So, above, we Run the transformer, we get a K> in return, we then Run that and that gets us a Maybe>. These are now concrete results we can work with.
An important point to note is that because you're manually unwrapping each layer of the transformer stack: you can stop at any point. So, partially unwrapping might make sense depending on the circumstances and what other monadic expressions you're working in.
There must be an easier way?!
Creating new monad transformers is, for sure, quite a bit of effort. But the benefit of using language-ext is that I have written most of the transformers you need. And so, really you only need to compose them yourself.
That doesn't necessarily mean composing them is trivial. In other languages with monad-transformers they're also quite awkward to work with.
Mostly you'll want to wrap your transformer-stack into a new type that hides the stack, but exposes the functionality through a bespoke API. The benefit of taking this approach is that you can change the stack at a later stage without the rest of your code breaking, but also it just reduces the amount of typing of generics.
A good example of this is the Eff type in language-ext. It has been rewritten to use monad-transformers. It stacks the ReaderT transformer with IO:
public record Eff(ReaderT effect) : K, A> { ... }
There's a lot of code in the Eff monad. That's not a requirement of using transformers, it's just a natural artefact of the evolution of the Eff monad from previous versions of language-ext. It is however worth looking at how the Eff type leans heavily on the inbuilt behaviours of ReaderT and IO.
At the time of writing the following monad-transformers are in language-ext:
EitherT
OptionT
TryT
ValidationT
ContT – exists but still WIP
IdentityT
ReaderT
WriterT
StateT
RWST
ProducerT
PipeT
ConsumerT
SinkT
SourceT
ConduitT
By combining these transformers with other monads you can create extremely complex functionality.
Deriving
When we wrap existing monad-transformer stacks in a new type our trait-implementation class ends up being a mechanical wrapping of the lifted transformer type.
So, for example, let's create a simple App monad that wraps a readable/IO monad-transformer stack:
// Simple record for carrying application configuration public record AppConfig; // Application monad that wraps a monad-transformer stack public record App(ReaderT runService) : K;
This encapsulates the IO and configuration passing.
Then we can add our extensions for downcasting and running:
// Extensions for downcasting and running public static class AppExtensions { public static AppAs(this K ma) => (App)ma; public static IO Run(this K ma, AppConfig config) => ma.As().runService.Run(config).As(); }
Now we need the trait-implementations:
// Trait implementation class public class App : MonadIO, Readable { public static K Map(Func f, K ma) => throw new NotImplementedException(); public static K Pure(A value) => throw new NotImplementedException(); public static K Apply(K> mf, K ma) => throw new NotImplementedException(); public static K Bind(K ma, Func> f) => throw new NotImplementedException(); public static K LiftIO(IO ma) => throw new NotImplementedException(); public static K> ToIO(K ma) => throw new NotImplementedException(); public static K Asks(Func f) => throw new NotImplementedException(); public static K Local(Func f, K ma) => throw new NotImplementedException(); }
That's quite a lot for us to fill in, but let's do it ...
// Trait implementation class public class App : MonadIO, Readable { public static K Map(Func f, K ma) => new App(ma.As().runService.Map(f)); public static K Pure(A value) => new App(ReaderT.pure(value)); public static K Apply(K> mf, K ma) => new App(mf.As().runService.Apply(ma.As().runService)); public static K Bind(K ma, Func> f) => new App(new ReaderT(config => ma.As().runService.Bind(a => f(a).Run(config)).Run(config))); public static K LiftIO(IO ma) => new App(ReaderT.liftIO(ma)); public static K> ToIO(K ma) => new App>(ma.As().runService.ToIO().As()); public static K Asks(Func f) => new App(ReaderT.asks(f)); public static K Local(Func f, K ma) => new App(ma.As().runService.Local(f)); }
When you look closely you'll realise that every single implementation just defers to the underlying ReaderT transformer. It's a true wrapper – no bespoke code has been injected.
Although writing these wrappers around monad-transformer stacks isn't difficult, it's boilerplate that we could do without. Luckily we can leverage our new higher-kinded trait skills to automate the wrapping and unwrapping of the inner-transformer.
Introducing Deriving:
So, instead of inheriting the traits and implementing them, we will inherit Deriving. variants of those trait types:
public class App : Deriving.MonadIO>, Deriving.Readable> { public static K, A> Transform(K fa) => fa.As().runService; public static K CoTransform(K, A> fa) => new App(fa.As()); }
The only things we need to implement are Transform (which unwraps the inner-transformer), and CoTransform (that re-wraps it). They're both incredibly efficient and provide default implementations which are passed through to the underlying transformer. You get to use super reliable compositional components to build pure functional power-monads!
You don't even need to know how to implement any of these things, you can just wrap existing monad-transformers that are provided in language-ext, stack them how you like, and then use Deriving.* to build the trait-implementations automatically!
I'll document the Deriving functionality in a later article. Just for know understand that even though it seems like magic, it's all beautifully type-safe and efficient!
Manually implemented transformers removed
Previous versions of language-ext had a number of monadic types that I have since removed:
TryAsync – can now be represented as TryT
TryOption – can now be represented as OptionT
TryOptionAsync – can now be represented as OptionT, A>
OptionAsync – can now be represented as OptionT
EitherAsync – can now be represented as EitherT
I have also had requests for ValidationAsync over the years. It can now be represented as ValidationT. This all puts the control back in the hands of the users of this library and stops me being a blocker to new functionality. It also significantly reduces the code footprint, which is a good thing for my sanity!
Ordering
The exact ordering of monads in the stack is another area where people often get confused. Remember when you Run your stack you're unwrapping each layer one-by-one and depending on the order you may find you've lost the resulting state you're after. Also, certain transformers stack inside-out and some stack outside-in. This can be quite confusing! Just remember than you can always look at the wrapped nested type to get an intuition for how each transformer works.
For example, the ReaderT transformer works by making the lifted monad into the inner-monad (opposite to MaybeT):
ReaderT(Func> runReader)
To a certain extent it takes a bit of trial and error to see what you get when you run the stack, but there's some advice online. Language-ext's monad transformers work exactly the same way as Haskell's, so any online advice for stacking Haskell's transformers will work here too.
Performance
For those of you who are performance-minded you may realise that nesting n monads into a super-monad comes with some overhead. There's plenty of nested lambdas and they're not free. Both from a memory allocations point-of-view, but also just the CPU cost of doing so.
Even though I spent my former life writing high-performance graphics engines for various Playstations, Xboxes, and the like, I firmly believe that large-scale professional application development should focus on correctness first and then performance afterwards. The old adage of don't prematurely optimise is a good one!
The benefit of monad-transformers is that you can build a stack quite quickly without writing any new monad code; once you have your stack you can then wrap it up into a new type that hides the stack. You can rely on its correctness because you're just doing composition. Then go and build your app.
At a later date if performance becomes a problem you can just replace the transformer-stack with a bespoke implementation of the transformer as a single monad (with all the features of the composed transformer).
This allows time for the stack to be updated depending on changes to requirements as your application evolves, but once the implementation has settled down, you can then consider replacing it with something bespoke.
No other code needs to change.
True encapsulation.
Domain Monads
One of the most valuable uses for monad-transformers (especially more complex ones) is in modelling layers/domains in your architecture. There are many approaches to this which will depend entirely on your code-base.
I don't want to get too deep into architecture right now, but I'll provide a couple of examples from my latest startup project (this is early days for the project, so these may change, but it's good enough to demo for now):
I have a type called Db it is the layer that talks directly to FoundationDB:
public record Db(StateT runDB) : K { public IO<(A Value, DbEnv Env)> Run(DbEnv env) => runDB.Run(env).As(); public static Db LiftIO(IO ma) => new (StateT.LiftIO(ma)); public static Db operator |(Db ma, Db mb) => ma.Choose(mb).As(); public Db Map(Func f) => this.Kind().Map(f).As(); public K MapIO(Func, IO> f) => this.Kind().MapIO(f).As(); public Db Bind(Func> f) => this.Kind().Bind(f).As(); public Db SelectMany(Func> bind, Func project) => this.Kind().SelectMany(bind, project).As(); public Db SelectMany(Func> bind, Func project) => this.Kind().SelectMany(bind, project).As(); public static implicit operator Db(Pure ma) => Db.pure(ma.Value).As(); public static implicit operator Db(Fail ma) => Db.fail(ma.Value); public static implicit operator Db(Fail ma) => Db.fail(ma.Value); public static implicit operator Db(Error ma) => Db.fail(ma); }
Things to note are:
It wraps StateT – so it packages up the state generic argument and its IO nature.
You can see lots of methods implemented like this:
this.Kind().XXX.As();
Kind converts to the underlying generic trait K
We then call the trait implementation for XXX.
Then we convert back to Db using As()
This allows us to defer the actual implementation of these functions to the trait-implementation. This concrete surface to the type could easily be generated with source-generators in the future (it's on my list!).
Because we've deferred the responsibility for implementing the methods above to the trait implementation. Let's take a look at it...
public partial class Db : Deriving.Monad>, Deriving.Stateful, DbEnv>, Deriving.Choice>, Fallible, MonadIO { static K, A> Natural>.Transform(K fa) => fa.As().runDB; static K CoNatural>.CoTransform(K, A> fa) => new Db(fa.As()); static K Maybe.MonadIO.LiftIO(IO ma) => new Db (StateT.LiftIO(ma)); static K> Maybe.MonadIO.ToIO(K ma) => dbEnv.Map(e => ma.As().Run(e).Map(r => r.Value)); // NOTE: This ignores the returned state static K Maybe.MonadIO.MapIO(K ma, Func, IO> f) => from e in dbEnv from r in f(ma.As().runDB.Run(e).Map(vs =>vs.Value).As()) // NOTE: This ignores the returned state select r; static K Fallible.Fail(Error error) => new Db(StateT.lift(IO.fail(error))); static K Fallible.Catch(K ma, Func Predicate, Func> Fail) => from e in dbEnv from r in liftIO(ma.As().runDB.Run(e).Catch(Predicate, err => Fail(err).As().Run(e)).As()) from _ in Stateful.put(r.Item2) select r.Value; }
Things to note:
Three uses of Deriving.* so we don't have to manually implement Monad, Stateful, or Choice.
We do implement MonadIO and Fallible, because StateT doesn't support those traits. You can see the compromise in the LiftIO and ToIO methods – StateT can't support those without losing its state. I know that's OK for this use-case but can't be generalised.
Looking at just the traits it's clear to see that this type is: a monad, manages state, handles failure (Fallible), alternatives (Choice or the | operator), and IO.
Once you have your domain-type defined and its traits implemented. You can create the API to your domain...
Comments and some implementation details removed for clarity
public partial class Db { public static Dbpure(A value) => Applicative.pure(value).As(); public static Db fail(string error) => Fallible.error((Error)error).As(); public static Db fail(Error error) => Fallible.error(error).As(); public static readonly Db dbEnv = Stateful.get().As(); internal static Db gets(Func f) => Stateful.gets(f).As(); public static Db put(DbEnv env) => Stateful.put(env).As(); public static Db liftIO(IO ma) => MonadIO.liftIO(ma).As(); internal static Db liftIO(Func f) => dbEnv.Bind(env => IO.lift(envIO => f(env, envIO))).As(); internal static Db liftIO(Func f) => MonadIO.liftIO(IO.lift(f)).As(); internal static Db liftIO(Func> f) => dbEnv.Bind(env => IO.liftAsync(async envIO => await f(env, envIO).ConfigureAwait(false))).As(); internal static Db liftIO(Func> f) => MonadIO.liftIO(IO.liftAsync(async e => await f(e).ConfigureAwait(false))).As(); static Db fdbVersion = liftIO(...).Memo(); public static Db shutdown = liftIO(...); public static readonly Db connect = (from ver in fdbVersion from env in dbEnv from con in liftIO(...) from res in put(env with { Database = Some(con) }) select unit) .Memo(); static readonly Db db = gets(...); static readonly Db transaction = gets(...); static readonly Db readOnlyTransaction = gets(...); public static Db subspace(string leaf, K ma) => subspace(FdbPath.Relative(leaf), ma); public static Db subspace(FdbPath path, K ma) => from t in readOnlyTransaction from r in liftIO(...) select r; public static Db readOnly(FdbPath subspacePath, K ma) => readOnly(subspace(subspacePath, ma)); public static Db readOnly(K ma) => connect.Bind(_ => liftIO(...)); public static Db readWrite(FdbPath subspacePath, K ma) => readWrite(subspace(subspacePath, ma)); public static Db readWrite(K ma) => connect.Bind(_ => liftIO(...)); public static Db get(string name) => liftIO(...); public static Db set(string name, A value) => liftIO(...); public static Db increment32(string name) => liftIO(...); public static Db increment64(string name) => liftIO(...); }
The Db monad then becomes the 'layer' that wraps my database. It manages connections, security, etc. I just need to write code like this:
public static Db generateEmailVerifyId(EmailAddress email) => from vid in Db.liftIO(randomCode) from res in Db.subspace(Subspaces.ValidationEmail, Db.set(vid, email.To())) select VerificationId.From(vid);
In the same project I have a Service monad. Its job is to talk to external services. The idea being is its a protected gateway to the outside world, but also it knows various configuration settings, which enables it to know how to talk to the outside world.
It looks like this:
public record Service(ReaderT runService) : K { ... }
So, this time we're using the ReaderT monad with a fixed environment (which carries the configuration). And it also does IO like the Db monad.
It enables code like this:
public static Service sendVerifyEmail(EmailAddress email, VerificationId verifyId) => from ky in Service.sendGridApiKey from rt in Service.webRoot from r1 in Service.liftIO(...) from r2 in r1.StatusCode == HttpStatusCode.Accepted ? Service.pure(unit) : Service.fail(ServiceError.EmailDeliveryFailed(email)) select r2;
So, that's two domains we've created (database and external services). Could we use them side-by-side?
Well, just to completely blow your mind. I have an Api monad. It is not a transformer monad, it's a Free monad.
I'll cover Free monads properly in a later article, but I'll give you a quick insight into how we can join these two domain-monads together. It's nothing to do with transformers really, but I hope it gives you some food for thought!
First, I have a DSL which is a simple-union:
public abstract record ApiDsl: K; public record ApiFail(Error Error) : ApiDsl; public record ApiDb(Db Action) : ApiDsl; public record ApiService(Service Action) : ApiDsl;
Notice how two of the cases wrap up Db and Service.
Then I make it into a Functor and add some convenience functions for constructing the cases of the DSL.
public class ApiDsl : Functor { static K Functor.Map(Func f, K ma) => ma switch { ApiFail(var error) => new ApiFail(error), ApiDb(var action) => new ApiDb(action.Map(f)), ApiService(var action) => new ApiService(action.Map(f)) }; public static Free fail(Error value) => Free.lift(new ApiFail(value)); public static Free db(Db value) => Free.lift(new ApiDb(value)); public static Free service(Service value) => Free.lift(new ApiService(value)); }
Now I need to create an Api type that wraps the Free monad (similar to how we do with the transformers):
public record Api(Free runApi) : K { public Api Map(Func f) => this.Kind().Map(f).As(); public Api Select(Func f) => this.Kind().Map(f).As(); public Api Bind(Func> f) => this.Kind().Bind(f).As(); public Api SelectMany(Func> bind, Func project) => this.Kind().SelectMany(bind, project).As(); public Api SelectMany(Func> bind, Func project) => this.Kind().SelectMany(bind, project).As(); public static implicit operator Api(Pure ma) => Api.pure(ma.Value).As(); public static implicit operator Api(Fail ma) => Api.fail(ma.Value); public static implicit operator Api(Fail ma) => Api.fail(ma.Value); public static implicit operator Api(Error ma) => Api.fail(ma); }
Then we create the trait implementation:
public partial class Api : Deriving.Choice>, Deriving.MonadIO> { static K, A> Natural>.Transform(K fa) => fa.As().runApi; static K CoNatural>.CoTransform(K, A> fa) => new Api(fa.As()); }
Just like with the transformers, we're just deferring to the underlying type that we're wrapping. In this case the Free monad.
Now we need a friendly API to our Api monad:
public partial class Api { public static Apipure(A value) => new (Free.pure(value)); public static Api fail(Error value) => new (ApiDsl.fail(value)); public static Api fail(string value) => new (ApiDsl.fail((Error)value)); public static Api lift(Db ma) => new (ApiDsl.db(ma)); public static Api readOnly(Db ma) => new (ApiDsl.db(Db.readOnly(ma))); public static Api readOnly(FdbPath subSpacePath, Db ma) => new (ApiDsl.db(Db.readOnly(subSpacePath, ma))); public static Api readWrite(Db ma) => new (ApiDsl.db(Db.readWrite(ma))); public static Api readWrite(FdbPath subSpacePath, Db ma) => new (ApiDsl.db(Db.readWrite(subSpacePath, ma))); public static Api lift(Service ma) => new (ApiDsl.service(ma)); }
These functions make it easy to construct an API monad in whatever DSL state we like. Notice how we lift both the Db and the Service into the Api monad.
Now we can write code:
public static Api register(EmailAddress email, PhoneNumber phone, Password password) => from id in Api.readWrite(from _ in Credential.createUser(email, phone, password) from t in Verification.generateEmailVerifyId(email) select t) from _ in Api.lift(Email.sendVerifyEmail(email, id)) select unit;
We have two blocks:
One which is the Db that interacts with the database
One which is the Service that interacts with third-party services
These are both lifted into the Api monad (via readWrite and lift). Notice how we automatically segregate our transactional DB code from our service-action code. This encourages us to write performant code without even trying!
What about running this? If you understand anything about Free monads, then you'll know they need an interpreter. So, let's write that:
public IORun(DbEnv dbEnv, ServiceEnv serviceEnv) => Interpret(dbEnv, serviceEnv, runApi); static IO Interpret(DbEnv dbEnv, ServiceEnv serviceEnv, Free fma) { return go(fma); IO go(Free ma) => ma switch { Pure(var value) => IO.pure(value), Bind(var bind) => bind switch { ApiFail> (var e) => IO.Fail(e), ApiDb> (var db) => db.Map(go) .Run(dbEnv) .Map(x => x.Value) .Flatten(), ApiService> (var service) => service.Map(go) .Run(serviceEnv) .Flatten(), _ => throw new NotSupportedException() } }; }
It's not particularly pretty, but it is just a recursive pattern-match operation.
Things to note are:
The Pure and Bind cases are from the Free monad itself.
Think: Pure means "we're done" and Bind means "continue"
The cases of the ApiDsl actually run the Db and Service monads.
They also feed in the external state or configuration (which is passed to the Interpret method),
Because they both have IO monads in their transformer stack, we can unwrap the stack to that level and then return it from the interpreter as its base monad. Meaning the Api monad is an IO monad also!
Hopefully you can imagine a web-request or an event of some sort calling the register function from earlier:
var action = Registration.register(email, phone, pass);
And then running it with the database-environment, configuration, and an IO environment (which enables cancellation and the like):
var result = action.Run(dbEnv, serviceEnv) .Run(envIO);
And so, what we've done here is compose various built-in monads and monad-transformers from language-ext (ReaderT, StateT, IO), wrapped them up into domain-specific monads: Db and Service and then lifted those into another domain-monad that is implemented using the Free monad: Api to give us a surface that manages:
IO
State
Configuration
Security
Transaction management
Resource tracking
And, segregation of operations that shouldn't mix!
The resulting domain-monads don't expose their underlying form until they are run. We try to hide the monad-transformer stacks and the states of the free-monad so that if we need to change it at a later date it is easy. It also means if I ever want more performance I can just go in and manually write those monads.
It should be noted that these techniques aren't slow. They're just slower than hand-crafted solutions. The chances are they're plenty fast enough for 99% of use-cases, so don't get too caught up on the idea that you have to go in and optimise early. As always: profile your code!
Conclusion
It may seem like this is one of the most convoluted ways to compose functionality going. And yeah, there's a bit of typing overhead here. But really, we build these domain monads a handful of times for a project, this isn't a daily job of creating new monad-transformer stacks. Personally, I think it's well worth building domain-monads and I think it's well worth leveraging the existing transformers to create your domain-monads.
Build your stack based on the features you need. Then box it to make it easy to use and consume. The API surface you build for your transformer stack is the the feature. The monad and transformer bit just makes the basics work, so don't forget to make a good domain API surface to get the most out of this approach!
In the next article we'll cover some more monad-transformers and more techniques to make working with transformers even more powerful.

Higher Kinds in C# with language-ext [Part 8- monads continued]

Paul Louth — Tue, 07 May 2024 17:59:04 GMT

This is a multi-part series of articles – and you'll need to know much of what's in the earlier parts to follow this – 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
In the last episode we finally defined the Monad trait and learned the reason for monads:
Enables pure functional programmers to sequence operations
The operations have a particular 'flavour' which defines what happens between the operations (Bind)
Encapsulates messy impure side-effects and effects
Results in a singular pure expression
But what are effects and side-effects? This is something that I think even seasoned pure-FP programmers aren't always clear on. Side-effects are fairly obvious: anything that changes the state of the world (writes to a file, adds a row to a database, changes a global variable, etc.) – but what about 'effects'?
When we have a pure and total function, you could imagine that the internals of it could be swapped for a switch expression. For example, let's make an IsEven function:
bool IsEven(int x) => (x & 1) == 0;
Instead of using the bitwise AND operation, let's swap it for a switch:
bool IsEven(int x) => x switch { 0 => true, 1 => false, 2 => true, 3 => false, ... };
Clearly, it would be a huge function! But that's the way to think about pure functions. They are a mapping from the input arguments to the output. They are also a 'zero time' operation. I don't mean they take zero processor cycles to complete, I mean by having zero impact on the outside world (no event happened) we can consider the transformation to have been instant.
Whereas non-pure functions change the world and so we have cause and effect (time) – this turns out to be a remarkably profound observation if you think about it – especially when considering software complexity.
In some circumstances a switch expression wouldn't be able to cover all of the possible input states. So, we augment the output by using data-types like Option, Either, Fin, Validation, etc. But the act of adding an extra value (None, Left, Fail, etc.) to the co-domain doesn't instantly make an effect – it's the behaviour change that comes as a result of the additional elements in the co-domain that is the effect. For example, when we sequence multiple Option returning computations, the effect is to exit early when we return None.
So, monads capture side-effects and effects ('side-effects' being a subset of 'effects'). The nature of the effect is the bespoke behaviour of the monad.
Effects are still 'felt' for applicatives and functors too. The Map function won't be invoked if the Option is in a None state for example. So, all of these higher-kinded abstractions get involved in the 'effectfulness'.
Flatten
Another part of the Monad trait is Flatten which is also known as 'monad join' in other ecosystems. There's a default implementation, so you never need to write it yourself, but it's worth understanding that there are two ways to implement a monad (Gah! Not another Yet Another Monad Tutorial, please!)
Let's look at the method-signature for Flatten:
K Flatten(K> mma)
Flatten takes a nested monad (like Option> or IO>) and 'flattens' it so it's not nested any more. To do this it must compute the outer monad to get to the inner monad. The behaviour is kinda similar to Bind without the mapping part.
So, if you override Flatten in your monad implementation, then the simplest way to implement it is in terms of Bind and the identity function:
public static K Flatten(K> mma) => mma.Bind(identity);
That's why we can easily provide a default implementation!
However, we could implement it without referencing Bind. Here's an example of implementing Flatten for Maybe:
public static K Flatten(K> mma) => mma switch { Just> (var ma) => ma, Nothing> => new Nothing() };
We pattern-match the outer-Maybe, if it's in a Just state, then the value inside will be what we need to return. If it's in a Nothing state then we just create a new Nothing.
Why's that important? Well we can now implement Bind in terms of Flatten and Map:
public static K Bind(K ma, Func> f) => ma.Map(f).Flatten();
This is why Bind is sometimes also called FlatMap.
Again, so what? Why do we care? Really, you don't need to care, it's purely down to which implementation is easiest or most efficient. So, you either implement Bind in terms of Flatten and Map, or you implement Flatten in terms of Bind (the default). Or, you could have bespoke implementations for both! Just remember when implementing your own monads that there are two distinct routes to implementing a monad – one route may be better than the other.
Flavours
I'm going to spend the rest of this article showing implementations of monads for the various types that are in language-ext (other than the compound monads, like Eff).
These will just be the raw monads/applicatives/functors, none of the support functions ( which are the 'API' of a data-type with a monad trait). The code below is enough for you to use these monads and leverage the built-in functionality of language-ext (functionality that targets traits like Monad, for example), but you'll realise – once you start building monads yourself – it's the supplementary support functions that leverage the monad that are the key.
The reason I highlight this is, up until now, users of language-ext have taken monads 'off the shelf' (like Option, Eff, etc.) – but now you're able to build your own. It's important to understand that you can build your own monads just like you would classes in OOP. They're no more special than any other type you might build that has bespoke functionality. The main difference is that they're cross-cutting computations, if 'inheritance' is top-down, then monads are slice-thru!
To give you a quick insight into what I mean, I am currently dog-fooding v5 language-ext with a new project I am building. Below are some of (not all!) the bespoke monads in the project:
Db – which manages interaction with FoundationDB. It manages state (sub-spaces, connections, etc.), security, and does IO.
Service – which are for access to 3rd party services, like SendGrid. It tracks resources, security, handles configuration, and does IO.
Api – which is a Free monad (I'll discuss in a later article) that wraps up interaction with the various subsystems, tracks resource usage, and provides configuration.
etc.
When people talk about 'layers' in classic software architecture, you can create layer-monads or, more broadly: domain-monads, that enforce anything you want – it could be security, resource management, logging, whatever!
With (the monads below) I won't provide too much running commentary. After the last article, which was very much about the philosophy, I want to instead present some actual implementations. You should just examine the Bind function for each type to see what each monad does differently (or often how similar they are to each other!).
Maybe
Effect: Early termination of computation when in a None state.
// Maybe data-type (same functionality as Option) public abstract record Maybe: K; public record Just(A Value) : Maybe; public record Nothing : Maybe; // Maybe trait implementation public class Maybe : Monad { public static K Bind(K ma, Func> f) => ma switch { Just (var x) => f(x), Nothing => new Nothing() }; public static K Map(Func f, K ma) => ma.Bind(x => Pure(f(x))); public static K Pure(A value) => new Just(value); public static K Apply(K> mf, K ma) => mf.Bind(ma.Map); }
Either
Effect: Early termination of computation when in a Left state. Left carries a 'failure' value.
// Either data-type public abstract record Either : K, R>; public record Right(R Value) : Either; public record Left(L Value) : Either; // Either trait implementation public class Either : Monad> { public static K, B> Bind(K, A> ma, Func, B>> f) => ma switch { Right(var r) => f(r), Left (var x) => new Left(x) // carries the error through }; public static K, B> Map(Func f, K, A> ma) => ma.Bind(x => Pure(f(x))); public static K, R> Pure(R value) => new Right(value); public static K, B> Apply(K, Func> mf, K, A> ma) => mf.Bind(ma.Map); }
Fin
Effect: Exactly the same as Either
This bakes in the Error type to capture the most common result of any C# function: either an error or a result. Those who used Result in v4 should be using Fin ('fin' being French for final/finished – synonym for 'result'). This is easier to use than Either as it doesn't require the application of two generic arguments.
// Fin data-type (same functionality as Either) public abstract record Fin: K; public record Succ(A Value) : Fin; public record Fail(Error Value) : Fin; // Fin traits public class Fin : Monad { public static K Bind(K ma, Func> f) => ma switch { Succ (var x) => f(x), Fail (var e)=> new Fail(e) }; public static K Map(Func f, K ma) => ma.Bind(x => Pure(f(x))); public static K Pure(A value) => new Succ(value); public static K Apply(K> mf, K ma) => mf.Bind(ma.Map); }
Validation
Effect: Early termination of computation when in a Fail state and multiple fail-value aggregation when using applicative Apply.
The main difference between Either and Validation is that F is constrained to be a monoid and that allows us to collect the errors in Apply (see the previous article on validation):
// Validation data-type public abstract record Validation : K, A> where F : Monoid; public record Succ(A Value) : Validation where F : Monoid; public record Fail(F Value) : Validation where F : Monoid; // Validation trait implementation public class Validation : Monad> where F : Monoid { public static K, B> Bind(K, A> ma, Func, B>> f) => ma switch { Succ(var r) => f(r), Fail (var x) => new Fail(x) // carries the error through }; public static K, B> Map(Func f, K, A> ma) => ma.Bind(x => Pure(f(x))); public static K, R> Pure(R value) => new Succ(value); public static K, B> Apply(K, Func> mf, K, A> ma) => (mf, ma) switch { (Succ> (var f), Succ (var a)) => new Succ(f(a)), (Fail> (var e1), Fail (var e2)) => new Fail(e1 + e2), // aggregates errors (Fail> (var e), _) => new Fail(e), (_, Fail (var e)) => new Fail(e), }; }
Try
Effect: Early termination on an exception. Catches exceptions and turns them into a data-type that is part of the co-domain. Purifying the exception machinery!
// Try data-type public record Try(Func runTry) : K; // Try extensions public static class TryExtensions { public static Try As(this K ma) => (Try)ma; // Run without catching the exception public static A RunUnsafe(this K ma) => ma.As().runTry(); // Run and catch the exception public static Fin Run(this K ma) { try { return new Succ(ma.As().runTry()); } catch (Exception e) { return new Fail(e); } } } // Try traits public class Try : Monad { public static K Bind(K ma, Func> f) => new Try(() => f(ma.RunUnsafe()).RunUnsafe()); public static K Map(Func f, K ma) => ma.Bind(x => Pure(f(x))); public static K Pure(A value) => new Try(() => value); public static K Apply(K> mf, K ma) => mf.Bind(ma.Map); }
Iterable
Effect: Iterate multiple items. Early termination if there the collection yields no values.
This is the first collection type that we've implemented as a monad. It's worth looking at how the Bind function is just nested foreach loops – which means its equivalent of the Option early-out mechanism would be to bind with an empty collection. Indeed we can imagine Option being a 'collection' of 0 or 1 items.
Iterable is a new data-type in language-ext that is a wrapper for IEnumerable – it's everything that IEnumerable is but with traits.
// Iterable data-type public record Iterable(IEnumerable Items) : K, IEnumerable { public IEnumerator GetEnumerator() => Items.GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => Items.GetEnumerator(); } // Iterable extensions public static class IterableExtensions { public static Iterable As(this K ma) => (EnumerableM)ma; } // Iterable trait implementation public class EnumerableM : Monad { public static K Bind(K ma, Func> f) { return new Iterable(Go()); IEnumerable Go() { foreach (var x in ma.As()) { foreach (var y in f(x).As()) { yield return y; } } } } public static K Map(Func f, K ma) { return new Iterable(Go()); IEnumerable Go() { foreach (var x in ma.As()) { yield return f(x); } } } public static K Pure(A value) => new Iterable([value]); public static K Apply(K> mf, K ma) => mf.Bind(ma.Map); }
Reader
Effect: Carries an 'environment' through the computation that can be accessed at any time without having to explicitly augment every function with an Env environment argument.
This is very similar to the IO monad from the last article. It wraps up a Func making it lazy. When invoked with an Env it runs the computation threading the environment through.
// Reader data-type public record Reader(Func runReader) : K, A>; // Reader extensions public static class ReaderExtensions { public static Reader As(this K, A> ma) => (Reader)ma; public static A Run(this K, A> ma, Env env) => ma.As().runReader(env); } // Reader trait implementations public class Reader : Monad> { public static K, B> Bind(K, A> ma, Func, B>> f) => new Reader(env => f(ma.Run(env)).Run(env)); public static K, B> Map(Func f, K, A> ma) => new Reader(env => f(ma.Run(env))); public static K, A> Pure(A value) => new Reader(_ => value); public static K, B> Apply(K, Func> mf, K, A> ma) => mf.Bind(ma.Map); } // Reader module public static class Reader { // Gets the environment out of the Reader and maps it public static Reader asks(Func f) => new (f); // Gets the environment out of the Reader public static Reader ask() => asks(identity); }
Writer
Effect: Produces an output log alongside the monad result value (aka the bound value).
This implementation takes an input argument (like Reader) and produces an additional output value (the log). There's an alternative approach to implementing this that doesn't need the input argument, but it's usually less efficient due to the need to concatenate collections in the Bind function – this approach only needs to concatenate in the tell function (which is just appending a single item).
Again note, this requires Out to be a monoid – it means we can create an Empty log and use the + operator to append new output values.
// Writer data-type public record Writer(Func runWriter) : K, A> where Out : Monoid; // Writer extensions public static class WriterExtensions { public static Writer As(this K, A> ma) where Out : Monoid => (Writer)ma; public static (A Value, Out Output) Run(this K, A> ma) where Out : Monoid => ma.Run(Out.Empty); public static (A Value, Out Output) Run(this K, A> ma, Out output) where Out : Monoid => ma.As().runWriter(output); } // Writer trait implementations public class Writer : Monad> where Out : Monoid { public static K, B> Bind(K, A> ma, Func, B>> f) => new Writer(log => { var (value, log1) = ma.Run(log); // threads the log through return f(value).Run(log1); // runs with the updated log }); public static K, B> Map(Func f, K, A> ma) => ma.Bind(x => Pure(f(x))); public static K, A> Pure(A value) => new Writer(log => (value, log)); public static K, B> Apply(K, Func> mf, K, A> ma) => mf.Bind(ma.Map); } // Writer module public static class Writer { // Writes a value to the output public static Writer tell(Out item) where Out : Monoid => new (log => (default, log + item)); }
State
Effect: Threads a state-value through the computation. It's a little bit like the Reader monad except the state isn't read-only: it can be updated. Again, it removes the need to provide and additional S state argument and a tuple (S, ...) return value for every function that manages state.
Note how the Bind function is almost a carbon copy of the Bind function for Writer. In fact they're basically the same monad, just Writer has constraints where its state must be a monoid and has the tell function which knows how to append items – but they're basically the same type.
// State data-type public record State(Func runState) : K, A>; // State extensions public static class StateExtensions { public static State As(this K, A> ma) => (State)ma; public static (A Value, S State) Run(this K, A> ma, S state) => ma.As().runState(state); } // State trait implementations public class State : Monad> { public static K, B> Bind(K, A> ma, Func, B>> f) => new State(state => { var (value, state1) = ma.Run(state); // threads the state through return f(value).Run(state1); // runs with the updated state }); public static K, B> Map(Func f, K, A> ma) => ma.Bind(x => Pure(f(x))); public static K, A> Pure(A value) => new State(state => (value, state)); public static K, B> Apply(K, Func> mf, K, A> ma) => mf.Bind(ma.Map); } // State module public static class State { // Gets the state value and maps it public static State gets(Func f) => new (state => (f(state), state)); // Gets the state value public static State get() => gets(identity); // Updates the monad's state value public static State put(S value) => new (state => (default, state)); }
~~Recap~~
~~That's a lot of the core capabilities of language-ext in a single article!~~
~~We've seen so far:~~
~~Alternative value monads:~~Maybe (equivalent of Option) – that has an alternative value of None
Either – that has a bespoke alternative value: L
Fin – equivalent to Either
Validation – that has a bespoke monoidal alternative value F that collects multiple alternative results
Try - has an alternative value of Error which is used to catch exceptions and make them declarative.
Collection monads
Iterable – works with many values
Others not included as they're all implemented in a very similar way
State and environment monads
Reader – threads an environment value (often configuration) through the computation. This is also a good way to do dependency injection with pure FP (either attach an interface to the environment or have member Func properties).
Writer – threads a monoidal output log through the computation.
State – threads a state value through the computation and allows it to be updated, giving state mutation-like capabilities (in a pure way).
Side effect monads
IO – for managing world changing side-effects (previous article)
Eff – not included as it requires a bit more explanation (next article)
~~Some other monads we didn't cover here:~~
~~Free – which allows for any functor to be turned into a monad for free.~~
~~Cont – continuations~~
~~Identity – manages no effects at all!~~
~~Other collections like: Seq, Arr, Lst, Set, HashSet~~
~~We'll cover those in a later article because they're either too hard to cover quickly (Free monad) or really need some context from what's coming in the next article.~~
~~Composition~~
Hopefully it should be fairly clear that these things are not super hard to make. Sure, if you're new to this, it might still be turning your head inside out a little, but the actual quantity of code you need to write to make these work is pretty minimal.
Remember: All of the types above will work with LINQ straightaway – there's no additional support code needed.
~~The single biggest issue is that these monads are all single-feature monads. What if you want to combine optional-behaviour (Option) and side-effects (IO)?~~
~~You can't.~~
A monadic expression can only work with one type at a time (you can't combine IO and Option in a single expression, for example) and that's a serious limitation. So serious in fact that in previous versions of language-ext I had the following (now removed) monads:
~~OptionAsync – Option and IO~~
~~EitherAsync – Either and IO~~
~~TryAsync – Try and IO~~
~~TryOption – Try and Option~~
~~TryOptionAsync – Try, Option, and IO.~~
~~These were all manually written compositions of the other monadic types. But, as we create more types, the combinations explode. What if you want to combine the capabilities of 3 or 4 monads?!~~
Luckily, in v5 of language-ext we have a solution to that, Monad Transformers. They allow us to compose existing monads into super-monads!!!
~~Part 9 Monad Transformers...~~

Are higher-kinds in C# real?

Paul Louth — Mon, 29 Apr 2024 10:49:40 GMT

In a recent Twitter semi flame-war I encountered some opposition to the idea that the approach to higher-kinds used in language-ext is a valid approach. In the end I decided to back out of it, because nothing is solved on Twitter, but I felt I needed to add enough context so those who follow me on Twitter can at least judge for themselves.
In this article I want to prove that f a in Haskell is equal (up to isomorphism) with K in C#.
To do this we need to build our own type system. It needs to follow the extended lambda calculus approach used by the likes of Haskell and other FP languages. Then, we need to augment it, so that we can represent generic-types the way that C# does it. If we can transform Haskell style higher-rank polymorphic representations to C# generics and back again (without losing any fidelity), we have a proof.
To make a simple type system we need:
Primitive types (int, string, etc.)
Type variables (like the A in Option)
Type names (like the Option in Option)
Lambda abstractions
Type applications
The last two items need a little explanation...
Lambda abstractions are like lambdas in any programming language except they're in the type system and are 'run' at compile time. The 'running' of the lambdas should (by the end of the compilation) generate concrete types. Lambda abstractions follow lambda calculus in that they accept single arguments only. Multiple arguments are achieved by nesting multiple lambdas.
Type applications are what's used to invoke the lambda abstractions (passing an argument to evaluate). They can apply a single argument to a single lambda. So applying multiple arguments to nested lambdas needs multiple type applications. This also means you can partially apply arguments. By example: Option is applying the int type to the Option lambda-abstraction.
First, we need a base type: Ty:
public abstract record Ty;
Then a primitive type to define all the supported primitives:
public enum Prim { Int, String, Bool } public record TyPrim(Prim Value) : Ty;
Type variables:
public record TyVar(string Name) : Ty;
Type names for concrete types:
public record TyName(string Name) : Ty;
Lambda abstractions:
public record TyLambda(string VarName, Ty Body) : Ty;
You should recognise the pattern from lambdas in languages that support them: a letter defining the variable-name of the argument and a body-expression. The idea is that when an argument is applied to the lambda the instances of TyVar(VarName) in Body are replaced with the applied type.
Type application:
public record TyApply(Ty LamdbaAbs, Ty Arg) : Ty;
The first argument should evaluate to a TyLambda and the second argument is the value to pass to the lambda as its parameter.
We can also make construction of these types a little easier by adding some static functions to Ty:
public record Ty { public static readonly TyPrim Int = new(Prim.Int); public static readonly TyPrim String = new(Prim.String); public static readonly TyPrim Bool = new(Prim.Bool); public static TyVar Var(string name) => new(name); public static TyName Named(string name) => new (name); public static TyLambda Lambda(string varName, Ty body) => new(varName, body); public static TyApply Apply(Ty lambda, Ty arg) => new(lambda, arg); }
That's all of the basics we need for the moment.
So, something like f a in Haskell would (in its type-system) look like this:
Ty.Apply(Ty.Var("f"), Ty.Var("a"))
Which, when evaluated, will look up f (which it expects to be a TyLambda) and then substitute the evaluated a for VarName in the lambda body. And so, this is how Haskell (and most FP languages) does polymorphism (generics). C# doesn't represent generic types as lambdas, which presumably is why higher-rank polymorphism isn't a thing in C#.
Let's take a look at my solution for higher-rank polymorphism in C#. It is primarily enabled by a single type: K. My argument is that K is equal up to isomorphism to f a in Haskell.
What does "equal up to isomorphism" mean? It means there's a way of transforming one type to the other type and back again without losing any fidelity. So, they're not equal because they're made of different components, but they're convertible back'n'forth and so they're equal up to isomorphism. Which is a slightly weaker statement about equality, but they're functionally equal because we can make one from the other.
K can't be directly represented with the type-system we have created. Let's ignore the K part – it is genuinely irrelevant to this discussion, it's just a label – there are no members in the K type, so the only thing that matters is the part. The part is a tuple of types. So, let's add TyTuple to our type system:
public record TyTuple(Seq Items) : Ty;
A tuple is zero or more types. Let's have some friendly constructors functions in Ty:
public static TyTuple Tuple(Seq items) => new (items); public static TyTuple Tuple(params Ty[] items) => new (toSeq(items));
We can now represent K or really in our type system:
Ty.Tuple(Ty.Var("f"), Ty.Var("a"));
So, to prove the isomorphism between f a and we need to be able to convert between their type-system representations without losing anything in the process.
Let's create a K type as it is in C# (I'm using Option to make it a bit more interesting):
var kOptionInt = Ty.Tuple(Ty.Named("Option"), Ty.Int); // Option
From that, can we create the Ty.Apply version? Yes, we can...
var optionInt = Ty.Apply(kOptionInt.Items[0], kOptionInt.Items[1]);
To prove the isomorphism we need to back able to go back and prove the types are the same...
var kOptionInt2 = Ty.Tuple(optionInt.LamdbaAbs, optionInt.Arg); Console.WriteLine(kOptionInt == kOptionInt2); // True
It outputs True and so proves we can convert one way and back again. Let's, for completeness, start with Ty.Apply and convert to Ty.Tuple and back again:
var optionInt = Ty.Apply(Ty.Named("Option"), Ty.Int); var kOptionInt = Ty.Tuple(optionInt.LamdbaAbs, optionInt.Arg); var optionInt2 = Ty.Apply(kOptionInt.Items[0], kOptionInt.Items[1]); Console.WriteLine(optionInt == optionInt2); // True
That also outputs True – they're equal up to isomorphism and we've proved it.
To take this proof further we can build the evaluator for the types and prove that the evaluated types are equal (up to isomorphism). I will do that if this article gets some push-back, but I already know the answer.
So, it doesn't matter what the purists say. The language-ext approach to higher-kinds is the same as the approach in Haskell and any other language with higher rank polymorphism. Yes, we need an additional type to represent the partially applied type (for example, IO for the IO), but that doesn't matter as we only attach the trait implementation to that 'partially applied' type. That's not much different to having separate types for the class instance definitions in Haskell – in fact I'd argue they're also isomorphic.
I do feel there's often a snobbishness about those of us who are doing functional programming in C#. The arguments are nearly always based around some bullshit academic reasoning not related to solving the problem but purely to be a position to sneer from. It adds nothing. Or we get something like "why do it in C# in the first place, when there are better languages around?" – which is always a naive statement to make.
By the way, I have no issue with academics or the pursuit of knowledge through academia. The whole of language-ext is standing on academic shoulders. But the unwillingness to accept other practical solutions to problems and then the inevitable sneering is tiring and unnecessary. C# can achieve every aspect of higher-kinded traits using its type-system. No hacks, no reflection, no dynamic references. Purely with its type-system – that should be the end of the discussion.
Haskell (the poster-child for pure functional programming) has many problems also. I led a team doing a pure Haskell project two years ago. It was the first time I'd used Haskell in a professional setting – I've used it on and off for many years on personal projects, just never professionally. The major problems I encountered were:
The open-source library ecosystem is poor:
Lots of unmaintained and incomplete projects for critical functions
Lots of amateurish solutions (again, for critical functions) – I put this down to the Haskell world being full of academics and not professional engineers.
We ended up building our own libraries of things you'd normally take off-the-shelf in other ecosystems. As a leader seeing time eaten up this way is tough.
The more junior devs in my team had a really hard time with the language. These devs had worked with language-ext for years, so it's not like they had no exposure to pure functional programming, but for some reason they struggled. In parallel to this we'd even done a weekly 'Haskell book club' to get everyone up to speed and to encourage discussion – but it didn't really move the needle.
The tooling, although much better than it was when I first learned Haskell, is still poor. The compiler is slow. It tends to exit on the first error and then produce other spurious errors. The debugging story was extremely poor (I suspect this was the main issue for juniors struggling). Even random things like the auto-formatting engine we were using just stop being supported. And the plugins to VSCode seem to be endlessly buggy.
Luckily, as a co-founder of the company, I was able to weather the relatively slow progress of the project: I understood that the code was likely to be more robust and would need less maintenance and so a slower initial phase of the project could be caught up later.
However, after a year we decided to can the project. It was a business decision not related to Haskell, so I won't claim it was the cause of the canning, but based on my experience I will probably never start a greenfield project with Haskell again.
Don't get me wrong, I still love the language, it has directly influenced much of language-ext, but the ecosystem is weak – which, after 30 years of Haskell's existence, probably means it's not likely to get much stronger.
The reality is C# is used by more people than Haskell. The library ecosystem is mature. C# for all its problems has world-class tooling. The compiler is probably second to none. The IDEs (Visual Studio or Rider) are second to none. There are probably more people doing functional programming in C# than in the entire Haskell community. These are things to not take lightly when choosing a language to build substantial projects with.
Don't we deserve higher-kinds? Aren't we allowed to follow the pure functional programming paradigm?
I think we are.
As expected a flame war started as soon as I posted this to Twitter (I mean, like within minutes!)
Anyway, I'm opting out again, because the arguments are circular and going nowhere. But, the whole point of this post was to ease the mind of those stepping into this world for the first time – it wasn't to make lambda calculus obsessives happy. So, I'll cover some of the "issues" raised and then leave it as that:
"As for your proof, here is a simple counter-example. In C# the following instantiation of type variables is legal: K. In Haskell 'String Int' fails to type check (exactly because there is simply no notion of kinds in C#)"
There are kinds in C#, we have generics, so we have kinds – we just can't use type-variables as the first part of the * -> * arrow (meaning we can't parameterise the F in F).
K is legal in C# but it has no use for implementing traits. That doesn't make the approach invalid. The argument that it should be invalid is arguing that the first parameter (string) should be a lambda-abstraction. But it doesn't need to be in the tuple based approach to implementing higher-kinds, because we're not using lambda-abstractions, and we're not using lambda-abstractions because we're using tuples, ... So, the argument is a pointless circular one. It's basically saying "It's not implemented like Haskell, therefore it's not valid" which isn't a good argument.
However, stating that IO as the first argument (for example) is a * -> * kind in Haskell and a * kind in C# does require a little more explanation. The isomorphism works in the type-system I invented in this article. The isomorphism doesn't work in Haskell or C# – Haskell doesn't have tuple types and C# doesn't have lambda-abstractions – so this proof can't be run in either language.
My primary point with the proof above was that a 2-tuple and a type-application are isomorphic.
I realise that's not the most profound proof to ever be written, but it validates the approach of using the tuple-type K to represent F. F isn't a lambda-abstraction because it doesn't need to be in our approach, we are able to resolve the relevant trait from the * type without the need for a partially applied value being passed as an argument to a trait-type.
Quite simply, we don't need lambda-abstractions to implement higher-kinded traits, which is lucky, because C# doesn't have them.
"No, Haskell does not encode HKTs. Its type system is directly based on lambda calculus, and LC is _the_ definition of kinds and types. There is no need to encode the definition when you (Haskell) are the "native" implementation of the definition."
I love it when someone points out Haskell's implementation is done with lambda calculus as I state clearly in the article and I implemented the type-system using it! Some people just like to score points on the internet I guess. Perhaps it needs a new term: 'Lambdasplaining' maybe?
"We can indeed see this HKT embedding as an alternative implementation, only in library space and not in the type system. It is not the same or equivalent to native support though and claim that C# supports HKTs."
This is one of those "you can't play with your toys because they're not as good as ours" arguments. It looks down on the implementation saying it's not 'native'. The only thing language-ext does is say: "Let's use this type K to represent higher-kinds" – but K is still a C# type, it's not something magical hacked into the type system – it introduces a convention, sure, but that's it. Everything else is the C# type-system as-is. There's no reflection, there's no cheating, all constraints are enforced by the C# type checker. As it should be. F is not constrained to be a lambda-abstraction, because lambda-abstractions don't exist and we don't need them to implement higher-kinded traits.
"As you write yourself, C# allows and accepts only type variable of kind *. In particular not of kind * -> *. No arrows, no HKTs. This is the definition of what it means to be a HKT and you can't promote an embedding to the real thing just by declaring them as equivalent."
This argument is, yet again, arguing that only lambda-abstractions can encode higher-kinded types. Yet, as we see, they can be encoded by other means. The general crux of this poster's recursive responses is that "it's not lambda calculus, so your approach isn't valid".
My response is this: Alan Turing proved that his Turing Machine was equivalent to Lambda Calculus. So, not every implementation has be in Lambda Calculus to be valid. And, if you have a problem with that, take it up with Alan Turing.
Response from Erik Meijer
"Super cool hack, really; but an encoding does not imply it is usable. More importantly

> Don't we deserve higher-kinds? Aren't we allowed to follow the pure functional programming paradigm?

Higher kinds does not give you pure functions

https://queue.acm.org/detail.cfm?id=2611829…

If you are using C#, IMHO, it is best to stick with idiomatic C# instead of trying to bolt a pseudo Haskell style on top.

Don't fight the language, embrace it. Write baby code. KISS."
I have a lot of respect for Erik. He brought LINQ to C# after all! He's one of the few people in the industry that I am always interested in hearing from, because even though his Twitter handle is @headinthebox, he really is someone who thinks outside of the box. I would encourage you to look up his talks on YouTube as they're always thought provoking and usually pretty inspirational too.
That doesn't mean I agree with him on everything though!
Before Erik wrote this response I already knew his position on this (because I've watched his talks). But let's break down what he's said:
but an encoding does not imply it is usable
Nobody knows yet whether this will be usable, because I have yet to release language-ext v5. But, I've been dog-fooding it myself, building a DB Layer for Foundation DB and I have to say, it feels pretty good! The fact that this actually makes LINQ work like do notation in Haskell (i.e. once you implement the Monad trait for your type, LINQ starts working), in my mind, finishes the job that should have been done by the C# team. They stopped short of implementing monads in C# properly and instead opted for 'magic methods' (Select and SelectMany) – this was a colossal mistake in my humble opinion. They should have at least committed to making a trait system to deal with the C# magic methods (all of them) if they weren't able to do it at the time.
Higher kinds does not give you pure functions
That wasn't what I was implying with the sentence I wrote. So a small misunderstanding there.
https://queue.acm.org/detail.cfm?id=2611829…
I'd previously read 'The Curse of the Excluded Middle' stating that "Mostly functional" programming doesn't work. Mostly.
I agree with the basic premise and go to great lengths in the Monad article to emphasise the importance of everything being pure functions. However, I don't fully agree with Erik's position.
Let's say this was my program:
void Main() { PureFunction().Run(); ImpureFunction(); }
If those functions represent (by some odd coincidence) half of your code base each (half pure, half impure). Then you still benefit from the pure functional programming half. So, you can start small and build up something that becomes progressively more stable. Every block of pure code, even if surrounded by impure code, is one block you don't have to worry so much about. Is it fundamentalist programming? Of course not. But slowly building out from there pays you back each time you expand the scope of the pure code. You won't have solved all of the worlds ills, but you've made part of the world's ills better. Any pure function in an impure code-base is, by-definition: more robust, easier to compose, cacheable, parallelisable, etc. these are real benefits, doesn't matter how small you start.
I have direct experience of this, the project I ran from 2005 - 2023, which was a 10 million lines of code behemoth, started out imperative and OO. It kept falling foul of the issues you get all of the time with mutable-state imperative applications (we were writing 'baby code' as Erik calls it). I looked for an alternative approach and that birthed language-ext. Over time language-ext took over the application.
Still today there are areas that are not pure, but there's a huge amount that is, and that code is easier maintain and extend than the impure parts. So, you do get benefits, and you can progressively move over to pure FP. Just remember, any impure function in a pure expression makes the whole thing impure – so as devs we have to be strict with ourselves.
But, even in a language like Haskell there's a function called unsafePerformIO which breaks all of the purity guarantees of Haskell – it doesn't show up in any function type-signature – so you have no idea whether any of your code is pure. By convention, people try not to do that, but they can. It's the same in any other language, you have to be strict with yourself. And, on a team, you have to have a good code-review process in place so impure code doesn't sneak into the pure bits of your code. It requires a culture change within your team, everyone needs to understand why you're doing this.
Ultimately though, that's why language-ext is more of a 'base class library' for FP in C#. Because if you're going to do pure FP in C# then you're not going to get it by just adding an Option library to your app, you have to go all-in. This library is intentionally breaking the idioms of C# to create a new community of functional-programmers within the C# set of devs. Much like the sub-communities with Scala-land (although, hopefully without the infighting!)
If you are using C#, IMHO, it is best to stick with idiomatic C# instead of trying to bolt a pseudo Haskell style on top.
As I've mentioned, I'm breaking the idioms on purpose, there's room for two. But, even with that said, I think the idioms of C# have moved quite far from where it was in v1.
Look at the new INumber type (which is the base interface for Int32 etc.):
public interface INumber : IComparable, IComparable, IComparisonOperators, IEqualityOperators, IModulusOperators, INumberBase, IAdditionOperators, IAdditiveIdentity, IDecrementOperators, IDivisionOperators, IEquatable, IIncrementOperators, IMultiplicativeIdentity, IMultiplyOperators, ISpanFormattable, IFormattable, ISpanParsable, IParsable, ISubtractionOperators, IUnaryPlusOperators, IUnaryNegationOperators, IUtf8SpanFormattable, IUtf8SpanParsable where TSelf : INumber
The .NET team, in their own especially wordy style, are also using this trait technique. With IAdditiveIdentity and IAdditionOperators they are also embracing semigroups and monoids! So, I'm not sure this approach is really that far away from idiomatic C# any more.
Of course, taking this a step further to implement more complex types like Monad and Applicative could be argued to be pushing that boundary a little, but the technique is the same really.

Higher Kinds in C# with language-ext [Part 7 - monads]

Paul Louth — Fri, 26 Apr 2024 15:02:33 GMT

This is a multi-part series of articles – and you'll need to know much of what's in the earlier parts to follow this – 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
OK, this is the big one, the one we've all been waiting for, yes, it's time to implement monads!
There's a bit of a meme in the dev community around the difficulty in explaining monads. Do a search for "Yet Another Monad Tutorial" and you'll see what I mean!
Apparently, nobody has found a way to concisely or clearly describe monads to the average non-monad-knowing person. There appears to be a 'thing' where, once someone is confident with pure functional-programming, they forget how difficult/alien it seemed at first and because pure functional-programming is – in many ways – simpler than imperative programming, they lose all ability to put their minds back into that initial confused state.
You may balk at the idea that pure functional-programming is simpler than imperative programming – especially when it comes to the terms, like 'monad', 'functor', 'applicative', ... there's a feeling of "I can't place these terms with real world concepts". But, terminology aside, I have never felt more confident about my code as I have in the pure functional-programming era of my life. I did ~15 years of procedural coding (BBC BASIC and C), ~15 years of OO coding (with C++ and C#), and have now done more than a decade of FP programming (C#, F#, Haskell, PureScript). So, I feel I can confidently state that I have had enough experience to at least have an opinion on this!
I suspect I fall into the 'fail to explain properly' trap sometimes too, it's probably impossible not to. I re-read my last article on the Traversable type and can't help but think that it needs some better exposition. But, right now, I can't tell whether the five previous articles are enough for the reader to follow along – it should be, but is it?
I promised myself I'd never write a 'Yet Another Monad Tutorial'. But, because we now have the new Monad trait in language-ext, it probably needs some explanation!
Yet Another Monad Tutorial
Something that is always missed in monad tutorials is "why?". Why do we even need monads?
First, we don't need them. C# devs can manage perfectly fine without them. But, what language-ext is all about is enabling pure functional programming in C#. And, although monads aren't needed for pure functional programming, they make the life of the pure functional dev easier. But, before I can explain why, let's just have a refresher on the whole pure functional programming 'thing'...
The basics of pure functional programming are this:
Functions are values
Everything is an expression
All expressions are pure and/or have referential transparency
Item 1, we know about, so that doesn't need explaining. Item 2, 'Everything is an expression' thing is interesting. If everything is an expression then we don't have statements – no lines of code, just an expression-tree of code. Expression trees are quite hard to mentally manage (as well as write), so we need to find a way of having lines-of-code that are still, somehow, expressions.
If you look at an ML based language, you might see some code like this:
let x = doSomething () in let y = doSomethingElse () in x + y
These look like statements in an imperative language, the temptation is to think the above is equivalent to:
var x = DoSomething(); var y = DoSomethingElse(); return x + y;
But, in fact they're completely different. The ML example gets rearranged by the compiler to be lambdas with invocations (everything is a function in functional programming!):
(fun x -> (fun y -> x + y) DoSomethingElse()) DoSomething()
That is how something that is an expression can end up looking like multiple statements.
There is a real scoping difference – even if they look exactly like regular statements. The example above can be factored and reduced in a way that imperative statements can't (well, not without some serious analysis).
OK, so what? Why should we care? Well, we can now write expressions in an imperative way (which I think is probably more natural for us) without losing any of the benefits of expressions.
Item 3: "All expressions are pure and/or have referential transparency" is the next thing we need in pure functional programming...
A pure expression is either a primitive value or entirely constructed from other pure expressions. The 'smallest' pure expression is a value. It should not produce any side-effects (no mutating global state, no writing to a file, etc.).
A pure function is one where the function body is a pure expression. The only values the expression can depend on are those provided to the function as arguments (so, no references to global state). That means the result of the function is entirely dependent on the inputs to the function.
An expression that has referential transparency is almost exactly the same as a pure expression. The main difference is that 'internally' it may not be a pure expression (could be implemented as a for loop, for example), but on the 'outside' it behaves in exactly the same way a pure expression behaves. Namely that you could replace the expression with a value and the consequence of using it remains the same.
There is a small problem though. A requirement of both pure expressions and referentially transparent expressions is that we should be able to replace the expression with a value (because we expect the same result from evaluating the expression every single time). But, for some expressions, that isn't true...
var now = DateTime.Now;
Clearly, we can't replace the DateTime.Now expression with the first result we get and then use it forever more, otherwise the time will never change. DateTime.Now is not pure.
So, if we're going to do pure functional programming, where every single expression is pure then we need a different approach.
You may think "So what, this is C#, just use DateTime.Now and get over it?!". That is certainly a valid approach. But, you have to remember why we're doing pure functional programming in the first place:
Fewer bugs: Pure functions, which have no side effects and depend only on their input parameters, are easier to reason about and test, leading to fewer bugs in the code-base.
Easier optimisation: Since pure functions do not have any side effects, they can be more easily optimised by the compiler or runtime system. This can lead to improved performance.
Faster feature addition: The lack of side effects and mutable state in pure functional programming makes it easier to add new features without introducing unintended consequences. This can lead to faster development cycles.
Improved code clarity: Pure functions are self-contained and independent, making the code more modular and easier to understand. This can improve code maintainability.
Parallelisation: Pure functions can be easily parallelised, as they do not depend on shared mutable state, which can lead to improved scalability.
Composition: This is the big one. Only pure functional programming has truly effective composition. Composition with impure components sums the impurities into a sea of undeclared complexity that is hard for the human brain to reason about. Whereas composing pure functions leads to new pure functions – it's pure all the way down, it's turtles all the way down. I find it so much easier to write code when I don't have to worry about what's going on inside every function I use.
That's the 'short list', there's probably more that I've forgotten, but it's already pretty compelling.
The main thing to note is that if you opt-out of pure functional programming anywhere in an expression, then you compromise the whole expression – it stops being turtles all the way down. So, we want everything to be pure to get the compositional benefits; we need a way to encapsulate impure actions like DateTime.Now and, somehow, make them pure – otherwise we may as well give up on the idea completely.
Back to the "why?"
OK, so pure functional programming refresher done and an unresolved issue highlighted: 'encapsulation of impure expressions'.
Let's get back to the "why?". Why do we even need monads?
Monads encapsulate impure side-effects and other effects, making them pure
Ding, ding!
Monads allow sequencing of operations, like the let example earlier, so that we can chain expressions together.
Monads (with LINQ in C#) allows us to write pure code that looks a lot like statements in imperative code.
Quite simply: Monads are the 'statements' of pure functional programming and they encapsulate messy side-effects.
And so, when you see people struggling to explain monads, or they're trying to bring them into a domain that isn't pure (or their goal isn't to enable a pure functional programming experience) then I think the reasoning in favour of monads goes awry.
Monads are simply a design-pattern for pure functional programmers. That is all. No more.
OK, that was a lot of words to say "it's a design pattern", but hopefully now you have some context for why we're even doing this.
It must be stated that, beyond the justifications above, they also encapsulate some truly awesome patterns that are not served by any other technique and they are super-powered boilerplate killers!
So, let's get back to DateTime.Now. And let's try to make that pure. What does DateTime.Now do? Well, it accesses the system-clock and uses that to give you a DateTime struct which is a snapshot of the current-time.
DateTime.Now is clearly doing an IO operation. It is accessing some state outside of the application and then returning that state. So, why don't we start by creating a type called IO:
public record IO(Func runIO);
Notice how we're capturing a Func and not a value. This is important because we're not trying to capture a snapshot but a computation.
OK, now let's create our own DateTime module (we'll call it DateTimeIO to avoid a name clash):
public static class DateTimeIO { public static readonly IO Now = new (() => DateTime.Now); }
So, now, instead of returning a DateTime we return an IO. This is the 'get out of jail free card', it means the return value isn't a snapshot of time any more. You can replace any call to DateTimeIO.Now with the resulting IO in any expression and the result will be the same. We've taken something that was impure and made it pure.
You might think that this is a sleight of hand, but it really isn't. The rules hold. We are still returning a data-structure, but it's a data representation of a computation, rather than a snapshot data-structure. The call to DateTimeIO.Now is interchangeable with IO in a pure expression.
The problem is that the code that wanted to use the DateTime snapshot, now can't, it has an IO not a DateTime – so what do we do? If you remember the discussion about lifting, this is a situation where we have a lifted computation, so we need to work in the lifted space. The first step is to make the IO type into a Functor:
So, as with the examples in the previous articles, derive the type from K:
public record IO(Func runIO) : K;
Add an extension to downcast:
public static class IOExtensions { public static IOAs(this K ma) => (IO)ma; }
Let's also have an extension that will run the IO computation to get a concrete value:
public static class IOExtensions { public static IOAs(this K ma) => (IO)ma; public static A Run(this K ma) => ma.As().runIO(); }
Then we can start building the IO trait-implementation class:
public class IO : Functor { public static K Map(Func f, K ma) => new IO(() => f(ma.Run())); }
What we're doing in the Map function is invoking the Func inside the IO type. It returns an A value; we pass that value to the f function, which gives us a B; and we then wrap that all inside a new Func so we can construct an IO.
That means we can now work with the value within the IO :
var thisTimeTomorrow = DateTimeIO.Now.Map(now => now.AddDays(1));
Hopefully it's obvious that every time we use DateTimeIO.Now we will get the latest time. That is also true if we assign DateTimeIO.Now to another variable and use that variable at some point in the future.
So, as seen in previous articles, we can lift functions into the IO functor and work with the value within.
Next, we can upgrade the IO type to be an Applicative:
public class IO : Applicative { public static K Map(Func f, K ma) => new IO(() => f(ma.Run())); public static K Pure(A value) => new IO(() => value); public static K Apply(K> mf, K ma) => mf.Map(f => f(ma.Run())); }
Both of these steps are needed on the way to making IO into a monad, we've done this in previous articles, so I'm pushing through quickly...
Now, let's upgrade the IO type to be a Monad:
public class IO : Monad { public static K Bind(K ma, Func> f) => new IO(() => f(ma.Run()).Run()); public static K Map(Func f, K ma) => new IO(() => f(ma.Run())); public static K Pure(A value) => new IO(() => value); public static K Apply(K> mf, K ma) => mf.Map(f => f(ma.Run())); }
The new function is Bind. If you look at the f function for both Map and Bind, you'll notice that the only difference is that instead of returning a B the Bind version of f returns an IO.
So, monad Bind and functor Map are very similar. We can even write Map in terms of Bind and Pure:
public static K Map(Func f, K ma) => Bind(ma, x => Pure(f(x)));
Which might give you a bit of insight into the similarities and differences between Map and Bind. The similarities are mostly aesthetic – they look similar. However, the differences are huge: by returning a new monad instead of a concrete value, we are inviting a chain of operations to happen. The implementation of Map (in terms of Bind and Pure above) highlights that Pure means 'terminate the chain'. Stop the operation here. So, Map is like a Bind operation that always terminates.
Applicative Apply can also be implemented in terms of Bind and Map:
public static K Apply(K> mf, K ma) => mf.Bind(ma.Map);
Which is quite elegant and is nearly always a good first implementation of Apply, but for some monads it's better to have a bespoke Apply method.
Now, let's look at the internals of Bind a little closer:
f(ma.Run()).Run()
We get the first IO – run it – then invoke f with the result. The result of f is an IO which we also run. So, that's one IO operation that runs, that returns a new IO operation, which we run too.
Sounds like two operations:
doTheFirstThing(); thenDoTheNextThing();
Bind is how 'statements' are done in pure functional programming.
Let's add a few more IO values to our DateTimeIO type:
public static class DateTimeIO { public static readonly IO Now = new (() => DateTime.Now); public static readonly IO Today = new (() => DateTime.Today); public static readonly IO Tomorrow = new (() => DateTime.Today.AddDays(1)); }
And now, let's try to use Bind:
var diff = DateTimeIO.Today.Bind( today => DateTimeIO.Tomorrow.Map( tomorrow => tomorrow - today));
So, Bind allows another IO operation inside its injected function. In theory you can do this multiple times (with any number of IO operations). But, as you can probably tell, that will turn into a pyramid-of-doom quite quickly.
You can also write the above example with two nested Bind calls and an IO.pure:
var diff = DateTimeIO.Today.Bind( today => DateTimeIO.Tomorrow.Bind( tomorrow => IO.pure(tomorrow - today)));
Now the terminating Pure seems more obvious!
To deal with the pyramid-of-doom we need some first-class language support. In Haskell, they deal with this using do notation, it might look something like this:
diff = do today <- DateTimeIO.today tomorrow <- DateTimeIO.tomorrow pure (tomorrow - today)
Notice the pure terminator
In C# our equivalent is LINQ. It is genuine first-class monad support in C#. The only thing we couldn't do in the past with LINQ was to generalise over all monads. But, now – with the higher-kinded types in language-ext – we can. Once you have implemented the Monad trait for your type, it will immediately work in LINQ (no need to manually implement Select and SelectMany):
var diff = from today in DateTimeIO.Today from tomorrow in DateTimeIO.Tomorrow select tomorrow - today;
I often see other language ecosystems trying to bring monads into their domain. But, without first-class support for monads (like do notation in Haskell or LINQ in C#), they are (in my humble opinion) too hard to use. LINQ is the killer feature that allows C# to be one of very few languages that can facilitate genuine pure functional programming.
I just wish Microsoft would put some effort into improving LINQ:
Discards for variable names (from _ in foo)
Allocation free local lambdas to reduce the garbage
Remove need to use select as the last term, allow a lifted type to be evaluated as the final term. This will allow for recursive monads that use trampolining internally (enabling infinite recursion).
So, Microsoft, please, this is your killer feature!
Pause
It's worth reviewing where we are, because we now have a fully fledged IO monad (and applicative, and functor!) with just this code:
public record IO(Func runIO) : K; public static class IOExtensions { public static IO As(this K ma) => (IO)ma; public static A Run(this K ma) => ma.As().runIO(); } public class IO : Monad { public static K Bind(K ma, Func> f) => new IO(() => f(ma.Run()).Run()); public static K Map(Func f, K ma) => Bind(ma, x => Pure(f(x))); public static K Pure(A value) => new IO(() => value); public static K Apply(K> mf, K ma) => mf.Bind(ma.Map); }
I spent a lot of time in earlier versions of language-ext building code-gen solutions to make it easy to generate monadic types. And now, without any code-gen, we have a much more powerful system that you can build by hand. Very cool!
Naming
Some other 'Yet Another Monad Tutorial' writers have tried to avoid using the word 'monad', or have introduced it at the end of the tutorial, or have renamed the concept entirely.
Personally, I believe if you're going to come along for the 'pure functional ride', then you need to know how to communicate with other people in the space; as well as be able to search online for further information on the subject. And that mostly means understanding the lexicon of Haskell, Scala, PureScript, etc. There's a common dialect and I think sticking with it, even if the words sometimes feel ugly, is the right way to go.
But, if it helps, here are some approachable names that might help give a more instinctive understanding:
Chainable instead of Monad – to represent the fact that operations are chained serially.
AndThen or Then instead of Bind
Composition
In the article on Validation – which was an extended discussion of Applicatives – there is a diagram (repeated below) that has lower-kinds at the bottom, higher-kinds above and the various functions (arrows) that map between the types.
The bottom toString arrow is saying: "If you provide an int, I will give you a string in return" (basic function invocation).
The top Maybe arrow is saying "If you provide a Maybe, I will give you a Maybe in return" (applicative Apply)
So, if you follow the arrows we have various composition options:
int -> Maybe -> Maybe which composes to int -> Maybe
int -> string -> Maybe which also composes to int -> Maybe
int -> string
Maybe -> Maybe
int -> Maybe
string -> Maybe
These arrows and compositions give us the full set of transformations for each of the types in the diagram. They also hint at potential optimisations: if there are two routes that start and end in the same place, which one is more efficient?
What we don't have is any way to get from:
Maybe -> int
Maybe -> string
Because there are no arrows there to follow. Do we need them? And do they make sense?
Usually, going from higher-kinds to lower-kinds is a destructive action. For example, to make Maybe (equivalent of Option in language-ext) collapse down to an int would require us to have a default value to use in case the type is in a Nothing (None) state.
These types of 'lowering' functions are type-specific and don't have abstractions that we can discuss. For discriminated-union types the function is usually a pattern-match operation that collapses the union down to a non-union type. So, we'll consider that to not be an option for trait-level programming.
However, lowering optionally to work on the values within the type, to then re-lift into the higher space is possible. And that is the Bind function...
If we look at the Monad trait we can get some clues:
public interface Monad : Applicative where M : Monad { public static abstract K Bind(K ma, Func> f); // default implementations removed for clarity }
So, we have an argument called ma which is of type: M. That is a 'structure' with zero or more A values within – from the outside we have no idea what's inside – but that doesn't matter, the implementation of the Bind function knows what's inside.
The Bind implementation must extract the A value(s) so that it can pass them to the function f which in return gets us an M.
Or, more concisely:
M -> A -> M
So, the effect of the Bind action is to zig-zag between higher and lower kinds.
The 'lowering' arrows (those pointing down) are the bespoke behaviour of the monad. If it's an IO monad then it knows how to run the internal Func computation that extracts the A value. If it's an Option monad then it does a check to make sure that the structure is in a Some state, and if so it yields the value.
So, why can't the lowering arrow be used to create a generalised lowering function? Because the higher-kind might not actually have any values within it. Option might be None, so we can't yield an A. But, we can map Option.None to Option.None – because we can pluck a None out of thin air. That allows the 'contract' of Bind to be honoured: M -> M,
This is also the essence of the short-cutting behaviour of monads. If there's no value to yield then the f function passed to Bind never gets called because we have no value to give it!
And, because we know that monads chain expressions together serially; not calling f means the rest of the expression isn't invoked either. We essentially exit out of the computation early.
There's another common phrase used to describe monads: "programmable semicolons". Although it is slightly misleading, you can see the lowering-arrow as the point between two computations (two statements) where additional logic lies. This logic can do lots of different things. In the case of Option it is effectively a 'null check' to see if we even have a value – and if not, it bails out of the computation.
Let's take a look at two examples using Option from language-ext:
var inp1 = "100"; var inp2 = "200"; var inpX = "NUL"; var res1 = from x in parseInt(inp1) from y in parseInt(inp2) select x + y; var res2 = from x in parseInt(inp1) from y in parseInt(inpX) // fails to parse, `y` is never assigned from z in parseInt(inp2) // never executes select x + y + z; // never executes // res1 == Some(300) // res2 == None
The parseInt function returns an Option and it will be None if the parse fails.
On the first example, everything parses correctly, which means the final x + y is run.
On the second example, the parseInt(inpX) will return None which means the we have no value to assign to y. And therefore we must exit, because the rest of the expression depends on y having a valid value.
If we look at the implementation of Bind for Option we can see this short-cutting behaviour:
static K Bind(K ma, Func> f) => ma.Match( Some: x => f(x), None: Option.None);
We pattern-match on the Option, if we're in a Some state then we call the f function that continues the expression. If we're in a None state, we just return None – halting the expression.
It's remarkably simple really, but extremely effective because this won't allow you to continue unless we have a value. It can't be cheated. You can't make a mistake when using Option – whereas similar if checks for null values (or the accidental absence of them) can lead to major bugs.
Another interesting aspect of Option is that it helps us fulfil our pure functional programming mandate. Remember, we shouldn't have any side-effects in our functions or expressions. Exceptions are side-effects. Really, if method-signatures in C# were honest, we'd never have a return type of void. And methods that throw exceptions might look something like this:
(Exception | int) ParseInt(string value)
Exceptions should be for truly exceptional events that you can't recover from. Exceptions should not be thrown for expected errors – a failure to parse is expected for a parsing function.
I saw an interesting post the other day on Twitter, from a PM on the .NET team at Microsoft, he was lamenting the incorrect usage of ArgumentException – and then giving advice on what should be done. Completely oblivious to the fact that exceptions are just the wrong approach. The system clearly isn't working as intended; and that's because there's no compiler support, there's no type-system support, it's just convention.
I find it crazy that something like that even needs to be written. The correct approach is to make your function total – that means for every combination of values provided to the function as arguments there should be an associated value in your return type: every value in your domain should map to a value in your co-domain. This honours the requirement for the output of a pure function being totally dependent on its inputs.
How do we do this?
Constrain the types that are used for the arguments. Make sure there's no possibility of constructing input values that are 'out of range'.
Where the input arguments are constrained as much as possible, but the combined states of all arguments still falls outside of what the co-domain can handle, augment the co-domain with a failure value. This is where Option comes in. It allows us to return None if we're unable to handle the input values: we augment the co-domain.
This leads to declarative type signatures like below. Type signatures that speak to programmers:
Option parseInt(string value)
Monads are a big part of the declarative programming story. They 'mark' whole sections of code as having a particular flavour. For example, once you're working in the IO monad you have declared that code as something that 'does IO'. I know that might sound obvious, but it encourages you to separate your non-IO code from your IO code, which leads to more composition options, and ultimately more robust code.
By the way, this is why you shouldn't ever really call .Run() on the IO monad (well, not externally, internal behaviours like Map and Bind are fine). Once you're in an IO lifted space you should stay there to indicate the expression 'does IO'. The place to call Run is once in your Main function. Although, because we sometimes need more flexibility in C#, once in your web-request handler also makes sense. Collapsing IO down to A re-injects your code with impure effects, breaking the pure functional programming mandate.
So far we've seen that:
The Bind function for the IO monad allows us to make impure operations, pure.
The Bind function for the Option monad allows us to deal with functions that might not be able to return a value (partial function) and, if no value is available, the Bind function automatically short-cuts the expression to stop accidental usage of None values.
The behaviour of the two Bind functions are dramatically different to each other, yet they share the same abstraction: they're both monads.
It turns out there are many different 'flavours' of Bind function that can be written that cover a whole slew of behaviours; from resource-tracking, state-management, configuration, logging, validation, list iteration, stream-processing, etc. etc. They're all just different implementations of Bind. I think this is another reason why Yet Another Monad Tutorials are quite hard to write: there's so much that you can do.
If you can program your semicolons, where's the limit!? How could you possibly write a tutorial that covers it all?
Ultimately, the Bind function is just another form of function composition. The result of the composition is: M -> M. Where M is the flavour of monad.
Everything in functional programming is function composition. E v e r y t h i n g. Monads are just another flavour of function composition that works with slightly different arrows to the other flavours! I know the abstractions are sometimes a bit hard to picture, but often it just means lining up the types and following the arrows. In many ways it ends up being more like Lego than programming!
This article is now probably one of the longest so far (with the fewest code examples); I realise there were a number of diversions into 'the why' of pure functional programming, but I feel that is the real origin-story of monads and why you should care about them.
That has made this article a bit longer and wordier, but hopefully it sets the scene nicely for the next episode. In the next article we'll dig into the different types of monad in language-ext and also discuss monad 'join', also known as Flatten.
Part 8: Monads continued

Higher Kinds in C# with language-ext [Part 6 - traversables]

Paul Louth — Tue, 16 Apr 2024 10:30:47 GMT

This is a multi-part series of articles, it's worth going back to the earlier parts 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
One interesting stat is that I have managed to remove nearly half a million lines of code from the v5 release of language-ext. At least 200,000 of those lines were auto-generated by some T4 templates (LanguageExt.Transfomers, which has now been deleted entirely); the rest of the deletions were from hand-written types and extension methods used to simulate higher-kinds (OptionAsync for example, is emulating the (new) monad-transformer stack OptionT).
The reason that so many lines of code have been removed is because we don't need to emulate higher-kinds any more, we really can write: OptionT, whereas before we relied on generated extension methods (I'll talk about transformers in a later article).
So, if the removal of nearly half a million lines of code doesn't justify the techniques I am highlighting in this series, I really don't know what will! Less code pretty much always means fewer bugs and easier long-term maintenance – something I am particularly looking forward to once this release is stable!
Also, v5 has much more functionality – not less!
One thing I noticed as I was working through all of the original language-ext unit-tests – trying to turn them all green – was that I discovered some tests-cases where both the code and the unit-test had a bug. The bugs discovered were in the manually written Traverse and Sequence functions.
On [some of the implementations of Traverse] I had made wrong assumptions and I had carried those wrong assumptions through to the unit-tests! It doesn't matter how good you are at programming, you will always end up making stupid mistakes like this – which is why I much prefer to leverage types over unit-tests: you can't cheat the compiler, but you can easily cheat yourself!
The new implementations of Traverse (leveraging the higher-kinded traits) exposed those bugs – because they are now following the rules of the trait-types – not the assumptions of a human that errs.
In the Foldables article I showed the graph from the Haskell Typeclassopedia – we're quite a way into implementing the key traits from this diagram:
In this article we will take on the Traversable trait. You can see from the diagram above that there are three arrows leading into the Traversable trait: Functor, Foldable, and Applicative. We have already implemented these in previous articles, so we have all of the components needed to create a Traversable trait.
But what are traversables? Simply, traversables are a little bit like foldables in that you can iterate over many items in a structure, aggregating as you go. Except, traversables don't expose an aggregated state-value, they instead return a nested foldable/applicative structure. The aggregation comes from running the default applicative behaviour for the structure instead of a provided fold function. This nested structure is 'flipped' so what was inner becomes outer and what was outer becomes inner.
That explanation is too abstract, so let's take a look at an example. Below, we have a collection of strings that we want to parse into integers. Not all strings can be parsed into a valid integer, so we need a way to deal with the failure to parse:
var items = Seq("1", "2", "3", "4", "5"); var values = items.Map(s => parseInt(s));
The example above takes a Seq, each value is passed to the parseInt function from the language-ext Prelude. parseInt returns an Option. And so, the result of this would be:
[Some(1), Some(2), Some(3), Some(4), Some(5)]
So, the success of the parsing is embedded into the list.
If we had an item that caused a failure:
var items = Seq("1", "2", "3", "X", "5"); // NOTE: 4th item is 'X' var values = items2.Map(s => parseInt(s));
Then the result looks like this:
[Some(1), Some(2), Some(3), None, Some(5)]
Now we can tell which items succeed and which failed. Which on its own is pretty useful, but if we want to work with the values in the list we have to do work on every step to test that the value exists.
Often, we want to know whether all items succeeded and only proceed if that is the case. And we often want to early out if any fail, not to continue to parse the rest of the list.
This is where Traverse comes in. Simply replace Map with Traverse:
var items = Seq("1", "2", "3", "4", "5"); var values = items.Traverse(s => parseInt(s));
Now the output is this:
Some([1, 2, 3, 4, 5])
We have 'flipped' the type. Instead of a Seq> we now have an Option> – this is the magic of traverse. It follows the rules of the outer applicative (Option) to accumulate the inner foldable (Seq) – resulting in the behaviour of Option being embedded for each item in the sequence.
If we have a collection where the transformation would produce None ...
var items = Seq("1", "2", "3", "X", "5"); var values = items.Traverse(s => parseInt(s));
... then we get:
None // Option>
If any item fails, they all fail.
This works for all foldables with all applicatives – injecting the default applicative behaviour for each step (which, by the way, may not shortcut the operation, as it does with Option).
Here's a simple example using the generic IO library with the Eff monad:
var items = Seq("c:\\test1.txt", "c:\\test2.txt", "c:\\test3.txt"); var values = items.Traverse(File.readAllText);
That will read all of the files (in parallel). If any fail then the whole thing fails.
Applicatives such as the Validation type from the last article would collect all of the errors during a Traverse call. And so, it should be clear that there's a lot of power lurking inside these combined types.
It can't be understated how valuable Traverse is for pure functional programming. It is one of the most powerful tools to reach for when you find your types are 'the wrong way around' – that is: the flipping of the types and the injecting of the default applicative behaviour allows for some incredibly concise transformations. As you can see it works especially well with sequences of values – but it's not only for sequences!
Let's look at the trait definition:
public interface Traversable : Functor, Foldable where T : Traversable, Functor, Foldable { public static abstract K> Traverse( Func> f, K ta) where F : Applicative; // ... default implementations removed for clarity ... }
This is enough to hurt anybody's head! I remember when I was first learning Haskell and I saw the type-signature for traverse – it took me quite some time to really grok it. Primarily because I had never really dealt with multiple levels of higher-kinded types before, so it messed with my brain a bit.
Here's the Haskell definition:
class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) -- default implementations removed for clarity ...
You should be able to see that we have the same constraints on the class/interface as well as the same constraint on the traverse / Traverse function:
(Functor t, Foldable t) is the same as : Functor, Foldable
Applicative f => is the same as where F : Applicative
The traverse / Traverse function also has the same arguments and return type:
(a -> f b) is the same as Func>
t a is the same as K
f (t b) is the same as K>
The return type – f (t b) – was what confused me when I was learning Haskell. It should be a little clearer to you seeing the C# version: it's two, nested, higher-kinded types.
We have two higher-kinds: F and T. F is constrained to be an applicative-functor and T is constrained to be a functor and a foldable.
So, we pass in a value that can be folded over and mapped. We also pass in a function that takes the bound-value of the foldable/mappable; it returns the applicative K.
So, it should be fairly obvious that we somehow iterate over each value in the foldable/mappable ta, pass each value to the function f, and get a value back for each item. What isn't clear is how that K turns into a K>.
As we're calling Traverse on Seq above, let's first look at the implementation of Traverse for the Seq type:
static K> Traverse(Func> f, K ta) { return F.Map, K>( ks => ks, Foldable.foldBack(cons, F.Pure(empty()), ta)); K> cons(K> xs, A x) => Applicative.lift(Prelude.Cons, f(x), xs); }
Ok, that's also enough to hurt anybody's head! Let's break it down:
We have two arguments:
Func> f – this is the function that does the transformation to the applicative
K ta – this is the Seq that is being traversed
Now let's look at the elements of the first expression. The critical part is:
Foldable.foldBack(cons, F.Pure(empty()), ta)
This leverages the fact that the input type (ta) is foldable. The fold operation needs an initial state:
F.Pure(empty())
F is the output Applicative - so we're lifting empty() into the F applicative. empty is just the constructor of an empty Seq. So, F.Pure(empty()) is a K>. It should be fairly clear that this is the result type before we've processed any of the values (and indeed if the input Seq is empty then this will be the result).
The function that does the folding is cons. Which is a local function below the expression:
K> cons(K> xs, A x) => Applicative.lift(Prelude.Cons, f(x), xs);
It takes in two arguments (as all fold functions do) – the first being the running state and the second being the next item to process. We then do an Applicative.lift with the Cons function from the Prelude (which prepends an item to be the new head of a list); the mapped item (f(x)); and the list so far xs.
Applictive.lift is like calling fun(Prelude.Cons).Map(f(x)).Apply(xs) – it's a handy shortcut that makes it a little easier to lift functions.
And so, you should see that the applicative Apply method is chained for each item in the sequence. The function being applied is the Seq cons function that prepends the mapped values to the head of the list. But, if you remember (from the previous Applicative article) the Apply function has inbuilt behaviour depending on the structure being applied.
And so, if we were processing a sequence of Option values then it would know to quit if the result of f(x) is None; if we were processing a sequence of Validation values it would know to collect all of the failed values; if we were processing a sequence of Eff effects it would know to run them in parallel; etc.
This is super, super powerful and turns into incredibly concise code.
But, there's still some code from the Seq implementation of Traverse that we haven't covered:
return F.Map, K>( ks => ks, Foldable.foldBack(cons, F.Pure(empty()), ta));
The result of the foldBack call is mapped using Functor.Map – remember the F is an Applicative, which inherits Functor. We do this to convert from Seq to K. So, even though Seq inherits K we still can't just cast the nested K> to K> because C# just does not play nice with covariant and contra-variant casting of nested types – there were some combinations of in and out on the trait types I could use to make the above compile (without needing to Map) but they were causing runtime casting exceptions – so I decided to err on the side of caution and make the casting explicit. This adds some overhead, but is correct, which is more important. So, we need to run a map operation to get to the base interface from the concrete nested inner-type.
Here's an alternative approach that doesn't need the Map:
static K> Traversable.Traverse(Func> f, K ta) { return Foldable.foldBack(cons, F.Pure(empty().Kind()), ta); K> cons(K> xs, A x) => Applicative.lift((b, bs) => b.Cons(bs.As()).Kind(), f(x), xs); }
This keeps working with the abstract types all the way through the fold operation. A few things to notice compared to the original implementation:
empty() has .Kind() called on it, that turns Seq into K
The updated cons function now has to convert bs to a Seq (using .As()) for each item – this is converting an interface to a struct (Seq is a value-type).
Once the Cons operation is complete it has to be converted back to the base-interface using Kind()
Ultimately, this has to do multiple boxing operations per item (.As() and .Kind()) which adds more overhead than necessary. And that is why this isn't the default implementation.
It is nearly always the case that when you're traversing a collection-type, like Seq, the applicative type you're mapping to is usually not a collection-type. So, doing the Map operation once (for the outer Applicative) is much more efficient than doing it on every item.
Because collections are a little more involved I wanted to present them first. Now let's look at a simpler example: Either:
// Either Traverse static K, B>> Traverse(Func> f, K, A> ta) => ta switch { Either.Right (var r) => F.Map(Right, f(r)), Either.Left (var l) => F.Pure(Left(l)), _ => throw new NotSupportedException() }; // Helper method to construct `Right` and cast to the underlying K type static K, A> Right(A value) => Either.Right(value); // Helper method to construct `Left` and cast to the underlying K type static K, A> Left(L value) => Either.Left(value);
Other than the constructor functions (Left and Right) this is much simpler and should be easier to follow.
We simply pattern-match on ta which is a K, A> to find out what state the Either is in:
For the Either.Right case we invoke the f transformation function to get a resulting F applicative – we then Map the value within the Applicative and lift it into the Right constructor, leaving us with K>>.
For the Either.Left case we want to shortcut the expression, so we don't call the f transformation function at all and instead lift the Left state into the applicative using F.Pure.
This then captures the Either short-cutting effect in the Traverse operation – we literally don't call the transformation operation at all if we're not in any state to deal with its result.
Sequence
In the previous version of language-ext there were also Sequence extension methods (for all of the types that supported Traverse. Sequence is like calling Traverse with the identity function on an already nested pair of types:
var xs = Seq(Some(1), Some(2), None); // Nested structure var ys = xs.Sequence(); // This line is equivalent var zs = xs.Traverse(x => x); // to this line. // ys == zs
In v5 of language-ext there are three additional methods with default implementations in the Traversable trait, including Sequence:
public static virtual K> Sequence( K> ta) where F : Applicative => Traversable.traverse(x => x, ta); public static virtual K> TraverseM( Func> f, K ta) where M : Monad => Traversable.traverse(f, ta); public static virtual K> SequenceM( K> ta) where F : Monad => Traversable.traverseM(x => x, ta);
Sequence and SequenceM are functionally equal, just one constrains to Applicactive and the other constrains to Monad. TraverseM is the monad equivalent of Traverse.
Mostly, you'd never need to implement these yourself, but there may be some traversable types that could benefit from having bespoke overridden implementations. Specifically, collection types like Seq have TraverseM implemented because it enforces sequential operations – this is useful when the applicative type you're working with is asynchronous: TraverseM enforces a serial evaluation rather than the parallel applicative behaviour – this enables the same functionality as TraverseSerial and TraverseParallel from v4 – but generalises it.
BIG NOTE: Sequence and SequenceM both take already nested types. C# doesn't like this for anything other than the nested K interface types, so Seq> can't be used with Sequence (compile-time error) – only K>; so if you're already in the more abstract space then Seqeunce will work, otherwise not. The workaround is to use Traverse with an identity function: xs.Traverse(x => x) – which works fine. This issue seems to just be a fundamental limitation of C# – it's extremely annoying, but at least there's a workaround.
Converting back to concrete
The result of the Traverse extension method (below) is two nested K types. Getting back to a concrete type isn't easy, because we can't just cast (as we do inside the .As() extension).
public static partial class TraversableExtensions { public static K> Traverse( this K ta, Func> f) where T : Traversable where F : Applicative => Traversable.traverse(f, ta); ... }
Everything that works with the K type will continue to work: so using Map, Apply, etc. will 'just work'. But, obviously we want to get back to our concrete data types to use them...
To make this as painless as possible, I have found that adding a Traverse and TraverseM method to your data-type reduces the complexity of getting back to a concrete state (this is in addition to the trait-implementation of Traverse):
Here's the Traverse and TraverseM implementation for Seq:
public readonly struct Seq{ ... public K> Traverse(Func> f) where F : Applicative => F.Map(x => x.As(), Traversable.traverse(f, this)); public K> TraverseM(Func> f) where M : Monad => M.Map(x => x.As(), Traversable.traverseM(f, this)); ... }
This implementation is pretty much always exactly the same for all types, you just need to replace Seq with whatever type you're implementing. So, copy-n-paste is your friend here.
What this does is map the inner-type to its concrete-type by calling .As() on it. And because this is a member of the Seq type (not an extension method) it gets picked first by C# (ahead of the Traverse and TraverseM extension methods).
It still means we have a generic outer-type (K), but the inner-type (Seq) is now concrete. This is then enough for us to call .As() on to make the whole type concrete:
var items = Seq("1", "2", "3", "X", "5"); Option> values = items.Traverse(s => parseInt(s)).As();
This is a little bit of a rough edge for traversables. It's a bit more effort than the other trait types and less elegant in implementation. However, it does work without any cheating and it does turn into a truly generic system of traversables.
Breaking Changes from v4
The 500 or so extension methods that existed before for Sequence and Traverse are now gone. The methods in the trait implementations have taken over that role. The type signatures are slightly different, with one variant of Sequence removed.
You nearly always want to use Traverse and not Sequence – because C#'s type-system won't play nice with your nested types most of the time. Sequence is useful when the inner nested type is already in K form.
In pre-v5 language-ext there were Traverse extension-methods for types that can't now be supported [with the new fixed trait-interface]. And so, you may get some breaking changes where Traverse doesn't exist any more for a nested-pair of types. In reality this is unlikely, because they didn't really make much sense and were just there for completeness.
TraverseSerial and TraverseParallel are currently deprecated. The parallelisation of the operations are now dependent on the implementation of Traverse only. However, types like Seq also have a TraverseM implementation which enforces serial operations – so you can think of Traverse as parallel and TraverseM as serial.
Because Traverse and Sequence return nested generic-types, it's not possible to make them concrete without having the same number of extension methods as before – so you'll need to call .As() to get back to your concrete type (see previous section).
Conclusion
There's no doubt that there's a couple of rough edges with traversables due to the limitations of the C# type-system. I will keep experimenting with ideas that could help improve that situation – but I won't do any hacks, I want this to use the type-system as it is.
Really, it would be nice to get some parity with the extension methods from v4, namely no issues with nested types and implicit variance casting. Luckily, everything is still totally usable, but the issues around Sequence are a little frustrating.
Even with all of that said, this version now has the bugs in Traverse and Sequence – from v4 – fixed. Because of the trait system, not in spite of it. And, you can now build your own traversable types which will instantly work with all of your foldable & applicative types and the foldable & applicative types in language-ext.
One thing that really frustrated me in the past was creating a type in my app domain that I then wanted to use with Traverse, only to remember that there was no generic traversable trait and that I'd have to implement Traverse and Sequence n-times to get the same functionality as the types in language-ext. That problem has now gone – you still need to implement Traverse for your type, but just once.
When you remember that Traverse is one of the most powerful tools in the pure-functional-programming-toolkit – it means (regardless of rough edges) we've gained some real FP superpowers here. And these superpowers can finally land in your code-base rather than just the language-ext provided types.
Next up: Monads! I promised myself I'd never write 'Yet Another Monad Tutorial' – well I guess I can't not write one now...
Part 7 - Monads.

Higher Kinds in C# with language-ext [Part 5 - validation]

Paul Louth — Sun, 24 Mar 2024 06:59:59 GMT

This is a multi-part series of articles, it's worth going back to the earlier parts if you haven't read them already:
Part 1 - Introduction, traits, semigroups, and monoids
Part 2 - Functors
Part 3 - Foldables
Part 4 - Applicatives
In the last article I introduced the Applicative trait and showed how it can be used to perform operations on 'lifted' values. The benefit of working in the 'lifted' environment is that we don't have to unpack the values, perform the operation, and then repack the values manually – the applicative functor does that for us. It is the same with Functor – we don't have to manually pattern-match the Maybe type, the Either type, or iterate the values in the List type — the functor does that job for us. These techniques are boilerplate removers!
But, where does the 'lifted' vernacular come from?
Take a look at Diagram 1 below. At the bottom of the diagram is a blue arrow linking A to B (which I will write A → B). The label f represents a single argument function that takes any value of type A and returns a value of type B – it's a Func.
Diagram 1
At the top of the diagram is an equivalent of A → B but with an outer F wrapping. This is the applicative-functor F. With functor F we can map F to F using the function F – which is F>.
If you remember from, the last article, the Apply function looks like this:
K Apply(K> mf, K ma)
It should be fairly obvious that we can project K → K using K> – which maps to the top section of the diagram above. What we're doing when we Apply is to do the equivalent of f.Invoke(a) where f is a regular delegate; but we're invoking for something with additional structure (Maybe, List, Either, ...). So, Apply is just Invoke for lifted structures.
Again, 'lifted', why lifted? Well, the etymology isn't entirely clear, but I believe that it's simply because when drawn out in diagram form (as above), the lifted elements are literally above the others. It is also the origin of 'higher' in higher-kinds.
It's fascinating that none of the Wikipedia references for lifting – whether it's category-theory or functional-programming related – specifies the etymology. If you have a reference to the etymology, or a better understanding of its mathematical origins, I'd be very interested to see it!
Even if my definition isn't the true etymology, this is how I like to think of it. We lift simple values and functions into a 'higher space'. And we try, as much as possible, to work in that higher-space; only coming back down when we have a concrete and robust way of doing so. For example, if you have a Maybe – only come back down to string when you have a meaningful default for the Nothing case. Otherwise, continue the optional computation in its higher-space using Map, Apply, etc.
The orange/vertical arrow in Diagram 1 is the process of lifting in action. The Map function in Functor lifts a – 'lower' – Func function and makes it into a 'higher' lifted function that can be applied to values of F. You can think of Map as both the operation to lift the function and the application of the argument (Apply). Whereas Apply will only work with pre-lifted functions.
If we put some real types in there then it becomes a little less abstract and slightly more obvious what's really going on.
Diagram 2
There seems to be a couple of arrows missing from the diagram however. If we can lift a function from being just a function to being an embellished function. Can we do the same with int → Maybe and string → Maybe?
Yes, we can:
Diagram 3
The two new arrows are gained from the Pure function that's part of the Applicative trait. So, with Pure and Map we are able to lift anything we want from being a regular value or function and make them into embellished values and functions.
I'm saying 'embellished' to mean 'giving extra capabilities to'. So, Maybe is an int with an optionality embellishment!
In diagram form functors and applicative-functors become quite tame – there isn't any great mystery behind them, they're simply mechanisms that allow us to continue working in a lifted space. This drawing of arrows between types is the essence of Category Theory and is much simpler than the name sounds.
So, now that I've explained the complete interface for Applicative, let's look at another concrete usage of applicatives: Validation.
Validation is definitely part of the 'awkward squad', it's never trivial to build validation into any application. It always seems trivial on the surface, but doing it well, isn't.
Let's try and validate a credit-card and associated details using the language-ext built-in Validation type. Then we can dissect how and why it works...
First, let's create the data model for what we expect the result of validating a credit-card to be:
// Credit care number public record CardNumber(Seq Number); // Expiry date public record Expiry(int Month, int Year); // CVV code public record CVV(int Number); // Complete credit card details public record CreditCardDetails(CardNumber CardNumber, Expiry Expiry, CVV CVV) { public static CreditCardDetails Make(CardNumber cardNo, Expiry expiry, CVV cvv) => new (cardNo, expiry, cvv); }
I realise these are declared as records and therefore we can't control their construction; but it reduces the amount of code I need to write here! You might want to protect their construction with classes instead.
We have a card-number which holds the 16 digit credit-card number, an expiry-date in Month/Year format, a 3 digit CVV number, and a composition of all of those types, making CreditCardDetails. Pretty simple.
Let's start with the simplest item, the CVV number. The rules are:
Must be all digits
Must be 3 digits in length
Part of the power of writing pure functional code is its powerful composition. Meaning we can build complex things from simple things. So, let's start with some simple things:
static Validation CharToDigit(char ch) => ch is >= '0' and <= '9' ? Pure(ch - '0') : Fail(Error.New($"expected a digit, but got: {ch}"));
Ok, so we take a char, check that it's one of the digit characters and if so, we return Pure(ch - '0') – Pure should have meaning to you now as the function that lifts values.
Because this is C# and C#'s type inference is awful, Pure actually constructs the type Pure. This can be seen as an intermediate value until the type-system has enough information to infer. At the point of construction the function Pure(...) knows nothing about Error, meaning we'd have to specify it. However, later, an implicit conversion can happen fromPure to Validation and we don't need to specify the Error type.
If the value isn't a digit, then we call Fail – which works a bit like Pure but for failure values. It constructs the type Fail (where E is the error-type).
There are some circumstances where, even with this technique, Pure and Fail don't resolve – and so the alternative is to directly construct the Validation value you need. For example:
static Validation CharToDigit(char ch) => ch is >= '0' and <= '9' ? Validation.Success(ch - '0') : Validation.Fail(Error.New($"expected a digit, but got: {ch}"));
Hopefully it's clear why Pure and Fail are so useful. It's much more elegant. All of the core types in language-ext support implicit conversion from Pure and Fail (and have SelectMany overrides so they can work in LINQ expressions also).
Anyway, back to the validation! We have a simple function that validates whether a char is a digit and, if so, it converts it to an int – otherwise it fails with a useful error message.
If we try it out:
CharToDigit('x'); CharToDigit('1');
We will get this output:
Fail(expected a digit, but got: x) Success(1)
Which is exactly what we want!
The CVV code is multiple digits though; so let's start leveraging the power of pure functional composition to check that all of the characters are digits:
static Validation> ValidateAllDigits(string value) => value.AsIterable() .Traverse(CharToDigit) .As();
This converts the string to an Iterable, traverses each item, running the conversion.
Iterable is a more advanced version of IEnumerable – it supports: Functor, Foldable, Traversable, Applicative, Monad, SemigroupK, and MonoidK – so it's like IEnumerable on steroids!
Let's try ValidateAllDigits :
ValidateAllDigits("xy123"); ValidateAllDigits("123");
This outputs:
Fail([expected a digit, but got: x, expected a digit, but got: y]) Success([1, 2, 3])
Notice how we get two errors returned for "xy123" – it is picking up both x and y as invalid digit characters and informing us of both issues.
This automatic tracking of multiple errors is enabled by the applicative capability of the Validation type. We'll dissect that later.
Now that we can prove all the of the characters in the string are digits, we can provide a wrapper function that maps the value to an int.
static Validation ValidateInt(string value) => ValidateAllDigits(value).Map(_ => int.Parse(value));
We don't bake this into the ValidateAllDigits function, because when we test the card-number later we won't convert it to an int. This gives us two functions that validate, one of which maps the value.
I won't test this, because it's obvious it will work!
Ok, so we can now test that the CVV is a multidigit value, but we haven't asserted that it's exactly three digits in length. Just to show off, let's do length validation for any foldable:
static Validation> ValidateLength(K fa, int length) where F : Foldable => fa.Count() == length ? Pure(fa) : Fail(Error.New($"expected length to be {length}, but got: {fa.Count()}"));
This leverages the built-in Count() extension for foldables.
But, because string isn't a foldable, let's create a version that turns the string into a foldable so it can be validated:
static Validation ValidateLength(string value, int length) => ValidateLength(value.AsIterable(), length) .Map(_ => value);
This is obviously overkill, but whatever, we're enjoying ourselves!
Time to test it:
ValidateLength("xy123", 3); ValidateLength("123", 3);
Which outputs:
Fail(expected length to be 3, but got: 5) Success(123)
Hopefully, you're also starting to see how easy this stuff is to test. These components are all pure and have no external moving parts – making testing trivial.
So, now we have the components to assert our spec for the CVV code:
Must be all digits
Must be 3 digits in length
Let's compose them together:
static Validation ValidateCVV(string cvv) => fun((code, _) => new CVV(code)) .Map(ValidateInt(cvv)) .Apply(ValidateLength(cvv, 3)) .As();
Here we start to see the standard applicative pattern start to emerge: a chain of Map follow by Apply – it's something that becomes very familiar after a while.
Let's try it out:
ValidateCVV("xy123"); ValidateCVV("123");
It outputs:
Fail([expected a digit, but got: x, expected a digit, but got: y, expected length to be 3, but got: 5]) Success(123)
We're collecting all of the errors! It's really starting to look more like the kind of output you'd see from a compiler. This is really powerful stuff.
This is all using the built-in Error type. A more advanced solution to this would be to create a bespoke error type that captures context better than raw text messages. For example, the errors could all be grouped together and displayed much better than repeating the same "expected a ..." text.
Now we have the CVV validator, let's look at the expiry date. Our rules will be:
Must be in the format ['\' | '/' | '-' | ' '] – some examples:
12-2024
01/2025
06 2029
The first part (the month) must be an integer from 1 – 12
The second part must be:
A four digit integer
Equal to this year or a year in the next 10
We already have the ValidateInt function from earlier, we can re-use that.
The next thing we're going to need is to check whether the parts of the date (the month and the year) are in range. The range is from now to ten years in the future. Dates are a little tricky, so instead of making the validator too complex, let's extend the Expiry type to act like a complex number that we can do range based operations on:
// Expiry date public record Expiry(int Month, int Year) : IAdditionOperators, IComparisonOperators { public static readonly Expiry OneMonth = new (1, 0); public static Expiry operator +(Expiry left, Expiry right) { var m = left.Month + right.Month; var y = left.Year + right.Year; while (m > 12) { m -= 12; y++; } return new Expiry(m, y); } public static bool operator >(Expiry left, Expiry right) => left.Year > right.Year || left.Year == right.Year && left.Month > right.Month; public static bool operator >=(Expiry left, Expiry right) => left.Year > right.Year || left.Year == right.Year && left.Month >= right.Month; public static bool operator <(Expiry left, Expiry right) => left.Year < right.Year || left.Year == right.Year && left.Month < right.Month; public static bool operator <=(Expiry left, Expiry right) => left.Year < right.Year || left.Year == right.Year && left.Month <= right.Month; public static Expiry Now { get { var now = DateTime.Now; return new Expiry(now.Month, now.Year); } } public static Range NextTenYears => LanguageExt.Range.fromMinMax(Now, Now + new Expiry(0, 10), new Expiry(1, 0)); }
I won't go into too much detail on that because it's pretty regular C#. But, the things to note are that it now supports the addition operator that understands how to add months and years. And it can do comparisons that take into account the month and year correctly. Finally, it exposes a language-ext Range that is from Now to 10 years from now.
That NextTenYears range is what we will validate against...
Let's create a general range validator:
static Validation ValidateInRange(A value, Range range) where A : IAdditionOperators, IComparisonOperators => range.InRange(value) ? Pure(value) : Fail(Error.New($"expected value in range of {range.From} to {range.To}, but got: {value}"));
It takes a value and a range and tests if the value is within the range. Let's test it:
ValidateInRange(new Expiry(10, 2024), Expiry.NextTenYears); ValidateInRange(new Expiry(2, 2034), Expiry.NextTenYears); ValidateInRange(new Expiry(10, 2034), Expiry.NextTenYears); ValidateInRange(new Expiry(1, 2023), Expiry.NextTenYears);
It outputs:
Success(10/2024) Success(2/2034) Fail(expected value in range of 3/2024 to 3/2034, but got: 10/2034) Fail(expected value in range of 3/2024 to 3/2034, but got: 1/2023)
Nice! It's always better if you can make a complex pairing like month and year work together in a single value-type. Of course we could have leveraged DateTime but this is more precise and declarative.
Now let's compose that into something that validates a month and a year string:
static Validation ValidateExpiryDate(string expiryDate) => expiryDate.Split(['\\', '/', '-', ' ']) switch { [var month, var year] => from my in ValidateInt(month) & ValidateInt(year) let exp = new Expiry(my[0], my[1]) from _ in ValidateInRange(exp, Expiry.NextTenYears) select exp, _ => Fail(Error.New($"expected expiry-date in the format: MM/YYYY, but got: {expiryDate}")) };
This is a little bit harder to parse. First we spit the expiryDate string. We are expecting two parts, so we pattern match to extract the month and year parts. If the match fails then we yield an explanatory error.
We then call ValidateInt twice. One for month and one for year. They are composed using the & operator. When you find that all terms of an Apply expression yield the same type then you can use & or | to check for any errors. & will collect the results of the operands into a Seq (if all are successful), whereas | will continue if either operand is successful, but if both fail then it will collect all of the errors.
NOTE: The | operator works slightly differently in v5 compared to v4. v4 was closer to the & behaviour. So, when migrating it is worth finding all usages of Validation and migrating | to &.
That means my is a Seq if both the month and the year validate as integers. We can then create a new Expiry and check that the expiry date is within the valid range.
Let's test...
ValidateExpiryDate("10-2024"); ValidateExpiryDate("02-2034"); ValidateExpiryDate("10/2034"); ValidateExpiryDate("1/2023"); ValidateExpiryDate("1X2023"); ValidateExpiryDate("02-F00");
It outputs:
Success(10/2024) Success(2/2034) Fail(expected value in range of 3/2024 to 3/2034, but got: 10/2034) Fail(expected value in range of 3/2024 to 3/2034, but got: 1/2023) Fail(expected expiry-date in the format: MM/YYYY, but got: 1X2023) Fail(expected a digit, but got: F)
Yeah, this is good! Meaningful validation output.
Now we need to validate the main credit-card number, here's the final function:
static Validation ValidateCardNumber(string cardNo) => (ValidateAllDigits(cardNo), ValidateLength(cardNo, 16)) .Apply((digits, _) => digits.ToSeq()) .Bind(ValidateLuhn) .Map(digits => new CardNumber(digits)) .As();
We've already seen the ValidateAllDigits and the ValidateLength validators, what we haven't seen is Apply used on a tuple of Validation types. This is an alternative approach to calling Apply – for some circumstances it's more elegant as you don't need to provide the type-signature of the lambda.
NOTE: Sometimes the tuple-based Apply doesn't pass the C# type-checker. The Apply methods extend (K, F, ...) and it seems sometimes C# doesn't want to coerce the value to its underlying interface – I'm not sure the exact rules around this, I will dig some more, but if you face this problem you can just chain the Map and Apply functions as seen in the examples up to now.
ValidateLuhn is also called sequentially using the monadic Bind operation. We'll discuss monads in a later article – but just know that Bind operation runs after we've validated that the card-number is 16-digits in length.
What about ValidateLuhn – what does it do? Let's look at it:
static Validation> ValidateLuhn(Seq digits) { int checkDigit = 0; for (int i = digits.Length - 2; i >= 0; --i) { checkDigit += ((i & 1) is 0) switch { true => digits[i] > 4 ? digits[i] * 2 - 9 : digits[i] * 2, false => digits[i] }; } return (10 - checkDigit % 10) % 10 == digits.Last ? Pure(digits) : Fail(Error.New("invalid card number")); }
This is an implementation of the Luhn algorithm, which is essentially a check-sum for credit-card numbers. It makes sure the person who typed it in didn't make a mistake. I haven't modified it much from the version on the Wikipedia page, I've simply made it accept a Seq and return a Validation depending on whether the check-sum succeeds or not. So, I won't dwell on this implementation too much.
It does however mean that ValidateCardNumber should check that each character is a digit, that the length of the digits is 16 characters, and that the digits pass the Luhn algorithm check-sum. Let's try it:
ValidateCardNumber("4560005094752584"); ValidateCardNumber("00000"); ValidateCardNumber("000000000000000x"); ValidateCardNumber("0000000000000000x");
It outputs:
Success([4, 5, 6, 0, 0, 0, 5, 0, 9, 4, 7, 5, 2, 5, 8, 4]) Fail(expected length to be 16, but got: 5) Fail(expected a digit, but got: x) Fail([expected a digit, but got: x, expected length to be 16, but got: 17])
The credit card number is a fake btw!
So, we have all of the component parts now. We should be able to do the final validator:
public static Validation Validate(string cardNo, string expiryDate, string cvv) => fun(CreditCardDetails.Make) .Map(ValidateCardNumber(cardNo)) .Apply(ValidateExpiryDate(expiryDate)) .Apply(ValidateCVV(cvv)) .As();
Here we get to see the pure functional composition really starting to open up. I really love seeing this stuff. We have combined small components (like digit-validators, integer-validators, range-validators, etc. into larger components, like ValidateCardNumber, ValidateExpiryDate, and ValidateCVV. And now, we get to compose those bigger components into an even bigger component.
It's pure all the way down! It's robust and error free all the way down! It's turtles all the way down! These things stick together like Lego – once you've built your core components then they all stack up beautifully.
Let's do the final test:
Validate("4560005094752584", "12-2024", "123"); Validate("00000", "00-2345", "XYZ");
It outputs:
Success(CreditCard([4, 5, 6, 0, 0, 0, 5, 0, 9, 4, 7, 5, 2, 5, 8, 4], 12/2024, 123)) Fail([expected length to be 16, but got: 5, expected value in range of 3/2024 to 3/2034, but got: 0/2345, expected a digit, but got: W, expected a digit, but got: X, expected a digit, but got: Y, expected a digit, but got: Z])
That all works exactly as it should, we have lots of errors that show at a fine-grained level what the issues were with the credit-card details. The thing is, maybe it's too fine-grained? Do we really care about individual digits being letters? Are the error messages descriptive enough? I'd say "no". We can do better.
When we're parsing a char to see if it's a digit we have no idea that it's part of a CVV code or card-number, so we can't give context. But we can add that context higher up the stack: This is where MapFail comes in. It allows you to take an error and provide more context higher up the stack where you have it.
Here's a version of ValidateCVV which overrides the simpler errors messages and provides something contextual:
static Validation ValidateCVV(string cvv) => fun((code, _) => new CVV(code)) .Map(ValidateInt(cvv).MapFail(_ => Error.New("CVV code should be a number"))) .Apply(ValidateLength(cvv, 3).MapFail(_ => Error.New("CVV code should be 3 digits in length"))) .As();
You could do other things like create Error hierarchies where the inner-errors hold the more fine-grained errors and they're wrapped in a more contextual error. This can be great for debugging purposes – where you want to carry the raw info but also give friendly errors to end-users.
For example, if we take the ValidateCardNumber from earlier and use MapFail:
static Validation ValidateCardNumber(string cardNo) => (ValidateAllDigits(cardNo), ValidateLength(cardNo, 16)) .Apply((digits, _) => digits.ToSeq()) .Bind(ValidateLuhn) .Map(digits => new CardNumber(digits)) .As() .MapFail(e => Error.New("card number not valid", e));
The final MapFail there will capture any failure and wrap it up in a new error that simply has the message "card number not valid" – but it carries the details in its Inner property.
If we run the test from before with these new changes:
Validate("00000", "00-2345", "WXYZ")
We get:
Fail([card number not valid, expected value in range of 3/2024 to 3/2034, but got: 0/2345, CVV code should be a number, CVV code should be 3 digits in length])
So now we have 4 errors, each explaining clearly what the problem is, but there is also some inner errors that give even more context if needed. Nice!
All of this behaviour is enabled by applicatives. If you remember from the last article the IO monad was able to run things in parallel (in its Apply function). It was leveraging the fact that it could wait for the successful result of two operations before applying the values. Validation works the opposite way, it waits for the failure results of two operations and combines them.
Here is the Apply trait implementation for Validation:
static K, B> Applicative>.Apply( K, Func> mf, K, A> ma) => mf switch { Validation.Success> (var f) => ma switch { Validation.Success (var a) => Validation.Success(f(a)), Validation.Fail (var e) => Validation.Fail(e), _ => Validation.Fail(FAIL.Empty) }, Validation.Fail> (var e1) => ma switch { Validation.Fail (var e2) => Validation.Fail(e1 + e2), _ => Validation.Fail(e1) }, _ => Validation.Fail(FAIL.Empty) };
If you follow the pattern-match through the two Validation.Fail cases, you'll see it calls e1 + e2 which are the two error values being combined into one.
The other thing to note is that Validation can have any value for its FAIL case as long as it's a Monoid (go back to the first article in this series for a reminder about monoids). So, if you want to implement a bespoke error type then make sure you make it monoidal.
Ok, so this article definitely went on longer than I expected! I did feel it was important to really see the benefits of the applicative-functor approach though – because I think it's a trait that gets overlooked quite often – mostly because it's not as pretty as functors and monads, but the compositional power of applicatives should not be ignored!
Because there's a lot of code in this article I've uploaded it all to a sample in the language-ext repo for your convenience.
Next up, traversables...

Higher Kinds in C# with language-ext [Part 4 - applicatives]

Paul Louth — Tue, 12 Mar 2024 10:00:24 GMT

This is a multi-part series of articles, it's worth going back to the earlier parts if you haven't read them already:
Part 1 - Introduction, traits, semigroups, and monoids
Part 2 - Functors
Part 3 - Foldables
Let's now look at the next trait-type: Applicative. Or, to give it its full name: Applicative Functor...
Applicative Functors are a 'stepping stone' between functors and monads – they're probably less well-known but have some interesting properties of their own when it comes to lifted expression evaluation. Two of the major uses in language-ext is to enable automatic parallel processing of effectful computations and to automatically collect multiple errors when validating. Those aren't the only usages – all of the higher-kinded-types, including the collection-types, have the applicative traits.
If we take a look back at Functor, it has a single method in its trait: Map. Map takes a regular function Func and allows it to run on the bound-values within the functor, effectively making a Func into a Func, F>.
For example, if I have an A then a Func will get me a B. This is basic stuff. But, if I have one or more A values within an F, I want to be able to apply the Func to the bound values to transform them: that's what Map does. It means that every function that's ever been written to work with single values of A can now work with any type that is a 'container' of zero or more values of A.
So, for List we get to turn it into a List by applying Func with Map.
The function passed to map has a single argument - it's a unary operation. So, simple operations like this are easily achievable:
// Simple unary function static bool Not(bool x) => !x; // Mapping of a list of booleans var xs = new List([true, false, true]); var ys = xs.Map(Not); // Mapping a boolean Maybe var mx = new Just(true); var my = mx.Map(Not);
What happens if we want to do a binary operation? How would we achieve that?
Let's take a look at a simple mathematical expression:
1 × 2 + 3 × 4
What if the operands weren't just pure values, but were instead lifted up into a Maybe?
Just(1) * Just(2) + Just(3) * Just(4)
Could we still operate on those values without losing the semantics of the Maybe structure – namely that the values are optional?
If the values were int? then we may write some code like this:
int? w = ...; int? x = ...; int? y = ...; int? z = ...; if(w.HasValue && x.HasValue && y.HasValue && z.HasValue) { return w.Value * x.Value + y.Value * z.Value; } else { return null; }
Plenty of boilerplate and plenty of opportunities to make a mistake.
WARNING: This next section is becomes a bit of a mindfuck before it gets good. Stick with it!
With Maybe what could we do? So far, we've only got support for Map and Fold behaviours. Map takes unary function arguments, but we have binary functions (+ and ×), how can we make them unary? Simply, we can curry them:
// Binary addition function static int Add(int x, int y) => x + y; // Binary multiplication function static int Multiply(int x, int y) => x * y; // Curry the functions var add = curry(Add); // (int x) => (int y) => x + y var multiply = curry(Multiply); // (int x) => (int y) => x * y
Currying creates a series of nested lambdas rather than a single 'tuple' lambda. This allows us to partially apply our arguments to the functions.
var add10 = add(10); // Func var result = add10(20); // 30
Partial application allows us to progressively feed values into the function without the need to collect all of the argument the values upfront.
Let's now create the four terms of our expression:
var mw = new Just(1); var mx = new Just(2); var my = new Just(3); var mz = new Just(4);
And then start multiplying with Map:
K> r1 = mw.Map(multiply);
What we end up here is the value inside mw being partially applied to the multiply function – it returns a function that gets wrapped back up inside a Maybe> – if we can just supply one more argument then we have the first multiplication expression done:
var r2 = r1.Map(f => mx.Map(f)); // K>
So, we call Map on r1 (which has a Func inside), we then pass that to mx.Map – which completes the multiplication operation.
But, we have problem! We want our Map operation to be int → int, we were not expecting another Maybe to be returned. However, because of our nesting of Mapoperations we cause the final r2 result to be two nested maybes. This isn't good!
If we take it further and try to do the full expression: 1 x 2 + 3 x 4 then it gets worse!
var lhs = mw.Map(multiply).Map(f => mx.Map(f)); var rhs = my.Map(multiply).Map(f => mz.Map(f)); var res = lhs.Map(l => l.Map(add).Map(f => rhs.Map(r => r.Map(f))));
Would you like to guess what res is? You got it:
K>>> res; // Ouch!
Four nested maybes! So, not only do we not have the result we want, it's truly horrible to write. We need a better solution, we need applicative functors!
public interface Applicative : Functor where F : Applicative { public static abstract K Pure(A value); public static abstract K Apply(K> mf, K ma); }
Take a look at the Apply function signature. Does is remind you of anything? Let's take a look at Functor again:
public interface Functor where F : Functor { public static abstract K Map(Func f, K ma); }
By the way, I am now using the definition from language-ext, where K is the last argument in the argument-list for Map.
Both Map and Apply look almost exactly the same. The only difference is that the Func is also lifted in the applicative Apply function (i.e. it's wrapped up in a K).
But, if you look at the, earlier, first step of trying to partially-apply the mulitply function:
K> r1 = mw.Map(multiply);
Then you'll notice that it too is a Func that is lifted into the Maybe structure. Looks like we might be on something here!
Let's implement Applicative for Maybe:
public class Maybe : Foldable, Applicative { public static K Pure(A value) => new Just(value); public static K Apply(K> mf, K ma) => mf switch { Just> (var f) => ma switch { Just(var a) => new Just(f(a)), Nothing => new Nothing() }, Nothing> => new Nothing() }; public static K Map(Func f, K ma) => ma switch { Just (var x) => new Just(f(x)), Nothing => new Nothing() }; public static S FoldWhile( Func> f, Func<(S State, A Value), bool> predicate, S state, K ta) => ta switch { Just (var x) when predicate((state, x)) => f(x)(state), _ => state }; public static S FoldBackWhile( Func> f, Func<(S State, A Value), bool> predicate, S state, K ta) => Fold(s => a => f(a)(s), state, ta); }
I have implemented the traits as they exist in language-ext. So, you'll notice the new implementation of Map reflects the interface in language-ext, rather than the implementations from the earlier articles. Additionally, you should see that Fold and FoldBack are now FoldWhile and FoldWhileBack – these are the actual abstract methods used in the language-ext interface: it allows for more optimal default implementations of the other trait methods, like Exists, ForAll, IsEmpty, etc.
Let's look at the implementation of Apply:
public static K Apply(K> mf, K ma) => mf switch { Just> (var f) => ma switch { Just(var a) => new Just(f(a)), Nothing => new Nothing() }, Nothing> => new Nothing() };
It's a simple nested pattern-match that tries to extract the Func from mf and the A from ma. If either of them are in a Nothing state then we get Nothing returned. Which makes sense – we can't invoke the function if we don't have the function or if we don't have the argument to pass to the function.
But, if both mf and ma are in a Just state then we can simply invoke the function and then wrap it back up inside a Maybe by passing the result to the constructor for Just.
Let's update our extension methods to allow us to use the new applicative Apply method. We'll also add a new Map extension with the arguments flipped (I mentioned in an earlier episode that I would demonstrate why the arguments are flipped – you're about to see why it works this way):
// Functor map (notice that `this` is a `Func`) public static K Map(this Func f, K ma) where F : Functor => F.Map(f, ma); // Applicative apply public static K Apply(this K> mf, K ma) where F : Applicative => F.Apply(mf, ma);
If you remember our first attempt at multiplying two Maybe values together looked like this:
var r = mw.Map(multiply).Map(f => mx.Map(f));
And that resulted in a nested Maybe>. Instead, we can now use the Apply function (along with the flipped-argument Map) to avoid the nesting:
var r = multiply.Map(mw).Apply(mx) // K
And that works! Returning a K rather than the double-nested maybe we saw earlier. The flipped-argument Map function also allows us to move the function-argument to the left-most position in the expression, it is then followed by n arguments that are fluently fed into the function. This just reads better.
For those that know Haskell, you'll recognise this technique. In Haskell it would look like this:
let r = multiply <$> mw <*> mx
I would love to be able to use operators to make this a little more elegant in C#, but operators can't be parametrically polymorphic and so the only way is to use this fluent style.
If you have functions with even more arguments then you can simply chain more calls to Apply and it will just work.
Now lets do the applicative-version of the imperative nullable-expression from earlier:
var lhs = multiply.Map(mw).Apply(mx); var rhs = multiply.Map(my).Apply(mz); var res = add.Map(lhs).Apply(rhs);
It is more concise than the imperative version, it's less error prone, and it supports every single applicative type ever written. So, we can run this with Either, Option, Seq, etc.
It's not quite as easy to read which is definitely the downside to using applicatives in C#. Most applicatives are also monads and monads (in C#) are 'LINQ friendly'. Which means we could have just written:
var res = from w in mw from x in mx from y in my from z in mz select w * x + y * z;
It's probably easier to read and doesn't need any special currying of functions. So, what is it that applicatives have over monads? Namely, monads are about sequential operations – we can only get each operand of the final expression in-sequence, first the w, then the x, then the y, then the z, then we return the result (if all succeeded). If any fail we return immediately and don't process the rest.
Applicatives however do not have sequential processing semantics. In fact, they're the opposite.
Let's take a look at the earlier mathematical expression in tree form. We can see that there are two main branches that are entirely independent of each other. We could calculate the left-hand-side in-parallel to the processing of the right-hand-side before applying the values to the addition function.
Because applicatives get access to both their function and its argument at the same time, they're able to follow a strategy where the operands are calculated independently.
You can see this in the Apply implementation for IO effect type:
public static IO Apply(this IO> ff, IOfa) => from tf in ff.Fork() from ta in fa.Fork() from f in tf.Await from a in ta.Await select f(a);
Notice how it forks both the function IO and the argument IO. That means they can run in parallel whilst further down the expression awaits both IO operations to complete. If you use functions with more arguments (and therefore chain more Apply calls) then each argument runs in parallel and the final function invocation only occurs when all arguments have been acquired.
And so, applicatives enable automatic parallelisation of effectful computations. No need to manually write code to do threaded coordination.
Here's a simple example. Let's first get three asynchronous IO operations:
var io1 = liftIO(() => File.ReadAllTextAsync(path1)); var io2 = liftIO(() => File.ReadAllTextAsync(path2)); var io3 = liftIO(() => File.ReadAllTextAsync(path3));
And some function that wants to use the result of those operations:
var concat = (string txt1, string txt2, string txt3) => txt1 + txt2 + txt3;
Next we map and apply the IO computations. These three IO operations will now all run in parallel and collect their results before invoking the concat function.
IO res = concat.Map(io1).Apply(io2).Apply(io3);
You might be thinking "but, you didn't curry the concat function first!". You're right, because language-ext has Map and Apply overrides that will deal with that automatically for multi-argument delegates. The overrides simply curry the function for you before invoking the regular Map and Apply methods.
Another thing to note with the above expression is that Map is called on the function – and so it doesn't get forked; only io1, io2, and io3 get forked. That means we're not launching pointless parallel processes to acquire the function (which would normally be available already).
Note the real-world Apply implementation for IO is quite a bit more complex because of how IO has been implemented as a DSL and the optimisations put in place to avoid async when it's not needed. It doesn't use Fork and instead unpacks Task values and uses Task.WhenAll. The theory is the same though. IO concurrency happens automatically with the applicative Apply behaviour.
Applicatives are a little hard to get your head around at first – but they are incredibly powerful. Even if you don't need the more 'hierarchal' behaviour (as opposed to the sequential behaviour of monads) they can – in the right circumstance – be very concise and elegant. However, in C# it isn't always the case, so it's best to pick your battles and use them when you need their unique capabilities or when the resulting code will be more elegant.
This article is a little long now – I still haven't explained the Pure method in Applicative and I wanted to cover how applicatives can be used for validation – but I think I'll dedicate a separate article to that so I can give some more real-world examples.
Part 5 – Validation

Higher Kinds in C# with language-ext [Part 3 - foldables]

Paul Louth — Sat, 02 Mar 2024 11:42:12 GMT

This is a multi-part series of articles, it's worth going back to the earlier parts if you haven't read them already:
Part 1 - Introduction, traits, semigroups, and monoids
Part 2 - Functors
And "yes", this time the artwork is my own. And whilst I'm no Kandinsky, he's not as good at functional-programming as me, so I guess we're even!
In part two we showed that by defining a separate trait-implementation type we could make a data-type (like List and Maybe) into a functor. Functors require higher-rank polymorphism to work, and we made it work. Yay!
Let's just do one more Functor type: Either. Either is a little more interesting, because it has two generic-parameters, whereas List and Maybe have only one.
// Data-types public abstract record Either : K, R>; public record Left(L Value) : Either; public record Right(R Value) : Either; // Trait implementation public class Either : Functor> { public static K, B> Map(K, A> either, Func f) => either switch { Left (var l) => new Left(l), Right (var r) => new Right(f(r)) }; } // Extensions that provides the down-casting public static class EitherExtensions { public static Either As(this K, R> ma) => (Either)ma; }
It should be relatively clear now that the trait-implementation should just have the last generic parameter removed. So, Either becomes Either, Maybe becomes Maybe, etc.
If you think about it, this is a little bit like how partial-application works with functions. But, because C# won't allow us to partially apply Either by just providing the L – we need a second type that is partially-applied. That second type completes its application, not by getting all of its arguments from the type, but by moving the final argument from the type-signature to the method-signatures.
The methods within the partially-applied trait-implementation provide the final argument. This is the key to the technique.
Let's look at another higher-kind now: Foldable. Foldables are aggregators. There are usually two methods: Fold and FoldBack – sometimes called FoldRight and FoldLeft, but in language-ext we use the Fold and FoldBack parlance.
For, the uninitiated, Fold is the same as Aggregate in LINQ (first item to last item aggregation); FoldBack is like doing the aggregation in reverse: last item to first.
When you consider this generally: folding applies a binary-operator over the values within the structure. For example, Fold looks like this:
((((a * s) * b) * c) * ...)
And FoldBack is this:
(a * (b * (... * (z * s))))
The * operator is a placeholder operator for the f binary-function passed to Fold and FoldBack. a, b, c, and z represent values in the foldable-structure and s represents an intial-state. So, the operation gets 'seeded' with s and depending on the precedence applied with the binary-operator we get Fold and FoldBack.
The trait looks like this:
public interface Foldable where T : Foldable { public static abstract S Fold(K ta, S initial, Func f); public static abstract S FoldBack(K ta, S initial, Func f); }
And, just like Select before, we can add our one-and-only implementation of the Fold and FoldBack extension methods:
public static class FoldableExtensions { public static S Fold(this K ta, S initial, Func f) where T : Foldable => T.Fold(ta, initial, f); public static S FoldBack(this K ta, S initial, Func f) where T : Foldable => T.FoldBack(ta, initial, f); }
Now we can get the three trait types we've made so far List, Maybe, and Either and make them foldable...
List
public record List : Functor, Foldable { public static K Map(K xs, Func f) => new List(xs.As().Items.Select(f).ToArray()); public static S Fold(K xs, S initial, Func f) => xs.As().Items.Aggregate(initial, f); public static S FoldBack(K xs, S initial, Func f) => xs.As().Items.AsEnumerable().Reverse().Aggregate(initial, f); }
Maybe
public class Maybe : Functor, Foldable { public static K Map(K ma, Func f) => ma switch { Just (var x) => new Just(f(x)), Nothing => new Nothing() }; public static S Fold(K ma, S initial, Func f) => ma switch { Just (var x) => f(initial, x), Nothing => initial }; public static S FoldBack(K ma, S initial, Func f) => Fold(ma, initial, f); }
Either
public class Either : Functor>, Foldable> { public static K, B> Map(K, A> ma, Func f) => ma switch { Left (var l) => new Left(l), Right (var r) => new Right(f(r)) }; public static S Fold(K, A> ma, S initial, Func f) => ma switch { Left => initial, Right (var r) => f(initial, r), }; public static S FoldBack(K, A> ma, S initial, Func f) => Fold(ma, initial, f); }
We still haven't modified the List, Maybe, or Either types directly. We're just extending the set of capabilities via the trait-implementations.
When we made our types into functors, they gained the ability to Map, but nothing else really. So, it was a fair amount of typing to apparently not get much in return. Foldable is quite different. Let's see what we can give any type that implements Foldable.
First up, let's count the items in any foldable:
public static int Count(this K ta) where T : Foldable => ta.Fold(0, (s, _) => s + 1);
And test it:
var mx = new Nothing(); var my = new Just(100); var mz = new List([1, 2, 3, 4, 5]); var c1 = mx.Count(); // 0 var c2 = my.Count(); // 1 var c3 = mz.Count(); // 5
So we just gave all foldables some additional (useful) functionality without touching the original types or traits. These can be used in any generic function that works with foldables.
Can we do more?
Let's sum the items in any foldable, with any numeric bound-value:
public static A Sum(this K ta) where T : Foldable where A : INumber=> ta.Fold(A.Zero, (s, x) => s + x);
And test it:
var mx = new Nothing(); var my = new Just(100); var mz = new List([1, 2, 3, 4, 5]); var c1 = mx.Sum(); // 0 var c2 = my.Sum(); // 100 var c3 = mz.Sum(); // 15
We could also see if any foldable is empty:
public static bool IsEmpty(this K ta) where T : Foldable => ta.Fold(true, (_, _) => false);
If the bound-value type is monoidal then we can use that to aggregate using the monoid's associative operator:
public static A Fold(this K ta) where T : Foldable where A : Monoid=> ta.Fold(A.Empty, (s, x) => s + x);
We can convert any foldable into an IEnumerable:
public static IEnumerableAsEnumerable(this K ta) where T : Foldable { var list = new System.Collections.Generic.List(); return ta.Fold(list, (s, x) => { s.Add(x); return s; }); }
We can implement more of the standard LINQ operators (without 'magic methods'):
// Returns true if the predicate holds for all items public static bool All(this K ta, Func f) where T : Foldable => ta.Fold(true, (s, x) => s && f(x)); // Returns true if the predicate holds for any item public static bool Any(this K ta, Func f) where T : Foldable => ta.Fold(false, (s, x) => s || f(x));
And we can check if a known item is within any foldable structure:
public static bool Contains(this K ta, A value) where A : IEquatablewhere T : Foldable => ta.Any(x => x.Equals(value));
These functions are written just once. And they work for List, Maybe, and Either automatically. They will also work for any foldable you write! Yay, free code!
Now, some of the more performance minded individuals reading this might think "Er, but these methods do more work than they need to". And, you'd be right. For example, the IsEmpty method has to traverse every item in the foldable, even though we would know on the first item if it's empty or not. Count traverses every item also, yet List has an internal representation that is an array – it knows how many items there are without walking the collection.
We fix this by moving these methods into Foldable and making them default implementations that can be overridden where desired.
New Foldable trait:
public interface Foldable where T : Foldable { // Abstract members that everyone has to implement public static abstract S Fold(K ta, S initial, Func f); public static abstract S FoldBack(K ta, S initial, Func f); // Virtual members with useful default implementations public static virtual bool IsEmpty(K ta) => T.Fold(ta, true, (_, _) => false); public static virtual int Count(K ta) => T.Fold(ta, 0, (s, _) => s + 1); public static virtual A Sum(K ta) where A : INumber => T.Fold(ta, A.Zero, (s, x) => s + x); public static virtual A Fold(K ta) where A : Monoid => T.Fold(ta, A.Empty, (s, x) => s + x); public static virtual IEnumerable AsEnumerable(K ta) { var list = new System.Collections.Generic.List(); return ta.Fold(list, (s, x) => { s.Add(x); return s; }); } public static virtual bool All(K ta, Func f) => T.Fold(ta, true, (s, x) => s && f(x)); public static virtual bool Any(K ta, Func f) => T.Fold(ta, false, (s, x) => s || f(x)); public static virtual bool Contains(K ta, A value) where A : IEquatable => T.Any(ta, x => x.Equals(value)); }
Note, how the methods we've moved into Foldable are static virtual – which means we can override them in our trait-implementations. But, if we don't, we still get the free functionality. The default implementations happen to be pretty optimial for Maybe and Either – they could be better, but's probably not worth the effort to provide hand-written overrides; but for List we should definitely do some manual overrides if we want to get the best performance.
Updated List trait-implementation with optimised overrides:
public record List : Functor, Foldable { public static K Map(K xs, Func f) { // Optimises by pre-allocating the array before mapping var items = xs.As().Items; var bs = new B[items.Length]; var ix = 0; foreach(var item in items) { bs[ix] = f(item); ix++; } return new List(bs); } public static S Fold(K xs, S state, Func f) { // Optimises by running as a simple imperative for-loop foreach(var item in xs.As().Items) { state = f(state, item); } return state; } public static S FoldBack(K xs, S state, Func f) { // Optimises by running an imperative for-loop backwards var items = xs.As().Items; for (var ix = items.Length - 1; ix >= 0; ix--) { state = f(state, items[ix]); } return state; } public static bool IsEmpty(K ta) => // Optimises by using the known length of the array ta.As().Items.Length == 0; public static int Count(K ta) => // Optimises by using the known length of the array ta.As().Items.Length; public static IEnumerable AsEnumerable(K ta) => // Optimises by passing the array back directly ta.As().Items; public static bool All(K ta, Func f) { // Optimises by turning into a simple loop that can bail out early foreach (var item in ta.As().Items) { if (!f(item)) return false; } return true; } public static bool Any(K ta, Func f) { // Optimises by turning into a simple loop that can bail out early foreach (var item in ta.As().Items) { if (f(item)) return true; } return false; } }
What's really nice about this is that we can 'get moving' and write our code to leverage these higher-kinded types and gain all of this functionality and then come back later to provide more optimal solutions. The definition of not optimising prematurely.
We should update the extension methods to use these new trait methods too. Here's the full set of extensions so far:
public static class FoldableExtensions { public static K Select(this K fa, Func f) where F : Functor => F.Map(fa, f); public static K Map(this K fa, Func f) where F : Functor => F.Map(fa, f); public static S Fold(this K ta, S initial, Func f) where T : Foldable => T.Fold(ta, initial, f); public static S FoldBack(this K ta, S initial, Func f) where T : Foldable => T.Fold(ta, initial, f); public static bool IsEmpty(this K ta) where T : Foldable => T.IsEmpty(ta); public static int Count(this K ta) where T : Foldable => T.Count(ta); public static A Sum(this K ta) where T : Foldable where A : INumber=> T.Sum(ta); public static A Fold(this K ta) where T : Foldable where A : Monoid => T.Fold(ta); public static IEnumerable AsEnumerable(this K ta) where T : Foldable => T.AsEnumerable(ta); public static bool All(this K ta, Func f) where T : Foldable => T.All(ta, f); public static bool Any(this K ta, Func f) where T : Foldable => T.Any(ta, f); public static bool Contains(this K ta, A value) where A : IEquatable where T : Foldable => T.Contains(ta, value); }
It is clear from this approach that we don't have to forego performance to leverage more abstract compositional capabilities. These methods will be as fast as any handwritten code and yet we can write abstract functions that work with any foldables and any functors; yet when they're consumed they run the highly optimised trait implementations, not some generic code that has no understanding of the underlying type.
Contrast that with IEnumerable, which, once your collection-type has been cast to from its concrete type, like List, to its abstract representation of IEnumerable, instantly becomes opaque – with the only access to the underlying type being its ability to yield an enumerator. Yet, we have a ton of extension methods hanging off the type that are completely clueless to what's underneath. There are no such issues with the higher-kinds + traits approach!
On the Haskell wiki is what's known as the 'Typeclassopedia'. So far, we've covered:
Semigroup
Monoid
Foldable
Functor
and mentioned in passing: Applicative and Traversable
Can you guess where we're going next?
Part 4

Higher Kinds in C# with language-ext [Part 2 - functors]

Paul Louth — Thu, 29 Feb 2024 11:27:10 GMT

In part 1 of this series I introduced the type K and left you all hanging with the promise that it would bring higher-kinded traits to C#. So, let's dig in a little to see how it works.
Firstly, you'll recall (from part 1) that we couldn't implement Mappable – using the traits technique – because it baked-in the bound-value type: A and didn't allow us to map to a new bound-value type of B.
So, it should be clear that a type like List can't ever inherit a trait that bakes in the A. If we want to implement an generic version of Select we need a Mappable trait that has no A.
Let's try that:
public interface Mappable where F : Mappable { public static abstract F Select(Flist, Func f); }
But, we already know we can't use: F and F – where F would be List and A and B would be the bound-value type of the items in the list. Why? Because C# doesn't support higher kinds!
What we can do though is use the new language-ext type: K revealed in the last article:
public interface Mappable where F : Mappable { public static abstract K Select(K list, Func f); }
This allows us to use F as an 'anchor' for an another type that will help us understand something about the structure of the 'mappable thing'.
If you haven't worked it out yet – K is short for Kind. I wanted to keep the type concise because it's needed a lot and I want the focus to be on the generic parameters, not the type-name. You'll see why this is important when we start filling in the generic parameters with concrete types.
First, let's create a simple list type:
public record List(A[] Items) : K;
Notice, how it inherits: K – but we don't have a type called List, just List. List is the type that will implement the Mappable trait – let's start to make it:
public class List : Mappable { public static K Select(K list, Func f) { throw new NotImplementedException(); } }
OK, that's looking very interesting! We have a K that maps to a K. If you look back at the implementation of List you'll see that it inherits a K – so we can downcast a K knowing it's a List:
public class List : Mappable { public static K Select(K list, Func f) => new List(((List)list) .Items .Select(f) .ToArray()); }
And that works! We have a general case Mappable implementation for List.
The casting is a little ugly though, so let's add a simple extension method to do the downcast:
public static class ListExtensions { public static ListAs(this K ma) => (List)ma; }
Now, we can remove the cast from the implementation:
public class List : Mappable { public static K Select(K list, Func f) => new List(list.As().Items.Select(f).ToArray()); }
And everything starts to look really elegant.
Seasoned developers might wince at the down-casting, but we should only ever derive one type from K – so it must be a List. Obviously, if you did something silly and derived two types from K then you'd get a failure on first usage, so it's not really a systemic risk to your code if you make a mistake. I'm OK with this.
We can then take that further, by creating the – one and only – Select extension method. Yes, you only need to write this extension once!
public static class MappableExtensions { public static K Select(this K fa, Func f) where F : Mappable => F.Select(fa, f); }
And, that's it – the extension method to end all extension methods. We can now use that like any other LINQ extension. And it will work for all types that implement Mappable:
var list = new List([1, 2, 3]); var nlist = list.Select(x => x + 1) .Select(x => x * 2);
As long as your data-type inherits K and you have a sibling type that implements Mappable then you will automatically gain the Select LINQ operator.
K creates the hook to a higher-kinded trait type: F that allows us to parameterise with any type we want in place of A.
Now the downside. In the last example, Select returns a K - not a List. So, whilst we're able to chain many Select calls together, we can't assign the result directly to List. But, we can use our downcast method to do that!
List nlist = list.Select(x => x + 1) .Select(x => x * 2) .As();
This isn't ideal, of course, but it has a tiny overhead – it's just casting after all – and it's not too intrusive. The only way to avoid this is for the C# team to add higher-kinds proper (or allow implicit casting of interfaces – that's another discussion!); but for now this works and gives us all of the same benefits.
One thing I've noticed, as I build out this capability in language-ext, is how little I am needing to call .As() – because if you stay in the 'abstract state' then you can continue to rely on the higher-kinded extensions to 'just work'. It's only when you need to go back to a concrete value that .As() is needed.
Let's try implementing another Mappable type:
public abstract record Maybe: K; public record Just(A Value) : Maybe; public record Nothing() : Maybe;
Here we create a simple discriminated-union type called Maybe that has two states: Just and Nothing.
It's the same as Option in language-ext, I just wanted to keep the example separate for now. Just is Some and Nothing is None.
Now, let's create the trait-implementing Maybe type:
public class Maybe : Mappable { public static K Select(K maybe, Func f) => maybe switch { Just(var x) => new Just(f(x)), Nothing => new Nothing() }; }
And add the downcast extension:
public static class MaybeExtensions { public static MaybeAs(this K ma) => (Maybe)ma; }
Now we can leverage the – already existing – Select extension method:
var mx = new Just(100); var my = new Nothing(); var r1 = mx.Select(x => x + 1) .Select(x => x * 3); // Just(303) var r2 = my.Select(x => x + 1) .Select(x => x * 3); // Nothing
You may think "So what? We could do this with extension methods and only have to write 1 method for each type." – what we couldn't do is write generic functions that work with any Mappable type; we'd have to implement Foo(Maybe mx), Foo(List mx), etc.
Now we can write those functions once:
public static K Foo(K ma) where F : Mappable => ma.Select(x => x.Length);
Those of you that have been paying attention will notice that Mappable is, of course, a Functor! Yes, I realise this was hardly the reveal of the century, but for those of you who are relatively new to functional programming, terms like Functor might be a bit too much to take in whilst learning about a new technique for higher kinds! Now when you hear "Functor" just think "Mappable".
Anyway, Mappable is Functor and Select should be called Map. Let's do that:
public interface Functor where F : Functor { public static abstract K Map(K fa, Func f); }
If we put our definition of Functor side-by-side with the Haskell definition of Functor – because Haskell is a language that has higher-kinds, traits, and probably has done more to promote this style of abstract programming than any other language...
class Functor f where fmap :: (a -> b) -> f a -> f b
You might notice a striking similarity!
Functor f == Functor
f a == K
f b == K
(a -> b) == Func
They're not just strikingly similar – but, barring the order of the arguments, they're exactly the same!
In the final version in language-ext, even the order of the arguments is the same. I will go into the reasons for that in a later article.
OK, so it's worth stopping to reflect right now – is this really higher-rank polymorphism? My answer to that is "100% yes!". Are there some compromises? Yeah, some, but they're pretty mild for what we gain. It is true that this isn't using lambda-abstractions in the type-system, so it's not completely general like Haskell, but it does generalise correctly for traits, which is what matters the most.
It's also worth remembering that our original data-types haven't been modified at all.
// List public record List(A[] Items) : K; // Maybe public abstract record Maybe : K; public record Just(A Value) : Maybe; public record Nothing() : Maybe;
All of the 'action' is in the trait implementation types: List and Maybe. This is very similar to how class-instances work in Haskell (class instances are implementations of type-classes – i.e. traits). You create a data-type that represents the 'shape' and the trait-implementations represent the 'capability' – this is a nice separation of concerns and leaves the data-type being a pure structure that can travel anywhere. This simplifies parallel processing and serialisation/deserialisation.
The primary difference for us, in C#, is the need for the data-type to derive from K – this is unavoidable, brings some limitations, but still allows us to build very powerful generic code.
One way to mentally process this (especially if you've never spent time in a language with higher-kinds) is imagine C# without generics – those of you who have been programming C# from v1.0 won't find that very hard to imagine! – could you imagine having a type-less List that only took object? Could you imagine the code explosion as you need to write 100 functions (all doing basically the same thing) for different types? Well, when you step up another rank with your generics, you gain a similar leap in power.
A perfect example is the implementations of Traverse and Sequence in language-ext v4 – I have written over 400 functions and over 1200 unit-tests by hand (actually, I got some help from the community – thank you, community!) that all do the same thing, but with different types. And guess what, if you decide to write a type that should be traversable – it won't work with any of the language-ext traversables or applicatives, you'd have to write n variants of traverse yourself. All because we can't write this type: T> – where the T is Traversable and F is an Applicative.
In v5 I can write: K> which allows for a single implementation of Traverse per type written (i.e. you implement your Traversable trait, once, like with Functor). And, if you decide to write a traversable or applicative type, it will automatically work with the traversable and applicative types in language-ext: you're not just limited to what I can provide in the library any more. True extensibility.
But that's for a later, we need to build up to that! I think that's enough for part 2. It's worth trying to digest the implications of this approach before moving on. Obviously Functor is a rather trivial type – so it may appear that we don't get a lot from this, but you'll quickly see how this technique gives us functional programming super powers!
In Part 3 we look at foldables!

Higher Kinds in C# with language-ext [Part 1]

Paul Louth — Tue, 27 Feb 2024 10:01:53 GMT

Those who have been following the language-ext repo will know that I am building up to a really massive version 5 release. I am looking at the release notes that I have been trying to keep up to date as I go and they're already up to nearly 1000 lines of text. And although there's quite a lot of content, there's also 100s of lines of just headings (waiting for the content)! So, the final release notes are going to be huge and a lot to take in.
Version 5 of language-ext is about as close to a rewrite as it's ever going to get. So there's a lot to cover.
Rather than have a big surprise on day 1 of the release, I figured I'd keep language-ext in a v5-beta state for longer (it is stable now, so prefer it over v4 if you're starting fresh) and in parallel I am starting this blog series to try and prepare the ground and whet the appetite somewhat. I also want terrify you enough that you upgrade with caution!
Note also that language-ext is getting more and more refinements to the ideas laid out in this series of articles and so apologies if some of the examples don't work as stated. I will do my best to review this series at regular intervals to make sure it's up to date – feel free to message me through the language-ext repo if you spot any issues.
Traits
A recent C# feature is static interface members – this opens up some new possibilities for bending C# to make trait like functionality work. You may have already seen the technique:
public interface Addable where SELF : Addable { public static abstract SELF Add(SELF x, SELF y); }
Note, how the Add member is static abstract and that the interface has a constraint that SELF is forced to inherit Addable, meaning this trait can't stand alone (i.e. be ad-hoc like in other languages).
We can then create two distinct types that inherit the Addable trait:
public record MyList(A[] values) : Addable> { public static MyList Add(MyList x, MyList y) => new (x.values.Concat(y.values).ToArray()); } public record MyString(string value) : Addable { public static MyString Add(MyString x, MyString y) => new (x.value + y.value); }
They both inherit Addable and pass themselves as the argument to construct the concrete Addable implementation.
We can then create a function that adds anything – as long a the type is Addable:
A AddAnything(A x, A y) where A : Addable => A.Add(x, y);
And now we can call AddAnything with either one of the list types we made:
var mx = new MyList([1, 2, 3]); var my = AddAnything(mx, mx); // [1, 2, 3, 1, 2, 3] var nx = new MyString("Hello"); var ny = AddAnything(nx, nx); // "HelloHello"
You may think: "so what, we could create addable interfaces before?" – and you'd be right. But, the difference here is that the static members don't need an instance. So, now we can do this:
public interface Addable where SELF : Addable { public static abstract SELF Empty { get; } public static abstract SELF Add(SELF x, SELF y); }
We've added an Empty property that presumably returns the 'zero' value for for SELF.
Now we can extend our types:
public record MyList(A[] values) : Addable> { public static MyList Empty { get; } = new ([]); public static MyList Add(MyList x, MyList y) => new (x.values.Concat(y.values).ToArray()); } public record MyString(string value) : Addable { public static MyString Empty { get; } = new(""); public static MyString Add(MyString x, MyString y) => new (x.value + y.value); }
With that we can write some more general functions that work with Addable values. First, we'll create FoldMap which iterates over a sequence of values, mapping them into Addable values, and then aggregating them as it goes using Add:
B FoldMap(IEnumerablexs, Func f) where B : Addable { var r = B.Empty; foreach (var x in xs) { r = B.Add(r, f(x)); } return r; }
Once we have that we can write a general concatenation function:
A Concat(IEnumerable xs) where A : Addable => FoldMap(xs, x => x);
And so we've managed to generalise folding and concatenation (for completely distinct types) in a way that wasn't possible before in C# (other than with the ad-hoc polymorphism trick leveraged in language-ext v4, but let's ignore that for now as it's not particularly attractive as a technique) .
Another major improvement is the return types from the members are the concrete value and not a (potentially boxed) Addable – which has been a classic problem of using interfaces in C#.
The eagle-eyed amongst you will recognise that the Addable structure is a Monoid. In fact a Semigroup does 'adding' (in reality any associative binary operation) and a Monoid inherits Semigroup and extends it with an identity element (Empty).
So, let's refactor Addable:
public interface Semigroupwhere A : Semigroup { public static abstract A operator+ (A x, A y); } public interface Monoid : Semigroup where A : Monoid { public static abstract A Empty { get; } }
This is the first major change in language-ext v5. Semigroups and Monoids are now types that you must inherit to make something into a semigroup or monoidal. You can see the new implementations here and here.
The big problem here is that we can't make types, that we don't own, into semigroups and monoids. That is, we don't have ad-hoc polymorphism. And so, we can't make string monoidal, or integers, or any type that is not under our control.
However, we can use the technique I have already shown above, of wrapping up an existing type in a small container type that does have the traits we need. It necessitates a small conversion step at the point of monoidal-usage, but other than that, it's relatively painless, if not entirely elegant.
This decision is a major shift from the ad-hoc polymorphism approach of earlier versions of language-ext. I believe it's the pragmatic decision that leads to more elegant code. The slightly less elegant part is when using types that don't belong to you, but I feel the trade is the right one.
Monoids are relatively simple types, what about something more complex? Could we make Select from LINQ into something more concrete and not a hack in the compiler?
Let's try the same trait-like technique from before, let's call the trait Mappable for no apparent reason (some of you will know where I'm going with this!):
public interface Mappable where SELF : Mappable { public static abstract SELF Select(SELF list, Func f); }
If we try to implement this everything goes wrong. We can't get the X in the array and transform it into an A to give to the mapping function f:
public record MyList(X[] values) : Mappable> { public static MyList Select(MyList list, Func f) => // Can't map an X to an A }
What if we remove the A argument from Select and instead embed it in the trait:
public interface Mappable where SELF : Mappable { public static abstract SELF Select(SELF list, Func f); }
It gets us closer, but now the A is baked into the return type of Select:
public record MyList(A[] values) : Mappable, A> { public static MyList Select(MyList list, Func f) => new(list.values.Select(f).ToArray()); } // ^^^ MyList doesn't type check
The problem now is that the A is baked into the trait, everything must work with A – so even the most basic mapping of values within a collection cannot be achieved with C#.
And the reason that this can't be done is because C# doesn't have higher-kinded types...
What are higher kinds?
Simply, higher-kinded types are types that are parameterised by other types. Option is a lower-kinded type, because it is entirely concrete. Option is a higher-kinded type, because it has a parameter A that can be used to construct a new type (like Option, Option, etc.)
If you think of types like functions, it's a function that takes one argument (a type) and returns a result (a type). These are the fundamentals of generics.
Obviously, we already have this capability in C#, so why am I trying so hard to get higher-kinds into C#? Well, it's the generalisation of the principle of parameterisation that is desired. That is, if we can make the A in Option a parameter, why can't we make the Option part a parameter: F ? This isn't allowed in C#. And, it's really needed!
It's not just that I want to add functors, applicatives, and monads to our ecosystem. The C# compiler itself is crying out for higher-kinds...
There are loads of 'magic functions' in the language: Select, SelectMany, Where, Join, GroupJoin, GetEnumerator, GetAwaiter, Add (on collections that implement IEnumerable), index initialisers [this], the new collection initialisers...
There are more of these magic functions, but I have forgotten them all – which highlights a major problem with this 'magic' approach – total lack of discoverability. The magic functions are all hacks by the C# language team to bring in higher-kinded – ad-hoc – traits into C# without doing the heavy-lifting of making it an actual feature that we can all use.
It seems each time the C# team needs higher-kinds – as evidenced by these magic functions – they just hack the compiler and leave the rest of us wanting. I find this really sad, because it's clear there's a need and they won't address it.
K
This is the most important new type in language-ext v5. It may possibly turn out to be the most impactful type ever added to language-ext.
This is the entirety of its definition:
public interface K;
Say what? How can a type, that has no members at all, be so important? Well, it allows:
For the removal of 300,000 lines of generated and hand-written code that tried to give the impression of generalised traits.
It allows users to write their own functors, applicatives, traversables, foldables, monads, and monad-transformers that all gain default behaviours written for those traits-implementations.
Namely, it allows for higher-rank polymorphism – higher kinds.
That's enough for part 1. For the rest of this story, check out for part 2!
Don't you just hate it when there's a cliffhanger like that at the end of an episode? This isn't Twin Peaks or something, it's not like you're desperate to find out who killed Laura Palmer – you just want to know how to do higher-kinds in C# – This is how binges happen!

Notes from a Small Functional Island

Paul Louth — Sun, 25 Feb 2024 18:27:19 GMT

Welcome to my new blog and content site for all things related to pure functional programming in C# (and probably some other languages too). I will obviously be focusing mostly on tutorials, guides, and general commentary about my language-ext project; but I will also take a look at the philosophy of software engineering to try and get a deeper understanding of why pure functional programming is so effective.
Things will be up and running here shortly, but you can subscribe in the meantime if you'd like to stay up to date and receive emails when new content is published! The site is hosted by me, so you're not giving away your personal details to some megacorp.
However, I'm sure you appreciate that creating content here as well as the rather sizeable efforts I put into building language-ext takes up a substantial amount of my time. So, if you like what you see here or you're generally finding language-ext to be something worth rewarding, I would definitely appreciate a subscription. That is optional though, so don't feel like you have to!
If you're wondering about the name 'Notes from a Small Functional Island', it's a play on the excellent, and hilarious, Bill Bryson book: 'Notes from a Small Island' about his journey around the UK before he moved back home to America. As I am from the UK, it seems like a fitting title!
Bill Bryson - Notes from a Small Island [affiliate link]
Subscribe
This site is an independent publication launched in February 2024 by Paul Louth. If you subscribe today, you'll get full access to the website as well as email newsletters about new content when it's available. Your subscription makes this site continue to exist. Thank you!
Fresh content, delivered
Stay up to date with new content sent straight to your inbox! No more worrying about whether you missed something because of a pesky algorithm or news feed.