# 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`

)

- 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. 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);
}
```

### 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 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
`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 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`Resource<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`

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!!! *