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

This is a multi-part series of articles – and you'll need to know much of what's in the earlier parts to follow along – so it's worth going back to the earlier episodes if you haven't read them already:

- Part 1 - Introduction, traits, semigroups, and monoids
- Part 2 - Functors
- Part 3 - Foldables
- Part 4 - Applicatives
- Part 5 - Validation
- Part 6 - Traversables
- Part 7 - Monads
- Part 8 - Monads (continued)
- Part 9 - Monad Transformers
- Part 10 - ReaderT monad transformer
- Part 11 - StateT monad transformer

In the last article we covered the `StateT`

monad-transformer, which is a close relative to the `ReaderT`

monad-transformer from the article before that. The `WriterT`

monad-transformer is implemented in exactly the same way as the `StateT`

monad-transformer. The only difference is that the state type (`S`

in the `StateT`

transformer, renamed to `W`

in the `WriterT`

) is constrained to be a `Monoid<W>`

.

That means we can create an 'empty' `W`

and we can 'append'/'combine' values to `W`

. So, `WriterT`

is good for logging multiple outputs, or aggregating an output value over the course of a monadic expression.

The classic way to implement a `Writer`

monad (not transformer), is like so:

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

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

monad

The interesting thing here is that the `runWriter`

property doesn't have an input state as part of its `Func`

delegate. It simply combines the outputs of two invocations of `runWriter`

in the `Bind`

method (`output1.Combine(output2)`

).

That allows for a very simple `tell`

function that we use to aggregate our output:

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

We simply return the `output`

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

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

The problem with this approach is that we call `tell`

much less than we call `Bind`

. And in the `Bind`

function we call `Monoid.Combine`

*every single time*. This is problematic for two reasons:

- Most of the time the outputs will be empty, so this is wasted work
- When they're not empty, the outputs could need to perform significant work to
`Combine`

the two states.- Imagine concatenating two (immutable) linked-lists that are 100 items long each, that would require a 100 item loop to build a new list! You can easily get into a problem of
*exponential*monoidal combines.

- Imagine concatenating two (immutable) linked-lists that are 100 items long each, that would require a 100 item loop to build a new list! You can easily get into a problem of

So, to get around this, we want to remove the `Combine`

from the `Bind`

function and find another way to aggregate the output. Really, we want the work to happen in the `tell`

function, because that is explicitly doing the work of outputting data.

To achieve this, we must first update the `Func<(W Output, A Value)> runWriter`

to take a `W`

input:

`Func<W, (W Output, A Value)> runWriter`

Then update our `Bind`

function to remove the `Monoid.Combine`

and to pass the initial `output0`

value through the expression:

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

`The eagle-eyed among you will realise that this is exactly the same as the ``State`

monad. It threads a state through the computation, returning the updated value.

Now we can update the `tell`

function:

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

Most of the time when using `Writer`

our output is a collection of some flavour. And so, this `tell`

function, usually, is just appending or consing a single item to the collection. And so, the risk of exponential concatenation issues goes away (as long as the monoid is implemented efficiently, something to take care with). This is much more efficient, generally.

The thing is, if we look at the implementation of `Writer`

, we can now drop the `Monoid<W>`

constraint:

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

We only need it for the `tell`

function. The rest of the implementation is exactly the same as `State`

. So, we don't actually need to implement `WriterT`

. We can simply write a `tell`

function for `StateT`

:

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

Or even, generalise it over all `Stateful`

types:

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

That means *anything *that implements `Stateful<M, W>`

can now aggregate an output state using the `Monoid<W>`

trait.

So, why would we ever implement `WriterT`

if `StateT`

is good enough? Well, I've asked myself that question a few times. I've considered dropping the `Writer`

and `WriterT`

types altogether. But, have decided to keep them because they are *declarative* – they tell the reader of your code that you're aggregating an output, not merely carrying some state. Communication with the reader of your code (including yourself) is important and this seems like a good distinction, even if – at a fundamental level – the types are the same.

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

"`WriterT`

is the same as`StateT`

, we just have a`Monoid`

constraint on the state". So, if you grokked the last article, then you're all good.

## RWST

Now that we've defined `ReaderT`

, `WriterT`

, and `StateT`

, we can finally implement `RWST`

:

```
public record RWST<R, W, S, M, A>(ReaderT<R, WriterT<W, StateT<S, M>>, A> runRWS)
: K<RWST<R, W, S, M>, A>
where M : Monad<M>
where W : Monoid<W>;
```

Reader, Writer, State, Transformer. This type is a combination of the `ReaderT`

transformer, the `WriterT`

transformer, the `StateT`

transformer, and an `M`

monad. So, **four** stacked behaviours. It is especially good for defining your 'application monad', i.e. the one that carries configuration, state, and needs to log as it goes, as well as being able to lift an `M`

monad (`IO`

, `Option`

, etc.).

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

traits:

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

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

*Until next time...*