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

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<Seq<string>> readAllLines(string path) =>
    liftIO(env => File.ReadAllLinesAsync(path, env.Token))
        .Map(toSeq);

static Option<string> validatePath(string path) =>
    Path.IsPathRooted(path) && Path.IsPathFullyQualified(path)
        ? Some(path)
        : None;

One function returns the IO<A> monad, which represents side-effects. The other returns an Option<A> – 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<M, B> Bind<A, B>(K<M, A> ma, Func<A, K<M, B>> 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<A> or Option<A> we could work with IO<Option<A>>:

var computation = from op in IO.Pure(validatePath(path))
                  from r  in op.Match(Some: readAllLines,
                                      None: () => IO.Fail<Seq<string>>(Errors.None))   
                  select r;

By lifting the Option returning validatePath into the IO monad we get a IO<Option<string>>, but that just means op is a Option<string> 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<A> and Option<A> – can be achieved (in language-ext) using the OptionT<IO, A> 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<Seq<string>

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<OptionT<IO>, Seq<string>>(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<IO, A> is recreate OptionAsync<A> (now removed from language-ext) without writing any new code. We could also use OptionT<Eff, A> to have a more advanced version with proper error handling, or Validation<IO, A> 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<T, M>

public interface MonadT<T, out M> : Monad<T> 
    where T : MonadT<T, M>
    where M : Monad<M>
{
    public static abstract K<T, A> Lift<A>(K<M, A> ma);
}

Notice the constraints on T and M:

• T is constrained to be itself like all traits. Itself is also a Monad<T>
• M is constrained to be a Monad<M>

We inherit Monad<T> 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<M<A>> – but in our world we're working with the following type: K<T, K<M, A>>

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<Env, A> from ReaderT<Env, Identity, A> and Option<A> from OptionT<Identity, A>, 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<A> type, from the last article, then we'd create a new type called MaybeT<M, A> – the transformer provides the standard optional behaviour of Maybe but augments it with the M monad that is lifted into it.

public record MaybeT<M, A>(K<M, Maybe<A>> runMaybeT) : K<MaybeT<M>, A>
    where M : Monad<M>
{
    // members to come...
}

public static class MaybeTExtensions
{
    // Standard downcast but with Monad constraint on M
    public static MaybeT<M, A> As<M, A>(this K<MaybeT<M>, A> ma) 
        where M : Monad<M> =>
        (MaybeT<M, A>)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<A> – but that's enough – we know how Maybe<A> 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<M> trait implementation:

public class MaybeT<M> : MonadT<MaybeT<M>, M>
    where M : Monad<M>
{
   // 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 methods (Lift and MapM) but it also inherits: Monad, Applicative, and Functor so we have to implement them all!

First, Functor:

public partial class MaybeT<M> : MonadT<MaybeT<M>, M>
    where M : Monad<M>
{
    static K<MaybeT<M>, B> Functor<MaybeT<M>>.Map<A, B>(Func<A, B> f, K<MaybeT<M>, A> ma) =>
        new MaybeT<M, B>(
            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<M, Maybe<B>> which we can use to construct a new MaybeT<M, B>.

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<MaybeT<M>, A> Applicative<MaybeT<M>>.Pure<A>(A value) =>
    new MaybeT<M, A>(M.Pure(Maybe.Just(value)));

static K<MaybeT<M>, B> Applicative<MaybeT<M>>.Apply<A, B>(K<MaybeT<M>, Func<A, B>> mf, K<MaybeT<M>, A> ma) => 
    mf.As().Bind(x => ma.As().Map(x));

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<M, Maybe<A>>.

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.

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.

Now, Monad:

static K<MaybeT<M>, B> Monad<MaybeT<M>>.Bind<A, B>(K<MaybeT<M>, A> ma, Func<A, K<MaybeT<M>, B>> f) =>
    new MaybeT<M, B>(
        ma.As().runMaybeT.Bind(mx =>
            mx switch
            {
                Just<A> (var x) => f(x).As().runMaybeT,
                Nothing<A>      => M.Pure(Maybe.Nothing<B>())
            }));

This is a little bit more complex. The reason for the complexity is that the f argument returns a MaybeT<M, B> – 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<A>), we then pattern-match on the Maybe<A>, if the result is a Just<A> we get the A value and pass it to the bind function: f - which returns a MaybeT<M, A>. We know that MaybeT<M, A> has a property which is a K<M, ...> type and that's what the bind function wants in return! If the result is Nothing then we can lift a new Nothing<B> 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<MaybeT<M>, A> MonadT<MaybeT<M>, M>.Lift<A>(K<M, A> ma) =>
    new MaybeT<M, A>(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<A>. 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<M>
{
    public static MaybeT<M, A> lift<A>(Maybe<A> ma) =>
        new(M.Pure(ma));

    public static MaybeT<M, A> Just<A>(A value) =>
        lift(Maybe.Just(value));

    public static MaybeT<M, A> Nothing<A>() =>
        lift(Maybe.Nothing<A>());
}

As well as:

public class MaybeT
{
    public static MaybeT<M, A> lift<M, A>(K<M, A> ma)
        where M : Monad<M> =>
        new (ma.Map(Maybe.Just));
}

Those will give us the ability to lift either an M<A> or a Maybe<A> 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<IO, Seq<string>> readAllLines(string path) =>
    MaybeT.lift(
        liftIO(async env => await File.ReadAllLinesAsync(path, env.Token))
            .Map(toSeq));

static MaybeT<IO, string> validatePath(string path) =>
    Path.IsPathRooted(path) && Path.IsPathFullyQualified(path)
        ? MaybeT<IO>.Just(path)
        : MaybeT<IO>.Nothing<string>();

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<Seq<string>> readAllLines(string path) =>
    liftIO(async env => await File.ReadAllLinesAsync(path, env.Token))
        .Map(toSeq);

static Maybe<string> validatePath(string path) =>
    Path.IsPathRooted(path) && Path.IsPathFullyQualified(path)
        ? Maybe.Just(path)
        : Maybe.Nothing<string>();

... and lift them ad-hoc:

var computation = from p in MaybeT<IO>.lift(validatePath(path))
                  from r in MaybeT.lift(readAllLines(path))
                  select r;

IO

Because lifting the IO<A> 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<A>, 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.

We can't however create a general MonadIO trait in C#. The problem is that we don't have ad-hoc traits, we have 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<IO, A> and MaybeT<Identity, A> or not. Clearly, the second example doesn't have an IO monad in the stack.

So, LiftIO is a function in the Monad<M> trait, which isn't ideal, but it's the best way I have found to make this work. It has a default implementation which throws an exception. Again, not ideal, but it's an exception that will happen the first time you use liftIO with the type, so I'm not too concerned about that.

This is the default implementation:

public static virtual K<M, A> LiftIO<A>(IO<A> ma) =>
    throw new ExceptionalException(Errors.IONotInTransformerStack);

If we implement that for our MaybeT transformer then we'll get liftIO support:

static K<MaybeT<M>, A> Monad<MaybeT<M>>.LiftIO<A>(IO<A> ma) =>
    new MaybeT<M, A>(M.LiftIO(ma.Map(Maybe.Just)));

It takes an IO<A> to lift. First we map the result of the IO<A> to IO<Maybe<A>>. 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<A> because it is the IO monad!

static K<IO, A> Monad<IO>.LiftIO<A>(IO<A> 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<Unit> writeAllLines(string path, Seq<string> lines) =>
    liftIO(async env => await File.WriteAllLinesAsync(path, lines, env.Token));

static IO<Seq<string>> readAllLines(string path) =>
    liftIO(async env => await File.ReadAllLinesAsync(path, env.Token))
        .Map(toSeq);

static MaybeT<IO, string> validatePath(string path) =>
    Path.IsPathRooted(path) && Path.IsPathFullyQualified(path)
        ? MaybeT<IO>.Just(path)
        : MaybeT<IO>.Nothing<string>();

I've now got two IO functions and one MaybeT<IO, string> 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<M, B> Bind<M, A, B>(
    this K<M, A> ma,
    Func<A, K<IO, B>> f)
    where M : Monad<M> =>
    M.Bind(ma, x => M.LiftIO(f(x).As()));

You can see the call to LiftIO that makes the IO<B> into a K<M, B> (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<A> 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<M, Maybe<A>> Run<M, A>(this K<MaybeT<M>, A> ma) 
    where M : Monad<M> =>
    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<Seq<string>

So, above, we Run the transformer, we get a K<IO, Maybe<Seq<string>> in return, we then Run that and that gets us a Maybe<Seq<string>>. 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. And 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<RT, A> type in language-ext. It has been rewritten to use monad-transformers. It stacks the StateT transformer with IO:

public record Eff<RT, A>(StateT<RT, IO, A> effect) : K<Eff<RT>, 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 StateT and IO.

At the time of writing the following monad-transformers are in language-ext:

• EitherT<L, M, R>
• OptionT<M, R>
• TryT<M, R>
• ValidationT<F, M, R>
• ContT<R, M, A> – exists but still WIP
• IdentityT<M, A>
• ReaderT<E, M, A>
• WriterT<W, M, A>
• StateT<S, M, A>
• Proxy<UOut, UIn, DIn, DOut, M, A>
• RWS<R, W, S, M, A> – coming soon!

By combining these transformers with other monads you can create extremely complex functionality.

Previous versions of language-ext had a number of monadic types that I have since removed:

• TryAsync<A> – can now be represented as TryT<IO, A>
• TryOption<A> – can now be represented as OptionT<Try, A>
• TryOptionAsync<A> – can now be represented as OptionT<TryT<IO>, A>
• OptionAsync<A> – can now be represented as OptionT<IO, A>
• EitherAsync<L, R> – can now be represented as EitherT<L, IO, A>

I have also had requests for ValidationAsync<F, S> over the years. It can now be represented as ValidationT<F, IO, S>. 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<Env, M, A>(Func<Env, K<M, A>> 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<A> it is the layer that talks directly to FoundationDB:

public record Db<A>(StateT<DbEnv, IO, A> runDB) : K<Db, A>
{
    public IO<(A Value, DbEnv Env)> Run(DbEnv env) =>
        runDB.Run(env).As();

    public K<Db, B> MapIO<B>(Func<IO<A>, IO<B>> f) =>
        from e in Db.dbEnv
        from r in f(runDB.Run(e).Map(vs => vs.Value).As())
        select r;

    public K<Db, A> IfFail(Func<Error, Db<A>> OnFail) =>
        from e in Db.dbEnv
        from r in MapIO(io => io.As()
                                .Match(Succ: x => IO.Pure((Value: x, Env: e)), 
                                       Fail: x => OnFail(x).Run(e)).Flatten())
        from _ in Db.put(r.Env)
        select r.Value;

    public static Db<A> LiftIO(IO<A> ma) =>
        new (StateT<DbEnv, IO, A>.LiftIO(ma));

    public static Db<A> operator |(Db<A> ma, Db<A> mb) =>
        ma.IfFail(_ => mb).As();

    public Db<B> Map<B>(Func<A, B> f) =>
        this.Kind().Map(f).As();

    public Db<B> Bind<B>(Func<A, Db<B>> f) =>
        this.Kind().Bind(f).As();
    
    public Db<C> SelectMany<B, C>(Func<A, Db<B>> bind, Func<A, B, C> project) =>
        this.Kind().SelectMany(bind, project).As();
    
    public Db<C> SelectMany<B, C>(Func<A, IO<B>> bind, Func<A, B, C> project) =>
        this.Kind().SelectMany(bind, project).As();

    public static implicit operator Db<A>(Pure<A> ma) =>
        Db.pure(ma.Value).As();
    
    public static implicit operator Db<A>(Fail<Error> ma) =>
        Db.fail<A>(ma.Value);
    
    public static implicit operator Db<A>(Fail<string> ma) =>
        Db.fail<A>(ma.Value);
    
    public static implicit operator Db<A>(Error ma) =>
        Db.fail<A>(ma);
}

Things to note are:

• It wraps StateT<DBEnv, IO, A> – 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<Db, A>
  • We then call the trait implementation for XXX.
  • Then we convert back to Db<A> 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 : Monad<Db>, StateM<Db, DbEnv>
{
    static K<Db, B> Monad<Db>.Bind<A, B>(K<Db, A> ma, Func<A, K<Db, B>> f) =>
        new Db<B>(ma.As().runDB.Bind(x => f(x).As().runDB));

    static K<Db, B> Functor<Db>.Map<A, B>(Func<A, B> f, K<Db, A> ma) => 
        new Db<B>(ma.As().runDB.Map(f));

    static K<Db, A> Applicative<Db>.Pure<A>(A value) =>
        new Db<A>(StateT<DbEnv, IO, A>.Pure(value));

    static K<Db, B> Applicative<Db>.Apply<A, B>(K<Db, Func<A, B>> mf, K<Db, A> ma) =>
        new Db<B>(mf.As().runDB.Apply(ma.As().runDB).As());

    static K<Db, Unit> StateM<Db, DbEnv>.Put(DbEnv value) =>
        new Db<Unit>(StateT.put<IO, DbEnv>(value).As());

    static K<Db, Unit> StateM<Db, DbEnv>.Modify(Func<DbEnv, DbEnv> f) => 
        new Db<Unit>(StateT.modify<IO, DbEnv>(f).As());

    static K<Db, A> StateM<Db, DbEnv>.Gets<A>(Func<DbEnv, A> f) => 
        new Db<A>(StateT.gets<IO, DbEnv, A>(f).As());

    static K<Db, A> Monad<Db>.LiftIO<A>(IO<A> ma) =>
        new Db<A> (StateT<DbEnv, IO, A>.LiftIO(ma));
}

Things to note:

• Everything is simply running the underlying monad-transformer. There is nothing there that is bespoke, we rely entirely on StateT<DbEnv, IO, A> to know what to do. Again, this is basically a wrapper for the transformer and something that can be source-genned in the future.
• Also note the use of the StateM trait. This allows the Db monad to participate in generalised state management. We'll cover that in a later article, but it's worth looking at the functions you gain if you implement this for your type.

So, 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 Db<A> pure<A>(A value) =>
        new (StateT<DbEnv, IO, A>.Pure(value));

    public static Db<A> fail<A>(string error) =>
        fail<A>((Error)error);

    public static Db<A> fail<A>(Error error) =>
        new (StateT<DbEnv, IO, A>.Lift(IO.Fail<A>(error)));

    public static readonly Db<DbEnv> dbEnv = 
        StateM.get<Db, DbEnv>().As(); 
    
    internal static Db<A> gets<A>(Func<DbEnv, A> f) => 
        StateM.gets<Db, DbEnv, A>(f).As();
    
    public static Db<Unit> put(DbEnv env) => 
        StateM.put<Db, DbEnv>(env).As();

    public static Db<A> liftIO<A>(IO<A> ma) =>
        new (StateT<DbEnv, IO, A>.LiftIO(ma));

    internal static Db<A> liftIO<A>(Func<DbEnv, EnvIO, A> f) =>
        dbEnv.Bind(env => IO.lift(envIO => f(env, envIO))).As();

    internal static Db<A> liftIO<A>(Func<EnvIO, A> f) =>
        MonadIO.liftIO<Db, A>(IO.lift(f)).As();

    internal static Db<A> liftIO<A>(Func<DbEnv, EnvIO, Task<A>> f) =>
        dbEnv.Bind(env => IO.liftAsync(async envIO => await f(env, envIO).ConfigureAwait(false))).As();

    internal static Db<A> liftIO<A>(Func<EnvIO, Task<A>> f) =>
        MonadIO.liftIO<Db, A>(IO.liftAsync(async e => await f(e).ConfigureAwait(false))).As();

    static Db<Unit> fdbVersion =
        liftIO(...).Memo();
    
    public static Db<Unit> shutdown =
        liftIO(...);
    
    public static readonly Db<Unit> 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<IFdbDatabase> db =
        gets<IFdbDatabase>(...);

    static readonly Db<IFdbTransaction> transaction =
        gets<IFdbTransaction>(...);
    
    static readonly Db<IFdbReadOnlyTransaction> readOnlyTransaction =
        gets<IFdbReadOnlyTransaction>(...);

    public static Db<A> subspace<A>(string leaf, K<Db, A> ma) =>
        subspace(FdbPath.Relative(leaf), ma);

    public static Db<A> subspace<A>(FdbPath path, K<Db, A> ma) =>
       from t in readOnlyTransaction
       from r in liftIO(...)
       select r;

    public static Db<A> readOnly<A>(FdbPath subspacePath, K<Db, A> ma) =>
        readOnly(subspace(subspacePath, ma));

    public static Db<A> readOnly<A>(K<Db, A> ma) =>
        connect.Bind(_ => liftIO(...));

    public static Db<A> readWrite<A>(FdbPath subspacePath, K<Db, A> ma) =>
        readWrite(subspace(subspacePath, ma));

    public static Db<A> readWrite<A>(K<Db, A> ma) =>
        connect.Bind(_ => liftIO(...));

    public static Db<Slice> get(string name) =>
        liftIO(...);
    
    public static Db<Unit> set<A>(string name, A value) =>  
        liftIO(...);

    public static Db<uint> increment32(string name) =>  
        liftIO(...);
    
    public static Db<ulong> increment64(string name) =>  
        liftIO(...);
}

The Db<A> 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<VerificationId> 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<A> 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<A>(ReaderT<ServiceEnv, IO, A> runService) : K<Service, A>
{
   ...
}

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<A> monad.

It enables code like this:

public static Service<Unit> 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<Unit>(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<A> 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<A> : K<ApiDsl, A>;
public record ApiFail<A>(Error Error) : ApiDsl<A>;
public record ApiDb<A>(Db<A> Action) : ApiDsl<A>;
public record ApiService<A>(Service<A> Action) : ApiDsl<A>;

Notice how two of the cases wrap up Db<A> and Service<A>.

Then I make it into a Functor and add some convenience functions for constructing the cases of the DSL.

public class ApiDsl : Functor<ApiDsl>
{
    static K<ApiDsl, B> Functor<ApiDsl>.Map<A, B>(Func<A, B> f, K<ApiDsl, A> ma) =>
        ma switch
        {
            ApiFail<A>(var error) => new ApiFail<B>(error),
            ApiDb<A>(var action)  => new ApiDb<B>(action.Map(f)),
            ApiService<A>(var action)  => new ApiService<B>(action.Map(f))
        };

    public static Free<ApiDsl, A> fail<A>(Error value) =>
        Free.lift(new ApiFail<A>(value));

    public static Free<ApiDsl, A> db<A>(Db<A> value) =>
        Free.lift(new ApiDb<A>(value));

    public static Free<ApiDsl, A> service<A>(Service<A> value) =>
        Free.lift(new ApiService<A>(value));
}

Now I need to create an Api<A> type that wraps the Free monad (similar to how we do with the transformers):

public record Api<A>(Free<ApiDsl, A> runApi) : K<Api, A>
{
    public Api<B> Map<B>(Func<A, B> f) =>
        this.Kind().Map(f).As();

    public Api<B> Select<B>(Func<A, B> f) =>
        this.Kind().Map(f).As();

    public Api<B> Bind<B>(Func<A, Api<B>> f) =>
        this.Kind().Bind(f).As();
    
    public Api<C> SelectMany<B, C>(Func<A, Api<B>> bind, Func<A, B, C> project) =>
        this.Kind().SelectMany(bind, project).As();
    
    public Api<C> SelectMany<B, C>(Func<A, IO<B>> bind, Func<A, B, C> project) =>
        this.Kind().SelectMany(bind, project).As();

    public static implicit operator Api<A>(Pure<A> ma) =>
        Api.pure(ma.Value).As();
    
    public static implicit operator Api<A>(Fail<Error> ma) =>
        Api.fail<A>(ma.Value);
    
    public static implicit operator Api<A>(Fail<string> ma) =>
        Api.fail<A>(ma.Value);
    
    public static implicit operator Api<A>(Error ma) =>
        Api.fail<A>(ma);
}

Then we create the trait implementation:

public partial class Api : Monad<Api>
{
    static K<Api, B> Monad<Api>.Bind<A, B>(K<Api, A> ma, Func<A, K<Api, B>> f) => 
        new Api<B>(ma.As().runApi.Bind(x => f(x).As().runApi).As());

    static K<Api, B> Functor<Api>.Map<A, B>(Func<A, B> f, K<Api, A> ma) => 
        new Api<B>(ma.As().runApi.Map(f).As());

    static K<Api, A> Applicative<Api>.Pure<A>(A value) =>
        pure(value);

    static K<Api, B> Applicative<Api>.Apply<A, B>(K<Api, Func<A, B>> mf, K<Api, A> ma) =>
        new Api<B>(mf.As().runApi.Apply(ma.As().runApi).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<A> monad:

public partial class Api
{
    public static Api<A> pure<A>(A value) =>
        new (Free.pure<ApiDsl, A>(value));
    
    public static Api<A> fail<A>(Error value) =>
        new (ApiDsl.fail<A>(value));
    
    public static Api<A> fail<A>(string value) =>
        new (ApiDsl.fail<A>((Error)value));
    
    public static Api<A> lift<A>(Db<A> ma) =>
        new (ApiDsl.db(ma));
    
    public static Api<A> readOnly<A>(Db<A> ma) =>
        new (ApiDsl.db(Db.readOnly(ma)));
    
    public static Api<A> readOnly<A>(FdbPath subSpacePath, Db<A> ma) =>
        new (ApiDsl.db(Db.readOnly(subSpacePath, ma)));
    
    public static Api<A> readWrite<A>(Db<A> ma) =>
        new (ApiDsl.db(Db.readWrite(ma)));
    
    public static Api<A> readWrite<A>(FdbPath subSpacePath, Db<A> ma) =>
        new (ApiDsl.db(Db.readWrite(subSpacePath, ma)));
    
    public static Api<A> lift<A>(Service<A> 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<A> and the Service<A> into the Api<A> monad.

Now we can write code:

public static Api<Unit> 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<A> that interacts with the database
• One which is the Service<A> that interacts with third-party services

These are both lifted into the Api<A> 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 IO<A> Run(DbEnv dbEnv, ServiceEnv serviceEnv) =>
        Interpret(dbEnv, serviceEnv, runApi);

    static IO<A> Interpret(DbEnv dbEnv, ServiceEnv serviceEnv, Free<ApiDsl, A> fma)
    {
        return go(fma);
        
        IO<A> go(Free<ApiDsl, A> ma) =>
            ma switch
            {
                Pure<ApiDsl, A>(var value) => 
                    IO.Pure(value),
                
                Bind<ApiDsl, A>(var bind) =>
                    bind switch
                    {
                        ApiFail<Free<ApiDsl, A>> (var e) =>
                            IO.Fail<A>(e),

                        ApiDb<Free<ApiDsl, A>> (var db) =>
                            db.Map(go)
                              .Run(dbEnv)
                              .Map(x => x.Value)
                              .Flatten(),
                        
                        ApiService<Free<ApiDsl, A>> (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<A> and Service<A> 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<A> and Service<A> and then lifted those into another domain-monad that is implemented using the Free monad: Api<A> 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.