使用 LINQ 递归遍历分层数据结构

• 下载源代码 - 22.29 KB

引言

本文尝试展示如何使用 LINQ 查询类似树形结构的分层数据，而无需额外开销来展平数据结构或循环遍历元素。

背景

不幸的是，在撰写本文时，尚未为 LINQ 定义递归查询运算符。 因此，无法像对扁平对象集合那样直接查询分层数据结构。

对于查询扁平对象集合，您可能会编写如下代码：

myItems.FindAll(i => i.Id == 25) 

对于分层集合，如果我们能够编写类似的代码来查询层次结构中的任何位置的对象，那将会是多么棒啊！

myItems.Traverse(i => i.Id == 25) 

这可以通过编写一个扩展方法来实现，该方法在内部使用 Y 组合子递归遍历层次结构。

Y 组合子

Y 组合子方法可用于编写递归 lambda 表达式。 关于 Y 组合子在 C# 中的更多理论信息和应用，可以在以下优秀的 MSDN 文章中找到。

• http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx
• http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx

Extensions 类中使用了 Y 组合子的通用实现。

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); 
    }

    ...
    ...
}

对于我们的目的，我们将使用类型为 IEnumerable<Item> 的参数调用它。 因此，Y 组合子最终将返回一个委托，该委托接受一个类型为 IEnumerable<Item> 的参数，并返回一个类型为 IEnumerable<Item> 的对象。

var traverse = Extensions.Y<IEnumerable<Item>, IEnumerable<Item>>(...)

扩展方法

Traverse 是 IEnumerable<Item> 的一个扩展方法，它接受一个类型为 Func<Item, bool> 的谓词作为参数。 该参数将包含封装层次结构中项的选择逻辑的 lambda 表达式。

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);
}

使用谓词，在 Traverse 扩展方法中，我们将构建要传递给 Y 组合子的递归 lambda 表达式。

用法

现在我们可以使用如下语法来查询分层集合。

IEnumerable<Item> result = myItems.Traverse(i => i.Id == 25);
result = myItems.Traverse(i => i.Name.Contains("Child"));
result = myItems.Traverse(i => !i.IsVisible);

限制

当前的实现不支持循环数据结构。