Free monads come to C#

Free monads allow the programmer to take a functor and turn it into a monad for free.

The [Free] code-gen attribute provides this functionality in C#.

Below, is a the classic example of a Maybe type (also known as Option, here we're using the Haskell naming parlance to avoid confusion with the language-ext type).

[Free]
public interface Maybe<A>
{
    [Pure] A Just(A value);
    [Pure] A Nothing();

    public static Maybe<B> Map<B>(Maybe<A> ma, Func<A, B> f) => ma switch
    {
        Just<A>(var x) => Maybe.Just(f(x)),
        _              => Maybe.Nothing<B>()
    };
}

Click here to see the generated code

The Maybe<A> type can then be used as a monad:

var ma = Maybe.Just(10);
var mb = Maybe.Just(20);
var mn = Maybe.Nothing<int>();

var r1 = from a in ma
         from b in mb
         select a + b;  // Just(30)

var r2 = from a in ma
         from b in mb
         from _ in mn
         select a + b;  // Nothing

And so, in 11 lines of code, we have created a Maybe monad that captures the short-cutting behaviour of Nothing.

But, actually, it's possible to do this in fewer lines of code:

[Free]
public interface Maybe<A>
{
    [Pure] A Just(A value);
    [Pure] A Nothing();
}

If you don't need to capture bespoke rules in the Map function, the code-gen will build it for you.

A monad, a functor, and a discriminated union in 6 lines of code. Nice.

As with the discriminated-unions, [Free] types allow for deconstructing the values when pattern-maching:

var txt = ma switch
{
    Just<int> (var x) => $"Value is {x}",
    _                 => "No value"
};

The type 'behind' a free monad (in Haskell or Scala for example) usually has one of two cases:

• Pure
• Free

Pure is what we've used so far, and that's why Just and Nothing had the Pure attribute before them:

[Pure] A Just(A value);
[Pure] A Nothing();

They can be considered terminal values. i.e. just raw data, nothing else. The code generated works in exactly the same way as the common types in language-ext, like Option, Either, etc. However, if the [Pure] attribute is left off the method-declaration then we gain an extra field in the generated case type: Next.

Next is a Func<*, M<A>> - the * will be the return type of the method-declaration.

For example:

[Free]
public interface FreeIO<T>
{
    [Pure] T Pure(T value);
    [Pure] T Fail(Error error);
    string ReadAllText(string path);
    Unit WriteAllText(string path, string text);
}

Click here to see the generated code

If we look at the generated code for the ReadAllText case (which doesn't have a [Pure] attribute), then we see that the return type of string has now been injected into this additional Next function which is provided as the last argument.

    public sealed class ReadAllText<T> : FreeIO<T>, System.IEquata...
    {
        public readonly string Path;
        public readonly System.Func<string, FreeIO<T>> Next;
        public ReadAllText(string Path, System.Func<string, FreeIO<T>> Next)
        {
            this.Path = Path;
            this.Next = Next;
        }

Why is all this important? Well, it allows for actions to be chained together into a continuations style structure. This is useful for building a sequence of actions, very handy for building DSLs.

var dsl = new ReadAllText<Unit>("I:\\temp\\test.txt", 
              txt => new WriteAllText<Unit>("I:\\temp\\test2.txt", txt, 
                  _ => new Pure<Unit>(unit)));

You should be able to see now why the [Pure] types are terminal values. They are used at the end of the chain of continuations to signify a result.

But that's all quite ugly, so we can leverage the monadic aspect of the type:

var dsl = from t in FreeIO.ReadAllText("I:\\temp\\test.txt")
          from _ in FreeIO.WriteAllText("I:\\temp\\test2.txt", t)
          select unit;

The continuation itself doesn't do anything, it's just a pure data-structure representing the actions of the DSL. And so, we need an interpreter to run it (which you write). This is a simple example:

public static Either<Error, A> Interpret<A>(FreeIO<A> ma) => ma switch
{
    Pure<A> (var value)                            => value,
    Fail<A> (var error)                            => error,  
    ReadAllText<A> (var path, var next)            => Interpret(next(Read(path))),
    WriteAllText<A> (var path, var text, var next) => Interpret(next(Write(path, text))),
};

static string Read(string path) => 
    File.ReadAllText(path);

static Unit Write(string path, string text)
{
    File.WriteAllText(path, text);
    return unit;
}

We can then run it by passing it the FreeIO<A> value:

var result = Interpret(dsl);

Notice how the result type of the interpreter is Either. We can use any result type we like, for example we could make the interpreter asynchronous:

public static async Task<A> InterpretAsync<A>(FreeIO<A> ma) => ma switch
{
    Pure<A> (var value)                            => value,
    Fail<A> (var error)                            => await Task.FromException<A>(error),  
    ReadAllText<A> (var path, var next)            => await InterpretAsync(next(await File.ReadAllTextAsync(path))),
    WriteAllText<A> (var path, var text, var next) => await InterpretAsync(next(await File.WriteAllTextAsync(path, text).ToUnit())),
};

Which can be run in a similar way, but asynchronously:

var res = await InterpretAsync(dsl);

And so, the implementation of the interpreter is up to you. It can also take extra arguments so that state can be carried through the operations. In fact it's very easy to use the interpreter to bury all the messy stuff of your application (the IO, maybe some ugly state management, etc.) in one place. This then allows the code itself (that works with the free-monad) to be referentialy transparent.

Another trick is to create a mock interpreter for unit-testing code that uses IO without having to ever do real IO. The logic gets tested, which is what is often the most important aspect of unit testing, but not real IO occurs. The arguments to the interpreter can be the mocked state.

Some caveats though:

• The recursive nature of the interpreter means large operations could blow the stack. This can be dealt with using a functional co-routines/trampolining trick, but that's beyond the scope of this doc.
• Although it's the perfect abstraction for IO, it does come with some additional performance costs. Generating the DSL before interpreting it is obviously not as efficient as directly calling the IO functions.

Caveats aside, the free-monad allows for complete abstraction from side-effects, and makes all operations pure. This is incredibly powerful.

Full code-gen documentation