TreeSelector : playing with generics and type inference

This piece of code is part of a personal bigger project that I am working on and I think there are interesting thing in it and I wanted to share it with you.

I am trying to use generics and type inference to imagine new kind of method prototype.
With all the stuff around Linq like lambda expressions, simple method calls have become extremely powerful.

What I have been trying here is to create a generic way to define a selection starting from a tree of objects, the most simpler way as possible.

Let's start with the beginning...
Here is a very simple little interface defining a node of the tree, basically, a value and the references to the child nodes.


public interface INodeSelector { object Value { get; } List<INodeSelector> Children { get; } }

You can notice that the Value is just typed as 'object'. To store any kind of value we will keep this definition, but to have an easy to use initialization, we will create generic methods and have all the benefits of the type inference and intellisense.

Now I will create an generic type to implement INodeSelector: NodeSelector<T>.

new NodeSelector<Customer>(customer);

As constructors can not infer their generic parameters from the parameters, I prefered to use a static method for creating NodeSelector<T> instances. For different reasons that I will explain later the name of the hosting class is not NodeSelector but TreeSelector.

public static class TreeSelector { public static NodeSelector<T> Create<T>(T source) { return new NodeSelector<T>(source); } } ... var ts = TreeSelector.Create(customer)

For the moment we just have NodeSelector<T> class that keeps the root value of our tree.

Now from this root, I would like to define paths to some other values. Each of those paths will provide a new child node attached to the root node (and to its parent node for the following levels).

Let's start thinking about just a single child.

We can achieve this easily using a simple selector expression, starting from the value of the current node and returning the child value.

public class NodeSelector<T> : INodeSelector { ... public void Add<TResult>(Func<T, TResult> selector) { Children.Add(TreeSelector.Create(selector(source))); } }

Then we can write:

var ts = TreeSelector.Create(customer); ts.Children.Add(c => c.CustomerID);

Now I would like to add two features:

adding new nodes at the same level.

  • adding new child nodes to an existing node.

Let's remind some generic rules. When calling 'ts.Children.Add(c => c.CustomerID)', we do not need to define the TResult generic parameter of Add<TResult> because it is infered by the expression 'c => c.CustomerID'. Without type inference we would have need to define Add<string>() explicitly.

I could return the new created node in the Add() method instead of returning void and then chain Add() calls:

ts.Children.Add(c => c.Address).Children.Add(ad => ad.City);

But if I want to add nodes at the same level (sibling), I will have to create a temporary reference and break this chain.

On the other hand, I could allow to pass an array of selectors to the Add method to add sibling nodes in just a call.

ts.Children.Add(c => c.CustomerID, c => c.Address);

Using this syntax, I can add as many sibling nodes as I want but returning a value from Add() has no sense so I am losing the previous syntax for chaining children creation.

So I have imagined something else that is not very usual: returning the current node instance from the Add() method (not the added one !).

public class NodeSelector<T> : INodeSelector { ... public NodeSelector<T> Add<TResult>(Func<T, TResult> selector) { Children.Add(TreeSelector.Create(selector(source))); return this; } }

Now we can write:

var ts = TreeSelector.Create(customer) .Add(c => c.CustomerID) .Add(c => c.Address);

So we now use chained Add() calls to add sibling nodes. We still need to add child nodes.

There is something very interesting in type inference: if a generic parameter is resolved by the first parameter of a method, then the following parameters can use it.

In my example, '.Add(c => c.Address, ...)', the TResult parameter is resolved as an Address type thanks to the first parameter 'c => c.Address'. So we can use it in the following parameters.

Inside the Add() method we are wrapping the resulting value of the projection in a new NodeSelector<TResult>. We would need to get it out so the second parameter could use it to add child nodes. To achieve this I will add a new delegate parameter providing the added NodeSelector<T> and waiting for it to be returned. In theory we don't need any return value but lambda expressions must return a value. As now, all Add() calls are returning the NodeSelector<T> itself, I will define my delegate that way:

