Holy goodness, this series got a lot longer than I expected. I was hoping to get to some actual category theory, but let’s just talk a bit about LINQ and then wrap up. Maybe I’ll do a series on the basics of category theory in the future.

I’ve said several times that SelectMany is the bind operation on the sequence monad, but of course there are several overloads of the SelectMany extension method of IEnumerable<T>. The one that is bind is as we previously discussed:  (Error checking removed for clarity.)

public static IEnumerable<R> SelectMany<A, R>(
  this IEnumerable<A> items, 
  Func<A, IEnumerable<R>> function)
{
  foreach(A outer in items)
    foreach(R inner in function(outer))
      yield return inner;
}

Now you might think that when you say

from outer in items
from inner in function(outer)
select inner

this translates directly into a call to

items.SelectMany(outer=>function(outer))

This is not what actually happens.

Why not? Because we want outer to still be in scope when the final select happens!

from outer in items
from inner in function(outer)
select new { outer, inner }  // outer had better still be in scope!

How do we get two parameters in scope at the same time? This is a hint that there is some sort of nested operation going on here. Suppose we have our unit function as an extension method: (Yes, it is super bad style to make an extension method on everything, but it is pedagogically and syntactically useful so I’m going to do so several in this episode.)

static IEnumerable<T> Singleton<T>(this T t) 
{ 
  yield return t; 
}

The query above then is actually two SelectManys, one nested inside the other!

items.SelectMany(
  outer => function(outer).SelectMany( 
    inner => new { inner, outer }.Singleton() ) )

Of course we know that there is a more efficient way to write that inner SelectMany; it’s just Select.

As I noted earlier in this series, we could implement Select out of SelectMany and a unit operation, but of course for efficiency in practice we do not.

items.SelectMany(
  outer => function(outer).Select( 
    inner => new { outer, inner }) )

This now has a structure that is nicely similar to the query expression syntax. Is this the code that the C# compiler actually transforms the query expression above into?

No. This is the code generated for the original prerelease version of LINQ, which we scrapped because we discovered that nested lambdas are bad for performance. Consider for example:

from a in items
from b in f(a)
from c in g(a, b)
from d in h(a, b, c)
select new { a, b, c, d }

This would then translate into

items.SelectMany(
  a => f(a).SelectMany(
    b=> g(a, b).SelectMany(
      c => h(a, b, c).Select(
        d => new {a, b, c, d}))));

That’s elegant and beautiful, but it is super hard to analyze at compile time. Many years ago I wrote a bit in my blog about how if you have lambdas nested O(n) deep, and each lambda has O(m) possible methods to choose from in an overload resolution problem, then that’s potentially an O(mⁿ) problem; that posting was motivated by this discovery during the development of LINQ. I sketched out a scenario demonstrating that the problem is at least NP-HARD.

(It is at least NP-HARD because it is equivalent to finding a solution of a 3-SAT problem; I suspect that overload resolution in C# is not actually harder than that. I see no reason, for instance, why it ought to be undecidable. But I don’t have a proof of this assertion. UPDATE: Overload resolution depends on convertibility, and convertibility in languages with contravariance and nominal generic subtyping has been shown to be undecidable! But I still do not know if overload resolution in C# is undecidable even if convertibility is restricted to a decidable subset of the convertibility rules. I still suspect it is not.)

That’s all very highfalutin; what we discovered in practice was that the compiler and IDE essentially hung indefinitely and chewed up all the address space when the nestings got about eight or nine deep, which is not at all unreasonable. Clearly something had to be done. What we did was split the problem into two parts. First, the simple case; if all you have in your query is:

from inner in items
from outer in function(items)
select projection(inner, outer)

then this is translated into

items.SelectMany( 
  inner => function(items), 
  (inner, outer) => projection(inner, outer)

Which is implemented as

public static IEnumerable<C> SelectMany<A, B, C>(
  this IEnumerable<A> items,
  Func<A, IEnumerable<B>> function,
  Func<A, B, C> projection) 
{
  foreach(A outer in items)
    foreach(B inner in function(outer))
      yield return projection(outer, inner);
}

Which is nicely efficient.

The complicated case is the scenario where there’s something other than a select immediately following the two from clauses. In that case, in order to avoid deeply nested lambdas the C# compiler does an even more complicated transformation involving “transparent identifiers” and anonymous types. Getting into all the details of that would take us far afield; I want to finish up this series. We’ll talk about transparent identifiers some other time.

So let’s drag this back to general monads. Suppose we have a monad M<T> and  extension methods:

static M<T> Unit<T>(this T item) 
{ ... }
static M<R> Bind<A, R>(
  this M<A> monad, 
  Func<A, M<R>> function) 
{ ... }

We can define the SelectMany extension method that LINQ wants without knowing anything about the monad’s amplification:

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()));
}

Of course, if we do know something about it, like we do with the sequence monad, then we can do a better job. But to illustrate that this is sufficient, let’s try it.

struct Maybe<T> 
{
  public static Maybe<T> Null = default(Maybe<T>);
  public bool HasValue { get; private set; }
  private T value;
  public T Value 
  {
    get
    {
      if (!HasValue) throw new Exception();
      return value; 
    }
  }
  public Maybe(T value) : this()
  { 
    this.HasValue = true;
    this.value = value;
  }
  public override string ToString()
  {
    return HasValue ? Value.ToString() : "NULL";
  }
}
static class Extensions
{
  public static Maybe<T> Unit<T>(this T value) 
  { return new Maybe<T>(value); }
  public static Maybe<R> Bind<A, R>(
    this Maybe<A> maybe,
    Func<A, Maybe<R>> function)
  {
    return maybe.HasValue ? 
      function(maybe.Value) :
      Maybe<R>.Null;
  }
  public static Maybe<C> SelectMany<A, B, C>(
    this Maybe<A> maybe, 
    Func<A, Maybe<B>> function,
    Func<A, B, C> projection)
  {
    return maybe.Bind(
      outer => function(outer).Bind(
        inner => projection(outer, inner).Unit()));
  }
  public static Maybe<short> AsSmall(this int x)
  {
    return 0 <= x && x <= 100 ? 
      ((short)x).Unit() : 
      Maybe<short>.Null;
  }
  public static Maybe<short> QuerySyntax(this Maybe<int> maybe)
  {
    return from outer in maybe
           from inner in outer.AsSmall()
           select inner;
  }
}
class P
{
  static void Main()
  {
    System.Console.WriteLine(1.Unit().QuerySyntax());
    System.Console.WriteLine(1000.Unit().QuerySyntax());
    System.Console.WriteLine(Maybe<int>.Null.QuerySyntax());
  }
}

And sure enough, the query comprehension binds the AsSmall function to the maybe monad. We get the (short) 1 out of the first call, and nulls out of the second and third.

Whew. I’m glad that worked after six weeks of buildup.

So what’s the upshot of this whole thing?

First: the monad pattern is an amazingly general pattern for “amplifying” types while maintaining the ability to apply functions to instances of the underlying types.

Second: because of that ability, the “bind” operation is the Swiss Army Knife of higher-order programming. The C# and VB teams could have built LINQ out of nothing other than functions that combine the unit and bind operations; the result would not have been as efficient as the optimized special-purpose helper functions we actually did build, but it can be done.

Third: LINQ in C# and VB were designed to be very comfortable to use on only one monad, the sequence monad. But as we’ve seen, the LINQ “select many” syntax is actually just a roundabout way to bind a new monadic workflow onto an existing one.

OK, I was wrong when I said that I’d be wrapping up here; next time on FAIC my former colleague Stephen Toub talks about the task comonad a bit more.