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

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<M> 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<M> 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<M, A> Flatten<A>(K<M, K<M, A>> mma)

Flatten takes a nested monad (like Option<Option<A>> or IO<IO<A>>) 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<Maybe, A> Flatten<A>(K<Maybe, K<Maybe, A>> 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<Maybe, A> Flatten<A>(K<Maybe, K<Maybe, A>> mma) =>
    mma switch
    {
        Just<K<Maybe, A>> (var ma) => ma,
        Nothing<K<Maybe, A>>       => new Nothing<A>()
    };

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

Why's that important? Well we can now implement Bind in terms of Flatten and Map:

public static K<Maybe, B> Bind<A, B>(K<Maybe, A> ma, Func<A, K<Maybe, B>> 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<A>).

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<M>, 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<A> – which manages interaction with FoundationDB. It manages state (sub-spaces, connections, etc.), security, and does IO.
• Service<A> – which are for access to 3rd party services, like SendGrid. It tracks resources, security, handles configuration, and does IO.
• Api<A> – 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<A>

Effect: Early termination of computation when in a None state.

// Maybe data-type (same functionality as Option)
public abstract record Maybe<A> : K<Maybe, A>;
public record Just<A>(A Value) : Maybe<A>;
public record Nothing<A> : Maybe<A>;

// Maybe trait implementation
public class Maybe : Monad<Maybe>
{
    public static K<Maybe, B> Bind<A, B>(K<Maybe, A> ma, Func<A, K<Maybe, B>> f) =>
        ma switch
        {
            Just<A> (var x) => f(x),
            Nothing<A>      => new Nothing<B>()
        };

    public static K<Maybe, B> Map<A, B>(Func<A, B> f, K<Maybe, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<Maybe, A> Pure<A>(A value) =>
        new Just<A>(value);

    public static K<Maybe, B> Apply<A, B>(K<Maybe, Func<A, B>> mf, K<Maybe, A> ma) =>
        mf.Bind(ma.Map);
}

Either<L, R>

Effect: Early termination of computation when in a Left state. Left carries a 'failure' value.

// Either data-type
public abstract record Either<L, R> : K<Either<L>, R>;
public record Right<L, R>(R Value) : Either<L, R>;
public record Left<L, R>(L Value) : Either<L, R>;

// Either trait implementation
public class Either<L> : Monad<Either<L>>
{
    public static K<Either<L>, B> Bind<A, B>(K<Either<L>, A> ma, Func<A, K<Either<L>, B>> f) =>
        ma switch
        {
            Right<L, A>(var r) => f(r),
            Left<L, A> (var x) => new Left<L, B>(x) // carries the error through
        };

    public static K<Either<L>, B> Map<A, B>(Func<A, B> f, K<Either<L>, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<Either<L>, R> Pure<R>(R value) =>
        new Right<L, R>(value);

    public static K<Either<L>, B> Apply<A, B>(K<Either<L>, Func<A, B>> mf, K<Either<L>, A> ma) =>
        mf.Bind(ma.Map);
}

Fin<A>

Effect: Exactly the same as Either<Error, A>

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<A> in v4 should be using Fin<A> ('fin' being French for final/finished – synonym for 'result'). This is easier to use than Either<Error, A> as it doesn't require the application of two generic arguments.

// Fin data-type (same functionality as Either<Error, A>)
public abstract record Fin<A> : K<Fin, A>;
public record Succ<A>(A Value) : Fin<A>;
public record Fail<A>(Error Value) : Fin<A>;

// Fin traits
public class Fin : Monad<Fin>
{
    public static K<Fin, B> Bind<A, B>(K<Fin, A> ma, Func<A, K<Fin, B>> f) =>
        ma switch
        {
            Succ<A> (var x) => f(x),
            Fail<A> (var e)=> new Fail<B>(e)
        };

    public static K<Fin, B> Map<A, B>(Func<A, B> f, K<Fin, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<Fin, A> Pure<A>(A value) =>
        new Succ<A>(value);

    public static K<Fin, B> Apply<A, B>(K<Fin, Func<A, B>> mf, K<Fin, A> ma) =>
        mf.Bind(ma.Map);
}

Validation<F, A>

Effect: Early termination of computation when in a Fail state and multiple fail-value aggregation when using applicative Apply.

The main difference between Either<L, R> and Validation<F, A> 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<F, A> : K<Validation<F>, A>
    where F : Monoid<F>;

public record Succ<F, A>(A Value) : Validation<F, A>
    where F : Monoid<F>;

public record Fail<F, A>(F Value) : Validation<F, A>
    where F : Monoid<F>;

// Validation trait implementation
public class Validation<F> : Monad<Validation<F>>
    where F : Monoid<F>
{
    public static K<Validation<F>, B> Bind<A, B>(K<Validation<F>, A> ma, Func<A, K<Validation<F>, B>> f) =>
        ma switch
        {
            Succ<F, A>(var r)  => f(r),
            Fail<F, A> (var x) => new Fail<F, B>(x) // carries the error through
        };

    public static K<Validation<F>, B> Map<A, B>(Func<A, B> f, K<Validation<F>, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<Validation<F>, R> Pure<R>(R value) =>
        new Succ<F, R>(value);

    public static K<Validation<F>, B> Apply<A, B>(K<Validation<F>, Func<A, B>> mf, K<Validation<F>, A> ma) =>
        (mf, ma) switch
        {
            (Succ<F, Func<A, B>> (var f),  Succ<F, A> (var a))  => new Succ<F, B>(f(a)),
            (Fail<F, Func<A, B>> (var e1), Fail<F, A> (var e2)) => new Fail<F, B>(e1 + e2), // aggregates errors
            (Fail<F, Func<A, B>> (var e),  _)                   => new Fail<F, B>(e),
            (_,                            Fail<F, A> (var e))  => new Fail<F, B>(e),
        };
}

Try<A>

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<A>(Func<A> runTry) : K<Try, A>;

// Try extensions
public static class TryExtensions
{
    public static Try<A> As<A>(this K<Try, A> ma) =>
        (Try<A>)ma;

    // Run without catching the exception
    public static A RunUnsafe<A>(this K<Try, A> ma) =>
        ma.As().runTry();

    // Run and catch the exception
    public static Fin<A> Run<A>(this K<Try, A> ma)
    {
        try
        {
            return new Succ<A>(ma.As().runTry());
        }
        catch (Exception e)
        {
            return new Fail<A>(e);
        }
    }
}

// Try traits
public class Try : Monad<Try>
{
    public static K<Try, B> Bind<A, B>(K<Try, A> ma, Func<A, K<Try, B>> f) =>
        new Try<B>(() => f(ma.RunUnsafe()).RunUnsafe());

    public static K<Try, B> Map<A, B>(Func<A, B> f, K<Try, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<Try, A> Pure<A>(A value) =>
        new Try<A>(() => value);

    public static K<Try, B> Apply<A, B>(K<Try, Func<A, B>> mf, K<Try, A> ma) =>
        mf.Bind(ma.Map);
}

Iterable<A>

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<A>(IEnumerable<A> Items) : K<Iterable, A>, IEnumerable<A>
{
    public IEnumerator<A> GetEnumerator() =>
        Items.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() =>
        Items.GetEnumerator();
}

// Iterable extensions
public static class IterableExtensions
{
    public static Iterable<A> As<A>(this K<Iterable, A> ma) =>
        (EnumerableM<A>)ma;
}

// Iterable trait implementation
public class EnumerableM : Monad<EnumerableM>
{
    public static K<Iterable, B> Bind<A, B>(K<Iterable, A> ma, Func<A, K<Iterable, B>> f)
    {
        return new Iterable<B>(Go());
        
        IEnumerable<B> Go()
        {
            foreach (var x in ma.As())
            {
                foreach (var y in f(x).As())
                {
                    yield return y;
                }
            }
        }
    }

    public static K<Iterable, B> Map<A, B>(Func<A, B> f, K<Iterable, A> ma)
    {
        return new Iterable<B>(Go());
        
        IEnumerable<B> Go()
        {
            foreach (var x in ma.As())
            {
                yield return f(x);
            }
        }
    }

    public static K<Iterable, A> Pure<A>(A value) =>
        new Iterable<A>([value]);

    public static K<Iterable, B> Apply<A, B>(K<Iterable, Func<A, B>> mf, K<Iterable, A> ma) =>
        mf.Bind(ma.Map);
}

Reader<Env, A>

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<A> 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<Env, A>(Func<Env, A> runReader) : K<Reader<Env>, A>;

// Reader extensions
public static class ReaderExtensions
{
    public static Reader<Env, A> As<Env, A>(this K<Reader<Env>, A> ma) =>
        (Reader<Env, A>)ma;
    
    public static A Run<Env, A>(this K<Reader<Env>, A> ma, Env env) =>
        ma.As().runReader(env);
}

// Reader trait implementations
public class Reader<Env> : Monad<Reader<Env>>
{
    public static K<Reader<Env>, B> Bind<A, B>(K<Reader<Env>, A> ma, Func<A, K<Reader<Env>, B>> f) =>
        new Reader<Env, B>(env => f(ma.Run(env)).Run(env));
    
    public static K<Reader<Env>, B> Map<A, B>(Func<A, B> f, K<Reader<Env>, A> ma) =>
        new Reader<Env, B>(env => f(ma.Run(env)));

    public static K<Reader<Env>, A> Pure<A>(A value) =>
        new Reader<Env, A>(_ => value);

    public static K<Reader<Env>, B> Apply<A, B>(K<Reader<Env>, Func<A, B>> mf, K<Reader<Env>, 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<Env, A> asks<Env, A>(Func<Env, A> f) =>
        new (f);

    // Gets the environment out of the Reader 
    public static Reader<Env, Env> ask<Env>() =>
        asks<Env, Env>(identity);
}

Writer<Out, A>

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<Out, A>(Func<Out, (A Value, Out Output)> runWriter) : K<Writer<Out>, A>
    where Out : Monoid<Out>;

// Writer extensions
public static class WriterExtensions
{
    public static Writer<Out, A> As<Out, A>(this K<Writer<Out>, A> ma) 
        where Out : Monoid<Out> =>
        (Writer<Out, A>)ma;
    
    public static (A Value, Out Output) Run<Out, A>(this K<Writer<Out>, A> ma)
        where Out : Monoid<Out> =>
        ma.Run(Out.Empty);
    
    public static (A Value, Out Output) Run<Out, A>(this K<Writer<Out>, A> ma, Out output)
        where Out : Monoid<Out> =>
        ma.As().runWriter(output);
}

// Writer trait implementations
public class Writer<Out> : Monad<Writer<Out>>
    where Out : Monoid<Out>
{
    public static K<Writer<Out>, B> Bind<A, B>(K<Writer<Out>, A> ma, Func<A, K<Writer<Out>, B>> f) =>
        new Writer<Out, B>(log =>
        {
            var (value, log1) = ma.Run(log);  // threads the log through
            return f(value).Run(log1);        // runs with the updated log
        });

    public static K<Writer<Out>, B> Map<A, B>(Func<A, B> f, K<Writer<Out>, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<Writer<Out>, A> Pure<A>(A value) =>
        new Writer<Out, A>(log => (value, log));

    public static K<Writer<Out>, B> Apply<A, B>(K<Writer<Out>, Func<A, B>> mf, K<Writer<Out>, A> ma) =>
        mf.Bind(ma.Map);
}

// Writer module
public static class Writer
{
    // Writes a value to the output  
    public static Writer<Out, Unit> tell<Out>(Out item) 
        where Out : Monoid<Out> =>
        new (log => (default, log + item));
}

State<S, A>

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<S, A>(Func<S, (A Value, S State)> runState) : K<State<S>, A>;

// State extensions
public static class StateExtensions
{
    public static State<S, A> As<S, A>(this K<State<S>, A> ma) => 
        (State<S, A>)ma;
    
    public static (A Value, S State) Run<S, A>(this K<State<S>, A> ma, S state) =>
        ma.As().runState(state);
}

// State trait implementations
public class State<S> : Monad<State<S>>
{
    public static K<State<S>, B> Bind<A, B>(K<State<S>, A> ma, Func<A, K<State<S>, B>> f) =>
        new State<S, B>(state =>
        {
            var (value, state1) = ma.Run(state); // threads the state through
            return f(value).Run(state1);         // runs with the updated state
        });

    public static K<State<S>, B> Map<A, B>(Func<A, B> f, K<State<S>, A> ma) =>
        ma.Bind(x => Pure(f(x)));

    public static K<State<S>, A> Pure<A>(A value) =>
        new State<S, A>(state => (value, state));

    public static K<State<S>, B> Apply<A, B>(K<State<S>, Func<A, B>> mf, K<State<S>, A> ma) =>
        mf.Bind(ma.Map);
}

// State module
public static class State
{
    // Gets the state value and maps it  
    public static State<S, A> gets<S, A>(Func<S, A> f) => 
        new (state => (f(state), state));
    
    // Gets the state value   
    public static State<S, S> get<S>() => 
        gets<S, S>(identity);
    
    // Updates the monad's state value   
    public static State<S, Unit> put<S>(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<A> (equivalent of Option<A>) – that has an alternative value of None
  • Either<L, R> – that has a bespoke alternative value: L
  • Fin<A> – equivalent to Either<Error, A>
  • Validation<F, A> – that has a bespoke monoidal alternative value F that collects multiple alternative results
  • Try<A> - 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<Env, A> – 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<Out, A> – threads a monoidal output log through the computation.
  • State<S, A> – 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<A> – for managing world changing side-effects (previous article)
  • Eff<A> – not included as it requires a bit more explanation (next article)

Some other monads we didn't cover here:

• Free<F, A> – which allows for any functor to be turned into a monad for free.
• Cont<A> – continuations
• Identity<A> – manages no effects at all!
• Other collections like: Seq<A>, Arr<A>, Lst<A>, Set<A>, HashSet<A>

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<A>) and side-effects (IO<A>)?

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<A> – Option and IO
• EitherAsync<A> – Either and IO
• TryAsync<A> – Try and IO
• TryOption<A> – Try and Option
• TryOptionAsync<A> – 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...