Higher Kinds in C# with language-ext [Part 8- monads continued]
![Higher Kinds in C# with language-ext [Part 8- monads continued]](/content/images/size/w960/2024/05/monads-2.png)
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
)
- The operations have a particular 'flavour' which defines what happens between the operations (
- 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. TheMap
function won't be invoked if theOption
is in aNone
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 whyBind
is sometimes also calledFlatMap
.
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 aFree
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 aLeft
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 aFail
state and multiple fail-value aggregation when using applicativeApply
.
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);
}
EnumerableM<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.
EnumerableM
is a new data-type in language-ext that is a wrapper for IEnumerable
– it's everything that IEnumerable
is but with traits.
// EnumerableM data-type
public record EnumerableM<A>(IEnumerable<A> Items) : K<EnumerableM, A>, IEnumerable<A>
{
public IEnumerator<A> GetEnumerator() =>
Items.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() =>
Items.GetEnumerator();
}
// EnumerableM extensions
public static class EnumerableMExtensions
{
public static EnumerableM<A> As<A>(this K<EnumerableM, A> ma) =>
(EnumerableM<A>)ma;
}
// EnumerableM trait implementation
public class EnumerableM : Monad<EnumerableM>
{
public static K<EnumerableM, B> Bind<A, B>(K<EnumerableM, A> ma, Func<A, K<EnumerableM, B>> f)
{
return new EnumerableM<B>(Go());
IEnumerable<B> Go()
{
foreach (var x in ma.As())
{
foreach (var y in f(x).As())
{
yield return y;
}
}
}
}
public static K<EnumerableM, B> Map<A, B>(Func<A, B> f, K<EnumerableM, A> ma)
{
return new EnumerableM<B>(Go());
IEnumerable<B> Go()
{
foreach (var x in ma.As())
{
yield return f(x);
}
}
}
public static K<EnumerableM, A> Pure<A>(A value) =>
new EnumerableM<A>([value]);
public static K<EnumerableM, B> Apply<A, B>(K<EnumerableM, Func<A, B>> mf, K<EnumerableM, 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 theReader
monad except the state isn't read-only: it can be updated. Again, it removes the need to provide and additionalS 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 ofOption<A>
) – that has an alternative value ofNone
Either<L, R>
– that has a bespoke alternative value:L
Fin<A>
– equivalent toEither<Error, A>
Validation<F, A>
– that has a bespoke monoidal alternative valueF
that collects multiple alternative resultsTry<A>
- has an alternative value ofError
which is used to catch exceptions and make them declarative.
- Collection monads
EnumerableM
– works with many values (almost all collections are implemented like this)- 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 memberFunc
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>
– continuationsResource<A>
– which tracks resources (disposables for later releasing)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
andIO
EitherAsync<A>
–Either
andIO
TryAsync<A>
–Try
andIO
TryOption<A>
–Try
andOption
TryOptionAsync<A>
–Try
,Option
, andIO
.
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!!!