How would I even use a monad (in C#)?

posted by Craig Gidney on October 30, 2012

As you may have guessed, based on everyone ever trying to explain what they are, monads are an interesting concept. I assume the difficulty in explaining them stems from the high level of abstraction, compared to related ideas like “being enumerable”, but I won’t be trying to explain what a monad is in this post. Instead I’m going to show you how, in C#, you can take advantage of a type being a monad.

If you do want an explanation of what a monad is, I recommend the marvels of monads, an old post that made the concept “click” for me. It even covers some of the same content I’ll be presenting here.

Querying your Monad

Language integrated query (LINQ) was a major feature introduced way back in C#3. Instead of manually looping over a list to create another list of transformed results, you could suddenly write a much more concise query expression:

// before linq
var transformedList = new List();
foreach (var item in inputList) {
    transformedList.Add(item * 2 + 1);
}
// after linq
var transformedSequence = from item in inputList select item * 2 + 1;

You probably already know about query expressions, but you may not have known that you can query over more than just lists and other enumerables. In fact, you can make your own custom types queryable. You do this by implementing extension methods corresponding to the various parts of the query expression.

For example, suppose we want to be able to query and transform tasks (a.k.a. Futures / Promises / Eventual Results). Queryable tasks would let us write code like this:

public async static void PrintQueryTasks() {
    // needs Task.Select, prints "7" one second after being invoked
    Console.WriteLine(await (from e in 5.DelayOneSecond()
                             select e + 2));
    // needs Task.SelectMany, prints "7" two seconds after being invoked
    Console.WriteLine(await (from e in 2.DelayOneSecond()
                             from r in (e + 1).DelayOneSecond()
                             select e * r + 1));
}
private static Task<T> DelayOneSecond<T>(this T result) {
    return Task.Delay(1000).ContinueWith(x => result);
}

The C# compiler implements these queries by transforming them into code that invokes methods called Select and SelectMany. In this case Select should take a task, as well as a function to apply to the task’s eventual result, and should return a task representing the function’s eventual output when eventually given the input task’s result. SelectMany should have corresponding functionality, but allowing for an intermediate task. We can implement these methods by delegating to the existing ContinueWith and Unwrap methods, like this:

///<summary>Transforms a task's result, or propagates its exception or cancellation.</summary>
public static Task<TOut> Select<TIn, TOut>(this Task<TIn> task, Func<TIn, TOut> projection) {
    var r = new TaskCompletionSource<TOut>();
    task.ContinueWith(self => {
        if (self.IsFaulted) r.SetException(self.Exception.InnerExceptions);
        else if (self.IsCanceled) r.SetCanceled();
        else r.SetResult(projection(self.Result));
    });
    return r.Task;
}
///<summary>Transforms a task's result and then does a combined transform, propagating any exceptions or cancellation.</summary>
public static Task<TOut> SelectMany<TIn, TMid, TOut>(
        this Task<TIn> task,
        Func<TIn, Task<TMid>> midProjection,
        Func<TIn, TMid, TOut> outProjection) {
    return task.Select(inp => midProjection(inp).Select(mid => outProjection(inp, mid))).Unwrap();
}

Once we’ve placed these extension methods inside of a static class, the task querying code from above should compile and run.

Another common type of thing to make queryable is nullable values. Querying a nullable value will propagate any nulls, instead of failing with an exception, but otherwise act normally. Unfortunately, the fact that, in C#, all references are nullable means we can only reasonably define this query for value types. However, it still makes a good example. So, in order to write nullable querying code like this:

public static void PrintQueryNullables() {
    int? five = 1;
    int? six = 2;
    int? noValue = null;

    // needs T?.Select, prints "true"
    Console.WriteLine(from e in five
                      select e == 5);
    // needs T?.Select, prints "" (meaning null)
    Console.WriteLine(from e in noValue
                      select e == 5);

    // needs T?.SelectMany, prints "false"
    Console.WriteLine(from e in five
                      from n in six
                      select e * 2 == n);
    // needs T?.SelectMany, prints "" (meaning null)
    Console.WriteLine(from e in noValue
                      from n in six
                      select e + 1 == n);
    // needs T?.SelectMany, prints "" (meaning null)
    Console.WriteLine(from e in five
                      from n in noValue
                      select e + 1 == n);
}

We can implement the corresponding extension methods like this:

///<summary>Transforms non-null values while propagating nulls.</summary>
public static TOut? Select<TIn, TOut>(this TIn? nullable, Func<TIn, TOut> projection)
        where TIn : struct
        where TOut : struct {
    if (nullable == null) return null;
    return projection((TIn)nullable);
}
///<summary>Transforms a value and then does a combined transform involving the intermediate result, propagating any nulls.</summary>
public static TOut? SelectMany<TIn, TMid, TOut>(
        this TIn? nullable,
        Func<TIn, TMid?> midProjection,
        Func<TIn, TMid, TOut> outProjection)
        where TIn : struct
        where TMid : struct
        where TOut : struct {
    if (nullable == null) return null;
    var mid = midProjection((TIn)nullable);
    if (mid == null) return null;
    return outProjection((TIn)nullable, (TMid)mid);
}

Once again, placing these extension methods in a static class should allow the nullable querying code from above to compile and run.

I hope these two examples have made it clear: to make some type M queryable, you implement Select and SelectMany methods that work with type M. You may be wondering how this all related to monads. Well here’s the important part: Select and SelectMany can be expressed in terms of Bind, which is a monad method. That means any type that is a monad is queryable with linq (you just need to implement Select/SelectMany). So you can use linq query expressions to inspect and produce sets, maps, tuples, pairs, maybes, parsers, futures, arrays, linked lists, trees, functions, observables, events, lists of trees, state, continuations, lists of trees, etc, etc, and etc (a lot of things are monads).

Use #1: Types that are monads can be made queryable.

Side note: implementing Bind is equivalent to implementing SelectMany. Both can be expressed in terms of the other. Given SelectMany, Bind is implemented as “from value in input from result in projection(value) select result”. Therefore, by writing an implementation of SelectMany for a type M, you are doing some of the work of explaining to the compiler how M is a monad.

Hybrid Queries

One thing you might notice, if you get on a “query everything” bender due to the information in the previous section, is that queries don’t work across different types. For example, this code fails to compile even if we can query lists and tasks:

// list then task
from e in Enumerable.Range(0, 10)
from r in e.DelayOneSecond() // compile error
select r + e
// task then list
from n in 10.DelayOneSecond()
from r in Enumerable.Range(0, n) // compile error
select r + n

The problem is that the intermediate result is not the same type of monad as the input, and we don’t have a SelectMany defined for that case. The compiler is unable to guess what we want, which is to wait for all results to complete and then return a combined eventual result composed of all the final outputs. We need to explain what we want by implementing two hybrid SelectMany methods, which we will do by using our Task.Select extension method and Task.WhenAll from the base class library:

public static Task<IEnumerable<TOut>> SelectMany<TIn, TMid, TOut>(
        this IEnumerable<TIn> sequence, 
        Func<TIn, Task<TMid>> midProjection, 
        Func<TIn, TMid, TOut> outProjection) {
    return sequence
        .Select(inp => midProjection(inp).Select(mid => outProjection(inp, mid)))
        .WhenAll();
}
public static Task<IEnumerable<TOut>> SelectMany<TIn, TMid, TOut>(
        this Task<TIn> sequence, 
        Func<TIn, IEnumerable<TMid>> midProjection, 
        Func<TIn, TMid, TOut> outProjection) {
    return sequence
        .Select(inp => midProjection(inp).Select(mid => outProjection(inp, mid)));
}

For consistency I chose to give both of these variants of SelectMany the same output signature: eventual enumerable results (the query expression syntax doesn’t place constraints on the return type of SelectMany). However, note that if I’d instead tried to make them both return enumerable eventual results, I would have failed. I would have come up against the impossibility of determining (without blocking) if a sequence that wasn’t available yet had a first item.

It’s interesting that we can “flip” from enumerable eventual results to eventual enumerable results, but we can’t flip back. Lets explore other cases where we can flip the nesting of two monads. We’ll start with a peek at an (inefficient but correct) implementation of WhenAll, which we used to do the one “flip” we know can be done so far:

///<summary>Eventually returns all of the eventual results from the sequence.</summary>
public static Task<IEnumerable<T>> WhenAll<T>(this IEnumerable<Task<T>> sequence) {
    return sequence.Aggregate(
        Task.FromResult(Enumerable.Empty<T>()),
        (eventualAccumulator, eventualItem) =>
            from accumulator in eventualAccumulator
            from item in eventualItem
            select accumulator.Concat(new[] { item }).ToArray().AsEnumerable());
}

Notice that there are only two constructs in this method that are specific to tasks: Task.FromResult and Task.SelectMany (implicit in the query expression). I wonder what happens if we replace them by the equivalent constructs for nullable values / an option type? (Note: we need an option type that applies to any type equally, because IEnumerable is not a value type, so just imagine an option type called May.) Well, we get a method that returns no-value if any item in the list is a no-value and otherwise returns a normal list of values:

///<summary>Returns the potential values' values from the sequence, unless one of them is a lack-of-value, in which case the result is lack-of-value.</summary>
public static May<IEnumerable<T>> MayGetAll<T>(this IEnumerable<May<T>> sequence) {
    return sequence.Aggregate(
        new May>(Enumerable.Empty<T>()),
        (maybeAccumulator, maybeItem) =>
            from accumulator in maybeAccumulator
            from item in maybeItem
            select accumulator.Concat(new[] { item }).ToArray().AsEnumerable());
}

Seems like a useful method to have around.

Something even more interesting happens if we replace the Task constructs with their IEnumerable equivalents. We get a method that enumerates all the ways you can choose one item from each enumerated sequence from a sequence:

///<summary>Returns all of the ways you can choose one item from each sequence in a sequence.</summary>
public static IEnumerable<IEnumerable<T>> AllPossibilitiesForChoosingOneFromEach<T>(this IEnumerable<IEnumerable<T>> sequence) {
    return sequence.Aggregate(
        new[] { Enumerable.Empty<T>() }.AsEnumerable(),
        (sequenceOfAccumulator, sequenceOfItem) =>
            from accumulator in sequenceOfAccumulator
            from item in sequenceOfItem
            select accumulator.Concat(new[] { item }).ToArray().AsEnumerable());
}

I find this really interesting. Our method for awaiting a bunch of tasks is almost identical to a method that can be used to flatten nested loops:

foreach (var i0 in Enumerable.Range(0, 10)) {
    foreach (var i1 in Enumerable.Range(0, 10)) {
        foreach (var i2 in Enumerable.Range(0, 10)) {
            foreach (var i3 in Enumerable.Range(0, 10)) {
                foreach (var i4 in Enumerable.Range(0, 10)) {
                    var I = new[] {i0,i1,i2,i3,i4};
                    ...
                }
            }
        }
    }
}
// is functionally equivalent to
foreach (var I in Enumerable.Repeat(Enumerable.Range(0, 10), 5)
                  .AllPossibilitiesForChoosingOneFromEach()) {
    ...
}

All of these apparently different methods are implemented in almost exactly the same way. It seems like as long as we have a type M that supports SelectMany and allows us to wrap the empty sequence into an instance, we can write a method that “flips” enumerable from being nested outside of M to being nested inside of M. Of course, as you may have guessed, any type that is a monad supports both of the operations we need to “flip” enumerable inside of that type. I’ve already mentioned monads have Bind, allowing us to implement SelectMany, but they also have ‘Return’ (wraps any value into the monad), which is exactly what we need to wrap our empty sequence as an M.

Use #2: Types that are monads can be queried in combination with enumerable.

There are other types of monads which allow this sort of “flipping” operation, but also some monads that don’t. As I’ve already mentioned, it doesn’t work with Task (it’s impossible to make an eventual result non-eventual). From what I’ve tried, it only seems to work on “collection-like” monads (in order to allow the aggregate call). So you can “flip” sets, maps, lists, trees, pairs, tuples, and options but not tasks, observables, parsers, or functions.

Hypothetical Usage

If the C# type system allowed us to represent monad as an interface (it doesn’t), we could implement all of the apparently distinct “flip enumerable” methods as a single method, which I will call BindAll:

///<summary>Pulls the monad type outside of the list type by binding across the list's elements.</summary>
///<remarks>Not actually possible to compile in C# today.</remarks>
public static M<IEnumerable<T>> BindAll<M, T>(this IEnumerable<M<T>> sequence)
    where M : Monad { //<-- Type parameter M takes a type parameter T. Not currently possible.
    return sequence.Aggregate(
        M.Return(Enumerable.Empty<T>()), //<-- Static interface method. Not currently possible.
        (wrappedAccumulator, wrappedNextItem) =>
            from accumulator in wrappedAccumulator
            from item in wrappedNextItem
            select accumulator.Concat(new[] { item }).ToArray().AsEnumerable());
}

BindAll is a great example of the power a flexible type system can give. If we could only represent monads then we could fuse WhenAll, MayGetAll, AllPossibilitiesForChoosingOneFromEach, and plenty of other useful methods (for other types of monads) into a single method. Plus, we could implement a single SelectMany method to enable all hybrid queries where the input type is an enumerable:

public static M<IEnumerable<TOut>> SelectMany<M, TIn, TMid, TOut>(
        this IEnumerable<TIn> sequence,
        Func<TIn, M<TMid>> midProjection,
        Func<TIn, TMid, TOut> outProjection)
        where M : Monad {
    return sequence
        .Select(inp => midProjection(inp).Select(mid => outProjection(inp, mid)))
        .BindAll();
}

Side note: this could potentially create an ambiguity with respect to what enumerating over two sequences means. Will it flatten the sequence of sequences via Enumerable.SelectMany or will it enumerate choice possibilities via our generic SelectMany using BindAll? Presumably the compiler would prefer the more specific overload: Enumerable.SelectMany.

Conclusion

LINQ allows you to take advantage of the fact that a particular type is a monad, by consuming and producing instances of that type via query expressions. You can even query (some) combinations of types. That might not seem like a lot of different uses, but the uses are very flexible and a great way to ease into functional programming. If C# had a type system capable of representing monads directly, instead of indirectly through compiler checks like "is there a SelectMany method?", there would be even more use cases.

---

Discuss on Reddit

---

  • Roman Koreshkov

    It was an interesting explanation. Thanks!


Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive

More interesting posts (13 of 33 articles)

Or check out our Portfolio.