Tasks, Monads, and LINQ

A few years back, Wes Dyer wrote a great post on monads, and more recently, Eric Lippert wrote a terrific blog series exploring monads and C#. In that series, Eric alluded to Task<TResult> several times, so I thought I’d share a few related thoughts on Task<TResult> and the async/await keywords.

As both Wes and Eric highlight, a monad is a triple consisting of a type, a Unit function (often called Return), and a Bind function. If the type in question is Task<T>, what are its Unit and Bind functions?

The Unit operator takes a T and “amplifies” it into an instance of the type:

public static M<T> Unit<T>(this T value);

That’s exactly what Task.FromResult does, producing a Task<T> from a T, so our Unit method can easily be implemented as a call to FromResult:

public static Task<T> Unit<T>(this T value)
{
    return Task.FromResult(value);
}

What about Bind? The Bind operator takes the instance of our type, extracts the value from it, runs a function over that value to get a new amplified value, and returns that amplified value:

public static M<V> Bind<U, V>(
    this M<U> m, Func<U, M<V>> k);

If you squint at this, and if you’ve read my previous blog post Implementing Then with Await, the structure of this declaration should look eerily like the last overload of Then discussed:

public static Task<TNewResult> Then<TResult, TNewResult>(
    this Task<TResult> task, Func<TResult, Task<TNewResult>> continuation);

In fact, other than the symbols chosen, they’re identical, and we can implement Bind just as we implemented Then:

public static async Task<V> Bind<U, V>(
    this Task<U> m, Func<U, Task<V>> k)
{
    return await k(await m);
}

This is possible so concisely because await and async are so close in nature to the monadic operators. When you write an async function that returns Task<V>, the compiler expects the body of the method to return a V, and it lifts (or amplifies) that V into the Task<V> that’s returned from the method call; this is basically Unit (async, of course, also handles the creation and completion of the returned Task for the case where an exception propagates out of the body of the async method). Further, a core piece of the Bind operator is in extracting the value from the supplied instance, and that’s nicely handled by await.

In Eric’s last post on monads, he talks about some of the C# LINQ operators, and how they can easily be implemented on top of types that correctly implement a Unit and a Bind method:

static M<C> SelectMany<A, B, C>(
    this M<A> monad,
    Func<A, M<B>> function,
    Func<A, B, C> projection)
{
    return monad.Bind(
        outer => function(outer).Bind(
            inner => projection(outer, inner).Unit()));
}

Sure enough, with our Bind and Unit implementations around Task<T>, we can substitute in “Task” for “M”, and it “just works”:

static Task<C> SelectMany<A, B, C>(
    this Task<A> monad,
    Func<A, Task<B>> function,
    Func<A, B, C> projection)
{
    return monad.Bind(
        outer => function(outer).Bind(
            inner => projection(outer, inner).Unit()));
}

What does it mean here to “just work”? It means we can start writing LINQ queries using the C# query comprehension syntax with operators that rely on SelectMany, e.g.

int c = await (from first in Task.Run(() => 1)
               from second in Task.Run(() => 2)
               select first + second);
Console.WriteLine(c == 3); // will output True

Of course, we can implement SelectMany without Bind and Unit, just using async/await directly:

static async Task<C> SelectMany<A, B, C>(
    this Task<A> task,
    Func<A, Task<B>> function,
    Func<A, B, C> projection)
{
    A a = await task;
    B b = await function(a);
    return projection(a, b);
}

In fact, we can implement many of the LINQ query operators simply and efficiently using async/await. The C# specification section 7.16.3 lists which operators we need to implement to support all of the C# query comprehension syntax, i.e. all of the LINQ contextual keywords in C#, such as select and where. Some of these operators, like OrderBy, make little sense when dealing with singular values as we have with Task<T>, but we can easily implement the others. This enables using most of the C# LINQ query comprehension syntax with Tasks:

public static async Task<V> SelectMany<T, U, V>(
    this Task<T> source, Func<T, Task<U>> selector, Func<T, U, V> resultSelector)
{
    T t = await source;
    U u = await selector(t);
    return resultSelector(t, u);
}

public static async Task<U> Select<T, U>(
    this Task<T> source, Func<T, U> selector)
{
    T t = await source;
    return selector(t);
}

public static async Task<T> Where<T>(
    this Task<T> source, Func<T, bool> predicate)
{
    T t = await source;
    if (!predicate(t)) throw new OperationCanceledException();
    return t;
}

public static async Task<V> Join<T, U, K, V>(
    this Task<T> source, Task<U> inner,
    Func<T, K> outerKeySelector, Func<U, K> innerKeySelector,
    Func<T, U, V> resultSelector)
{
    await Task.WhenAll(source, inner);
    if (!EqualityComparer<K>.Default.Equals(
        outerKeySelector(source.Result), innerKeySelector(inner.Result)))
            throw new OperationCanceledException();
    return resultSelector(source.Result, inner.Result);
}

public static async Task<V> GroupJoin<T, U, K, V>(
    this Task<T> source, Task<U> inner,
    Func<T, K> outerKeySelector, Func<U, K> innerKeySelector,
    Func<T, Task<U>, V> resultSelector)
{
    T t = await source;
   
return resultSelector(t,
        inner.Where(u => EqualityComparer<K>.Default.Equals(
            outerKeySelector(t), innerKeySelector(u))));
}

public static async Task<T> Cast<T>(this Task source)
{
    await source;
    return (T)((dynamic)source).Result;
}

Interestingly, Task<TResult> already has the members necessary to be considered “comonadic.” As Brian Beckman discusses in his precis, a comonad is the dual of a monad, a triple consisting of the type and two operators: Extract (the flip of Unit/Return) and Extend (the flip of Bind). Here I’ve taken a few liberties with the signatures from what Brian outlines, such as swapping the order of some of the parameters:

public T Extract<T>(this W<T> self);
public W<U> Extend<T, U>(this W<T> self, Func<W<T>, U> func);

Task<TResult> already supports Extract, it’s just called Result:

public TResult Result;

And it already supports Extend, it’s just called ContinueWith:

public Task<TNewResult> ContinueWith<TNewResult>(
    Func<Task<TResult>, TNewResult> func);

(In truth, to correctly implement all of the comonadic laws Brian outlines, we’d likely want to tweak both of these with a thin layer of additional code to modify some corner cases around exceptions and cancellation, due to how Result propagates exceptions wrapped in AggregateException and how ContinueWith tries to match thrown OperationCanceledExceptions against the CancellationToken supplied to ContinueWith. But the basic idea stands.)

Most of the posts I write on this blog are about practical things. So, is any of this really useful in everyday coding with Tasks and async/await? Would you actually want to implement and use the LINQ surface area directly for Tasks? Eh, probably not. But it’s a fun to see how all of these things relate.

(Update 4/3/2013: Thanks to Aaron Lahman for pointing out the bug I had in my GroupJoin implementation.  Fixed.)