public NodeSelector<T> Add<TResult>(Func<T, TResult> selector, Func<NodeSelector<TResult>, NodeSelector<TResult>> childrenSelectors) { var n = TreeSelector.Create(selector(source)); childrenSelectors(n); Children.Add(n); return this; }

Now we can write:


var ts = TreeSelector.Create(customer) .Add(c => c.CustomerID) .Add(c => c.Address, ad => ad .Add(a => a.City) .Add(a => a.Country) );

Now it becomes quite interesting. We have a single expression allowing us to add both siblings and child nodes without creating any temporary reference to any node.

Playing with indentation we can even 'see' the resulting tree.

Let's try to display it in a TreeView control.

The code is recursive but quite simple:

private void FillTreeView(TreeNodeCollection nodes, INodeSelector ns) { var node = nodes.Add(ns.Value.ToString()); foreach (var child in ns.Children) FillTreeView(node.Nodes, child); } ... FillTreeView(treeView1.Nodes, ts);


Now we have a good basic solution, let's add some more features !

In the current example, we have built a tree using simple selectors, jumping to one value to another one. (one-to-one relationship)

What if the relationship is one-to-many like 'c => c.Orders' ?

Then we could create a method to add all the children into as many sibling nodes.

So we will need a selector to retrieve the collection (c => c.Orders). Then another selector to apply on each item of the collection. It the itemSelector is not provided (null) we will add the item itself (the Order in our example).

public NodeSelector<T> AddRange<TResult>( Func<T, IEnumerable<TResult>> collectionSelector, Func<TResult, object> itemSelector) { foreach (var item in collectionSelector(source)) if (itemSelector != null) Children.Add(TreeSelector.Create(itemSelector(item))); else Children.Add(TreeSelector.Create(item)); return this; } public NodeSelector<T> AddRange<TResult>( Func<T, IEnumerable<TResult>> collectionSelector) { return AddRange(collectionSelector, null); }

Now we can write :

var ts = TreeSelector.Create(customer) .Add("CustomerID", c => c.CustomerID) .Add(c => c.Address, ad => ad .Add(a => a.City) .Add(a => a.Country) ) .AddRange(c => c.Orders, o => o.OrderDate);


We can see that the AddRange() method has added 3 new nodes. So the AddRange() is just the repeat of what we can do with Add().

Maybe would like to group all these nodes under a common one whose value would be the collection.

Let's create the AddCollection() method.

public NodeSelector<T> AddCollection<TResult>( Func<T, IEnumerable<TResult>> collectionSelector, Func<TResult, object> itemSelector) { var selector = collectionSelector(source); var node = TreeSelector.Create(selector); Children.Add(node); foreach (var item in selector) if (itemSelector != null) node.Children.Add(TreeSelector.Create(itemSelector(item))); else node.Children.Add(TreeSelector.Create(item)); return this; } public NodeSelector<T> AddCollection<TResult>( Func<T, IEnumerable<TResult>> collectionSelector) { return AddCollection(collectionSelector, null); }

Now we can write:

var ts = TreeSelector.Create(customer) .Add(c => c.CustomerID) .Add(c => c.Address, ad => ad .Add(a => a.City) .Add(a => a.Country)) .AddCollection(c => c.Orders, o => o.OrderDate);


Ok, one last feature, but a useful one.

As you can see in all the screen captures, I am just displaying the Values because it's the only thing I have !! 🙂

But ! Maybe you would like to add a label or any kind of other object to your nodes.

In the Winforms TreeNode for example, there is a very useful Tag property that allows you to attach what you want to your nodes.

Let's add such a feature to our code.

Let's start with the NodeSelector definition itself:

an extended interface :

public interface INodeSelectorWithTag : INodeSelector { object Tag { get; } }

an extended implementation :

