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.

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>, SemiAlternative<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>, SemiAlternative<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>, 
    SemiAlternative<RWST<R, W, S, 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>, SemiAlternative<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...