Introduction
This article makes an attempt to show how to query for objects in a tree like hierarchical data structure using LINQ and without additional overhead of flattening the data structure or looping through the elements.
Background
Unfortunately at the time of writing this article, there has not been a recursive query operator defined for LINQ. Therefore there is no direct method to query for objects in a hierarchical data structure as you would do for a flat object collection.
For querying a flat object collection, you would probably write something like:
myItems.FindAll(i => i.Id == 25)
For a hierarchical collection, wouldn't it be cool if we were able to write something similar to query for objects anywhere in the hierarchy:
myItems.Traverse(i => i.Id == 25)
This can be achieved by writing an extension method which internally uses the Y Combinator to recursively traverse the hierarchy.
Y Combinator
The Y Combinator method can be used for writing recursive lambda expressions. More theoretical information and applications of the Y Combinator in C# can be found in the following excellent MSDN articles.
A generic implementation of the Y Combinator is used in the Extensions class.
public static class Extensions
{
private delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
private static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
Recursive<A, R> rec = r => a => f(r(r))(a); return rec(rec);
}
...
...
}
For our purpose, we will be calling it with parameters of type IEnumerable<Item>. Therefore the Y Combinator will ultimately return a delegate which takes an IEnumerable<Item> as an parameter and returns an IEnumerable<Item>.
var traverse = Extensions.Y<IEnumerable<Item>, IEnumerable<Item>>(...)
Extension Method
Traverse is an extension method for IEnumerable<Item> which takes a predicate of type Func<Item, bool> as a parameter. This parameter will contain the lambda expression encapsulating the selection logic for the items in the hierarchy.
public static IEnumerable<Item> Traverse(this IEnumerable<Item> source,
Func<Item, bool> predicate)
{
var traverse = Extensions.Y<IEnumerable<Item>, IEnumerable<Item>>(
f => items =>
{
var r = new List<Item>(items.Where(predicate));
r.AddRange(items.SelectMany(i => f(i.Children)));
return r;
});
return traverse(source);
}
Using the predicate, within the Traverse extension method, we will build the recursive lambda expression to be passed over to the Y Combinator.
Usage
Now we can use syntax like below to query the hierarchical collection.
IEnumerable<Item> result = myItems.Traverse(i => i.Id == 25);
result = myItems.Traverse(i => i.Name.Contains("Child"));
result = myItems.Traverse(i => !i.IsVisible);
Limitations
The current implementation will not support cyclic data structures.
