在LINQ中表达递归

Question

我正在为一个分层数据源编写一个LINQ提供程序.我发现通过编写显示我想如何使用它的示例来设计我的API是最容易的,然后编写代码以支持这些用例.

我遇到麻烦的一件事是在LINQ语句中表达"深度查询"或递归的简单/可重用/优雅方式.换句话说,区分以下内容的最佳方法是:

from item in immediate-descendants-of-current-node where ... select item

与:

from item in all-descendants-of-current-node where ... select item

(编辑:请注意上面这些例子都不一定反映我想要的查询结构.我感兴趣的是表达递归/深度的任何好方法)

请注意我不是问如何实现这样的提供程序,或者如何以允许递归的方式编写我的IQueryable或IEnumerable.我是从一个人编写LINQ查询并利用我的提供者的角度问的 - 他们表达是否想要递归的直观方式是什么？

数据结构类似于典型的文件系统:文件夹可以包含子文件夹的集合,文件夹也可以包含项集合.所以myFolder.Folders表示myFolder的直接子节点的所有文件夹,myFolder.Items包含myFolder中的所有项目.这是网站层次结构的基本示例,非常类似于包含文件夹和页面的文件系统:

(F)Products
    (F)Light Trucks
        (F)Z150
            (I)Pictures
            (I)Specs
            (I)Reviews
        (F)Z250
            (I)Pictures
            (I)Specs
            (I)Reviews
        (F)Z350
            (I)Pictures
            (I)Specs
            (I)Reviews
        (I)Splash Page
    (F)Heavy Trucks
    (F)Consumer Vehicles
    (I)Overview 

如果我写:

from item in lightTrucks.Items where item.Title == "Pictures" select item

表达查询获取Light Trucks下的所有项目或仅仅是直接项目的最直观方式是什么？区分两种意图的最少侵入性,最低摩擦的方式？

我的第一个目标是能够将这个LINQ提供者转变为对LINQ有一个平均理解的其他开发人员,并允许他们编写递归和列表查询,而不给他们编写递归lambda的教程.鉴于用法看起来不错,我可以针对该代码对代码进行编码.

另外澄清:(我真的在吮吸沟通!) - 这个LINQ提供程序是一个外部系统,它不仅仅是走一个对象图,在这个特定的情况下,递归表达式实际上转换成任何类型的真正的递归活动引擎盖下.只需要一种方法来区分"深层"查询和"浅层"查询.

那么,您认为表达它的最佳方式是什么？或者是否有一种标准的表达方式我错过了？

Answer 1

Linq-toXml处理这个很好,有一个XElement.Elements()/.Nodes()操作来获取直接子节点,还有一个XElement.Descendents()/ DescendentNodes()操作来获取所有后代.你会认为这是一个例子吗？

总结Linq-to-Xml的行为......每个导航函数对应于XPath中的轴类型(http://www.w3schools.com/xpath/xpath_axes.asp).如果导航功能选择元素,则使用轴名称.如果导航功能选择节点,则轴名称将与附加的节点一起使用.

例如,函数Descendants()和DescendantsNode()对应于XPath的后代轴,返回XElement或XNode.

例外情况并不奇怪是最常用的情况,即儿童轴.在XPath中,如果未指定轴,则使用此轴.为此,linq-to-xml导航功能不是Children()和ChildrenNodes(),而是Elements()和Nodes().

XElement是XNode的子类型.XNode包括HTML标签,还包括HTML注释,cdata或文本.XElements是一种XNode,但特指HTML标签.因此,XElements具有标记名称,并支持导航功能.

现在,在Linq-to-XML中链接导航并不像XPath那样容易.问题是导航功能返回集合对象,而导航功能则应用于非集合.考虑XPath表达式,它选择一个表标记作为直接子项,然后选择任何后代表数据标记.我认为这看起来像"./children::table/descendants::td"或"./table/descendants::td"

使用IEnumerable <> :: SelectMany()可以调用集合上的导航函数.等同于上面的内容类似于.Elements("table").SelectMany(T => T.Descendants("td"))

Answer 2

嗯,首先要注意的是,实际上,lambda表达式可以是递归的.不,老实说!这样做并不容易,当然也不容易阅读 - 大多数LINQ提供程序(除了LINQ-to-Objects,它更简单)只会看着它咳嗽......但它是可能.请看这里的完整,血腥的细节(警告 - 很可能是脑痛).

然而!!这可能无济于事......对于一个实用的方法,我会看看XElement它的方式等...注意你可以使用Queue<T>或删除一些递归Stack<T>:

using System;
using System.Collections.Generic;

static class Program {
    static void Main() {
        Node a = new Node("a"), b = new Node("b") { Children = {a}},
            c = new Node("c") { Children = {b}};
        foreach (Node node in c.Descendents()) {
            Console.WriteLine(node.Name);
        }
    }
}

class Node { // very simplified; no sanity checking etc
    public string Name { get; private set; }
    public List<Node> Children { get; private set; }
    public Node(string name) {
        Name = name;
        Children = new List<Node>();
    }
}
static class NodeExtensions {
    public static IEnumerable<Node> Descendents(this Node node) {
        if (node == null) throw new ArgumentNullException("node");
        if(node.Children.Count > 0) {
            foreach (Node child in node.Children) {
                yield return child;
                foreach (Node desc in Descendents(child)) {
                    yield return desc;
                }
            }
        }
    }
}

另一种方法是编写类似的东西SelectDeep(模仿SelectMany单个级别):

public static class EnumerableExtensions
{
    public static IEnumerable<T> SelectDeep<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        foreach (T item in source)
        {
            yield return item;
            foreach (T subItem in SelectDeep(selector(item),selector))
            {
                yield return subItem;
            }
        }
    }
}
public static class NodeExtensions
{
    public static IEnumerable<Node> Descendents(this Node node)
    {
        if (node == null) throw new ArgumentNullException("node");
        return node.Children.SelectDeep(n => n.Children);
    }
}

同样,我没有对此进行优化以避免递归,但它可以很容易地完成.

Answer 3

我会以这样的方式实现它,以便控制我想要查询的深度.

像Descendants()这样的东西会通过所有级别检索后代,而Descendants(0)会检索直接的孩子,Descendants(1)会得到孩子和孙子等等......