Monads, part twelve

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: [1. 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: [1. 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.[1. 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(mn) 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.[1. 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.]

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.

About these ads

16 thoughts on “Monads, part twelve

  1. “throw new Exception()”

    Please don’t, not even in a throwaway sample. If you don’t have a meaningful exception to throw, use something like InvalidOperationException.

    • InvalidOperationException would probably be appropriate in this case, but that wouldn’t always be true. In general, I think it is better to throw System.Exception than to hastily throw something that might not accurately reflect the nature of the exception. Obviously, you’d need to replace it with something more specific before it goes to production, especially if it’s going into a reusable library, but in throwaway code, why not?

      • The problem with throwing System.Exception is that it makes it much harder for calling code to respond appropriately. There’s at least one code path in the BCL which, when passed invalid input, catches a FormatException and wraps it in a System.Exception, making it extremely painful to call. I reported it as a bug in .NET 1, but was told it couldn’t be fixed because it might break backwards compatibility.

        Throwing a System.Exception with the intention of going back to change it to a more appropriate exception later is a bad idea, because nine times out of 10 you’ll never go back and change it. You’ll either forget to do it, miss it, or run out of time.

        Throwing a System.Exception in a throwaway code sample is bad, because it encourages other people to do the same thing in their production code. After all, if Eric does it, it must be the right thing to do!

        • Same goes with sample code not disposing Disposables or leaking event handlers (especially when using lambda construct += (sender, e) => …). For what it’s worth, I see some overhead if each code snippet someone puts on his blog should follow all good coding practices…

  2. Pingback: Tasks, Monads, and LINQ - .NET Parallel Programming - Site Home - MSDN Blogs

  3. Regarding footnote 4: I learned in University (and the Wikipedia article on NP hardness says the same) that undecidability is included in the class of NP hard problems. Or am I confusing decision problems (Wikipedia cites an undecidable *decision problem* as NP hard) with optimisation problems?

    Which is it?

    • If a problem is NP-HARD that means it is AT LEAST as hard as the HARDEST problem in NP. Since the halting problem is harder than any NP problem, by definition it is NP-HARD.

      So it was silly of me to say that the problem is “at least NP-HARD”, since the definition of NP-HARD already includes an “at least”. I should have been more clear; what I meant to say is that the problem is definitely NP-HARD, and I believe it to be NP but I don’t have a proof of that.

  4. Aw, this was an extremely good post. Finding the time and actual effort to create
    a really good article… but what can I say… I
    procrastinate a whole lot and don’t seem to get nearly anything done.

    my page :: Rudy

  5. Pingback: Functional Programming in Matlab using Query (Part III) | A Page of Insanity

  6. What i don’t realize is in fact how you are now not really much more neatly-preferred than you might
    be now. You are so intelligent. You understand thus significantly in the case
    of this subject, made me personally imagine it from a lot of numerous angles.
    Its like men and women aren’t fascinated until it’s something to accomplish with Woman gaga!
    Your personal stuffs great. All the time deal with it up!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s