public static IEnumerable<T> PreOrder<T>(this T startingPoint, Func<T, IEnumerable<T>> children)
{
yield return startingPoint;
foreach (var child in children(startingPoint))
{
var preOrderedChildren = PreOrder(child, children);
foreach (var preOrderedChild in preOrderedChildren)
{
yield return preOrderedChild;
}
}
}
"What is it?" you say? It's a generic, recursive generator, implemented as an extension method with a functor."Uhh, so... what does it do?" you counter? It traverses a tree of items (of type T) by yielding them, starting at the provided startingPoint and obtaining the children of a given instance of T using the provided children function object.
"I am from Missouri. You have got to show me." Sure thing! Suppose we have this Node class:
public class Node : IEnumerable<Node>
{
private readonly IList<Node> _children = new List<Node>();
public IEnumerable<Node> Children { get { return _children; } }
private readonly string _name;
public string Name { get { return _name; } }
public Node(string name)
{
_name = name;
}
public Node Add(string nodeName)
{
return Add(new Node(nodeName));
}
public Node Add(Node node)
{
_children.Add(node);
return node;
}
#region IEnumerable<Node> Members
public IEnumerator<Node> GetEnumerator()
{
return Children.GetEnumerator();
}
#endregion
#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return Children.GetEnumerator();
}
#endregion
}
...we can then use the Node class to represent its own high-level parse tree:
var compilationUnit = new Node("Node.cs")
{
new Node("namespace Test")
{
new Node("public class Node : IEnumerable<Node>")
{
new Node("public IEnumerable<Node> Children")
{
new Node("get;")
},
new Node("public string Name")
{
new Node("get;")
},
new Node("public Node(string name);"),
new Node("public Node Add(string nodeName);"),
new Node("public Node Add(Node node);"),
new Node("#region IEnumerable<Node> Members")
{
new Node("public IEnumerator<Node> GetEnumerator();"),
},
new Node("#region IEnumerable Members")
{
new Node("System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator();"),
},
},
},
};
Notice how the Node constructor accepts both regular arguments (in this case, a string representing the node's Name) as well as a list of Node instances? That feature -- collection initializers -- is made available to classes that implement IEnumerable as well as an Add method.The PreOrder method can then be called on the compilationUnit instance, as follows, due to the extension method feature:
The second argument to the method is a lambda expression that, given an instance of Node, returns an IEnumerable<Node>. In other words, it explains to PreOrder how to get a sequence of Node instances given a single Node instance. In our case, it is rather simple, as the Node class has the Children property for that purpose (and it could have been even simpler than that, since Node implements IEnumerable and thus the second parameter could have been written as n => n).var sequenceOfNodes = compilationUnit.PreOrder(n => n.Children);
Anyway, calling the PreOrder method looked like it did nothing and it almost did indeed do nothing, which is the point of a generator: until you start pulling on the IEnumerable, no work is performed and no items are generated. All that was done by calling PreOrder was setting up the generator instance in the sequenceOfNodes variable. Let's actually start generating (a.k.a. yielding):
foreach (var node in sequenceOfNodes)
{
Console.WriteLine(node.Name);
}
...when that loop starts executing, the code in PreOrder kicks in and the first item yielded is the startingPoint, which was initialized in compilationUnit, so its Name is printed to the console. The children of startingPoint are obtained by calling the children functor on startingPoint itself. As you will remember, that's simply the Children property. The process repeats recursively behind the scenes, yielding a node, then its children, while our loop doesn't need to worry about all of that. The loop will end up printing a flat list version of the original tree.Conclusion (a.k.a. Too long; didn't read)
In 12 lines of code, I made use of the following groovy C# 3.5 compiler features:- Extension methods: extend a closed type with a static method that appears like an instance method
- Lambda expressions: inline, anonymous methods that replace private classes that implement an interface AND can operate on local variables
- Generators (a.k.a. Iterators): the yield return keyword in methods that return IEnumerable
- Implicitly-typed local variables: the var keyword, to avoid repeating yourself
Bonus
If this modest display of mad skillz hasn't convinced you to switch to .NET 3.5, well, you don't even need to! You can compile all this code with the C# 3.5 compiler but still target the .NET 2.0 runtime or even the JVM!Targetting the .NET 2.0 runtime
Not only can you make use of the new compiler features, you can also make use of the new IDE features, such as call hierarchy and reference highlighting.- Open Visual Studio (this should work in Visual Studio 2008 and 2010)
- File > New > Project...
- Select .NET Framework 2.0 from the drop-down list on the right:
- Create the ExtensionAttribute replacement by adding a file called ExtensionAttribute.cs in your project with the following contents:
namespace System.Runtime.CompilerServices { public class ExtensionAttribute : Attribute { } } - Create a Delegates.cs file that contains the missing Action and Func delegates from the System namespace (you probably only need up to 4 arguments)
- Start writing cool code!
