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 SelectMany
s, 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(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.
(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.
Category theory would be *great* for a series. 🙂
“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…
Did I get April Fooled a day late or was there different article up earlier?
My post for two weeks from now accidentally got its publishing date set wrong.
Great work! Thanks a lot. Would you mind publishing the whole Monad series as a single, e-reader-friendly document?
Pingback: Tasks, Monads, and LINQ - .NET Parallel Programming - Site Home - MSDN Blogs
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.
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
Pingback: Functional Programming in Matlab using Query (Part III) | A Page of Insanity
Hi friends, fastidious paragraph and pleasant arguments commented here, I am truly enjoying by these.
Hi! Would you mind if I share your blog with my facebook
group? There’s a lot of people that I think would really enjoy your
content. Please let me know. Thank you
Pingback: Curiosidades de C#: tipado estructural… sólo para algunos | Koalite
Pingback: Про ошибки и исключения – CHEPA website
Pingback: How would you solve this design issue for a Some monad in C#? (Bonus minor Either design issue) - How to Code .NET
Pingback: Monads, part eleven | Fabulous adventures in coding
Pingback: Tasks, Monads, and LINQ – essay studess