public class NodeSelector<T, TTag> : NodeSelector<T>, INodeSelector<T, TTag> { public NodeSelector(TTag tag, T source) : base(source) { Tag = tag; } public TTag Tag { get; private set; } object INodeSelectorWithTag.Tag { get { return this.Tag; } } public NodeSelector<T, TTag> Add<TResult>( TTag tag, Func<T, TResult> selector) { Children.Add(TreeSelector<TTag>.Create(tag, selector(source))); return this; } and all the AddXXX() methods ...

and an extended creator class :

public static class TreeSelector<TTag> { public static NodeSelector<T, TTag> Create<T>(TTag tag, T source) { return new NodeSelector<T, TTag>(tag, source); } public static NodeSelector<T, TTag> Create<T>(T source) { return TreeSelector<TTag>.Create(default(TTag), source); } }

Now we can write :

var ts = TreeSelector<string>.Create("Customer", customer) .Add("CustomerID", c => c.CustomerID) .Add("Address", c => c.Address, ad => ad .Add("City", a => a.City) .Add("Country", a => a.Country) );

Let's modify our TreeView code.


private void FillTreeView(TreeNodeCollection nodes, INodeSelectorWithTag ns) { var node = nodes.Add((ns.Tag ?? "") + " > " + ns.Value.ToString()); foreach (var child in ns.Children) FillTreeView(node.Nodes, child); }


This post is already too long so I will stop here.

What's next ?

- I will use this TreeSelector to project an Xml structure.

- I will rewrite it to support deferred loading. Actually it's already done but I am not really happy with my code. I will wait for CLR4 generics covariance to propose a clean solution.

The whole solution is attached to this post.

Comments (17)

  1. odhan says:

    This is a very interesting implementation.

    Just two little things : I’m not a fan of the Tag solution (too much oldy VCL style IMO) – it’s very handy of course but not as smart as the rest of your code. The second point is the choice to break the Add() usual working way by returning current instance instead of the created child. Here too it’s very handy (cascaded Add) but it’s a bit dangerous in case someone else will have to work on your code (for maintenance purpose by example).

    Apart these 2 points, global idea seems to be very good and you made a very smart use of the C# 3.0 syntax ! 🙂

  2. Jeff Handley says:

    Hey Mitsu, this is awesome!  Neat stuff and I look forward to seeing the rest of this.

  3. Mitsu Furuta says:

    Thanks guys !

    @Olivier: I know there are some unusual things here. I am looking for new ways to write some prototypes taking advantage of C# 3.0 new features. Type inference is extending intellisense possibilities making code extremely fast to write. I am also trying to make the use of lambda expressions more familiar. People really need to get used with this syntax.

    The whole ting is more testing than a final idea.

    @Jeff: good to hear from you Jeff !

    My final goal is to create view proxy objects on demand. Once again it’s just a try but I think you should like it 🙂

  4. Hi Mitsu.

    I was at all your sessions at Marseille, yesterday and tomorrow. I was (one of) the (two) guy with the camera 🙂

    Do you already know what will be added regarding generics ? Is C# trying to get closer to C++’s templates ? Or the "opposite" ?

  5. Mitsu Furuta says:


    In C# 4.0, we will add support for covariance and contravariance on generic type parameters (use of ‘in’ and ‘out’ keywords).

    We are absolutly not trying to get closer to C++ templates. Even if generics visually looks like C++ templates, they are really different (checked at compile time but resolved at runtime, type inference support). My opinion is that .Net generic types are a very good illustration of how you to get something more powerful by reducing the possibilities 🙂

  6. Ok.

    Is there some place where we can find informations on those upcoming features ?

  7. Kirk says:

    "With all the stuff around Linq like lambda expressions, simple method calls have become extremely powerful."

    In light of your later code, there should be a law passed to prevent you from trying to teach. Placing lamba expressions inside a method call is the polar opposite of simple.

    In fact, the only thing that I can find is that it saves one from typing out the full method with signature and name at another place in the code. Or, put another way, it is lazy coding.

    If lazy coding becomes the norm for C#, then the framewwork will fall by the wayside. Look at history. .NET rose to promenance in spite of being relatively limited in version 1. Its strength was that fact that it was easy to read. Shoving a method into a method call is not conducive to easy to read, easy to follow code.

  8. Mitsu Furuta says:

    Kirk, first of all, hello,

    Usually I just don’t answer to this kind of comment.

    But even if your style is a little bit aggressive, I will try to answer.

