Code Magic
21 Aug 2009 
around lunchtime 
Matt Winckler
Magic is bad. There should not be anything magical in production code, because by definition, magic is something not understood. I’m on board with this notion.
But what happens when magic is twice as fast (or faster) than normal code? Fast magic is a temptation difficult to resist, particularly when the performance of the normal code is not acceptable to begin with.
And so it is that I have done something I thought I never would: I have implemented the Y combinator, in a useful fashion(!), in a C# project I’m working on. I used to think Y combinator had no place in C#, because the language itself supports recursion. However, LINQ doesn’t, and I don’t know of another way to employ it generically short of using Y.
I don’t understand all the ins and outs and mathematical equations and untyped lambda calculus on that Wikipedia page (in fact, I don’t understand any of them. Side question: do math-related Wikipedia pages make sense to anybody, including mathematicians?). But I do understand that after trying to understand the real-world mechanics and looking at an example or two, I was able to implement a function of my own that delves through a TreeView and gets all the TreeNodes that are checked. And, depending on how many nodes there are and how many are checked, this function is at least twice as fast as the conventional way of doing it, a speedup I attribute mostly (if not entirely) to LINQ’s deferred execution.
public static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f) {
Func<A, R> g = null;
g = f(a => g(a));
return g;
}
/// <summary>
/// Gets all checked TreeNodes in the specified TreeView.
/// </summary>
/// <param name="treeview"></param>
/// <returns></returns>
public static IEnumerable<TreeNode> GetCheckedNodes(this TreeView treeview) {
var getNodes = Y<TreeNode, IEnumerable<TreeNode>>(
f => n => new[] {n}.Concat(
(from TreeNode node in n.Nodes select node).SelectMany(f)
));
return (from TreeNode N in treeview.Nodes select N)
.SelectMany(getNodes).Where(n => n.Checked);
}
(Yes…I desperately need to get a syntax highlighting plugin here. It’s on the todo list along with the site revamp. Copy the code into Visual Studio and pretend it wasn’t a hassle.)
Plus, the magic gave me a tingly sensation, which changed from frightening to slightly pleasant once I decided that this fixed-point combinator untyped lambda calculus business wasn’t going to open a portal to some other dimension and let a bunch of aliens through to take over the world. (I thought I saw the wall behind my monitors starting to distort into a torus shape, but after rubbing my eyes the effect disappeared.)
I still profess to be a hack and a neophyte at this magic, so gurus are invited to point me to a better way of accomplishing this without resorting to Y combinator magic. Though I do fear that tingly sensation may be habit-forming.