    First, I do not pretend to teach to anyone. As I said, this sample is a test and I am looking for new ways to write method calls taking advantage of type inference. As I am interested by others’ opinion (even yours), I am sharing it. Of course, if you prefer not to test new solutions, you have no risk to find some!

    Now regarding your concern about using a lambda as a parameter of a method call, I suggest you start reading evolution of other languages. This technic, quite new to C# is extremely used in dynamic (javascript, python, etc.) and functional languages (like F#).

    My humble opinion if you want to know it is that this functional flavor of C# 3.0 solves one of the limits of object programming. According to you, those lambdas should be implemented in the class. Ok, but what if the lambda use is local to the method and has no meaning inside the class. Then you will get a bunch of methods with absolutely nothing in common, degrading the readability of your class. Not a question of lazy coding…

    Moreover, a lambda is not exactly a simple method of a class. The compiler creates an environment to allow a lambda to be able to be executed completely alone, even if the class that is hosting it has been disposed for example.

    Finally, I think you mismatch “it’s not simple to read” and  “I’am not used to this syntax”.

    Linq is mainly about using lambdas as parameters of method calls:

    var q =

       from e in elements

       where e.Attribute == “value”

       order by e.Id

    which is equivalent to:

    Elements.Where(e => e.Attribute == “value”).OrderBy(e => e.Id);

    I suggest you write the same thing without lambdas, using regular methods and we will compare which code is easier to read or follow.



    PS: if you want to get other opinions, you can add the same comment to mostly any post talking about Linq!

  9. Steve says:

    Nice article, I’ve just implemented something similar and always wondered why something like this was not in the framework. One thing I’ve found to be enormously useful while working with these structures is to write a Descendants() method similar to the LINQ to XML API. Its only 5-6 line of code and very, very powerful. A Flatten method is also great. This takes the entire tree and flattens it while maintaining the parent – child linkages. Using yield return, this is also like 8-10 lines of code.

  10. DavidEkl says:

    This might confuse things a little bit for people trying to read the code, but i do have a suggestion on how to get around using the "Tag".

    I notice that you call the base method ToString() on your object Value property.

    Couldnt one override that method in a business object, and put that object in the Value property?

    I think i’ve used this approach with some winform elements that took type object as parameter successfully in the past.

    Thus keeping the object handy (like ComboBox.SelectedItem), and also getting it’s desired string representation.

    Very interesting read though i must admit, keep it coming! 🙂


  11. hack2root says:

    I want make you code more elegant (no boxing unboxing), so I will add it to my library and upgrade it as follows:

       public interface INodeSelectorWithTag<TTag> : INodeSelector


           TTag Tag { get; }

           new List<INodeSelectorWithTag<TTag>> Children { get; }


  12. Json says:

    Dang kirk, don’t be such a prick. This is cutting edge code. The point of using complex structures like generics and lambdas in class code, is to simplify the component’s API and usage to consumers. Like Mitsu said, the reason libraries like the Linq providers out there are so simple and functional is because heavy usage of lambdas, anon methods, generics, etc… This example is geared towards library writers. If you just write code that consumes libraries others have written, then you will appreciate the thought that goes into making simple and functional APIs.

  13. Enigmatic says:

    It was mentioned that using a Tag wasn’t the most elegant approach (reminds me of my old vb 6 days).

    What solutions have others tried instead of this?

  14. Mitsu Furuta says:

    Interesting thoughts around the Tag feature.

    You can notice that the "Tag" version of the nodes is only used when needed. Unlike the WinForms.Control.Tag which is always present.

    If I had to explore other ways I would try to get a solution comparable to the wpf AttachedProperties mecanism. I really love this approach of having extra data ‘attached’ to instances.

    To be very honest, I would even love to have such a mecanism for all relationships between objects (one to one or one to many).

    I am tired to see the complexity and the dependencies of customer.Orders.

  15. Erhan Hosca says:

    public interface INodeSelector<T>


       T Value { get; }

       List<INodeSelector<T>> Children { get; }


  16. young says:

    very interesting topic. thanks for sharing. can you post the lazy load code part too?

Skip to main content