26

我正在为分层数据源编写 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

表达查询获取轻型卡车下的所有项目或仅直接项目的意图的最直观方式是什么？区分这两种意图的侵入性最小、摩擦最小的方法是什么？

我的 #1 目标是能够将此 LINQ 提供程序转交给对 LINQ 有平均理解的其他开发人员，并允许他们编写递归和列表查询，而无需向他们提供编写递归 lambda 的教程。给定一个看起来不错的用法，我可以对提供程序进行编码。

附加说明：（我真的很讨厌交流这个！） - 这个 LINQ 提供程序是针对外部系统的，它不仅仅是遍历对象图，在这种特定情况下，递归表达式实际上也不会转化为任何类型的真正递归活动在引擎盖下。只需要一种方法来区分“深”查询和“浅”查询。

那么，你认为最好的表达方式是什么？还是有一种我错过的标准表达方式？

4

9 回答 9

20

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"))

于 2009-04-08T23:37:18.397 回答
19

嗯，首先要注意的是，实际上，lambda 表达式可以是递归的。不，老实说！这不容易做到，当然也不容易阅读 - 哎呀，大多数 LINQ 提供程序（LINQ-to-Objects 除外，它更简单）只是看着它就会咳嗽......但它是可能的。请参阅此处了解完整的血腥细节（警告 - 可能会导致脑痛）。

然而！！这可能不会有太大帮助......对于一种实用的方法，我会看看它的方式等等......注意你可以使用 a orXElement删除一些递归：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);
    }
}

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

于 2009-04-27T13:39:56.400 回答
6

我会以这样一种方式来实现它，以便控制我想要查询的深度。

像 Descendants() 这样的东西会通过所有级别检索 Descendants，而 Descendants(0) 会检索直系子女， Descendants(1) 会获得子女和孙子女等等......

于 2009-04-08T23:49:53.060 回答
3

我将只实现两个函数来清楚地区分这两个选项（Children 与 FullDecendants），或者重载 GetChildren(bool returnDecendants)。每个都可以实现 IEnumerable，因此只需将哪个函数传递给其 LINQ 语句即可。

于 2009-04-08T23:40:16.860 回答
3

您可能希望为您的类型实现一个（扩展）方法，如 FlattenRecusively。

from item in list.FlattenRecusively() where ... select item
于 2009-04-29T16:00:07.420 回答
3

Rex，您当然开启了一个有趣的讨论，但您似乎已经消除了所有可能性 - 也就是说，您似乎拒绝（1）让消费者编写递归逻辑，以及（2）让您的节点类公开更大的关系超过一度。

或者，也许您还没有完全排除 (2)。我可以想到另一种方法，它几乎与 GetDescendents 方法（或属性）一样具有表现力，但可能不会那么“笨重”（取决于树的形状）......

from item in AllItems where item.Parent == currentNode select item

和

from item in AllItems where item.Ancestors.Contains(currentNode) select item
于 2009-04-30T03:27:07.393 回答
2

我不得不同意弗兰克的观点。看看 LINQ-to-XML 如何处理这些场景。

事实上，我会完全模拟 LINQ-to-XML 实现，但要针对任何数据类型进行更改。为什么要重新发明轮子？

于 2009-04-09T00:13:23.987 回答
1

你可以在你的物体上做繁重的工作吗？（它甚至没有那么重）

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace LinqRecursion
{
    class Program
    {
        static void Main(string[] args)
        {
            Person mom = new Person() { Name = "Karen" };
            Person me = new Person(mom) { Name = "Matt" };
            Person youngerBrother = new Person(mom) { Name = "Robbie" };
            Person olderBrother = new Person(mom) { Name = "Kevin" };
            Person nephew1 = new Person(olderBrother) { Name = "Seth" };
            Person nephew2 = new Person(olderBrother) { Name = "Bradon" };
            Person olderSister = new Person(mom) { Name = "Michelle" };

            Console.WriteLine("\tAll");
            //        All
            //Karen 0
            //Matt 1
            //Robbie 2
            //Kevin 3
            //Seth 4
            //Bradon 5
            //Michelle 6
            foreach (var item in mom)
                Console.WriteLine(item);

            Console.WriteLine("\r\n\tOdds");
            //        Odds
            //Matt 1
            //Kevin 3
            //Bradon 5
            var odds = mom.Where(p => p.ID % 2 == 1);
            foreach (var item in odds)
                Console.WriteLine(item);

            Console.WriteLine("\r\n\tEvens");
            //        Evens
            //Karen 0
            //Robbie 2
            //Seth 4
            //Michelle 6
            var evens = mom.Where(p => p.ID % 2 == 0);
            foreach (var item in evens)
                Console.WriteLine(item);

            Console.ReadLine();

        }
    }

    public class Person : IEnumerable<Person>
    {
        private static int _idRoot;

        public Person() {
            _id = _idRoot++;
        }

        public Person(Person parent) : this()
        {
            Parent = parent;
            parent.Children.Add(this);
        }

        private int _id;
        public int ID { get { return _id; } }
        public string Name { get; set; }

        public Person Parent { get; private set; }

        private List<Person> _children;
        public List<Person> Children
        {
            get
            {
                if (_children == null)
                    _children = new List<Person>();
                return _children;
            }
        }

        public override string ToString()
        {
            return Name + " " + _id.ToString();
        }

        #region IEnumerable<Person> Members

        public IEnumerator<Person> GetEnumerator()
        {
            yield return this;
            foreach (var child in this.Children)
                foreach (var item in child)
                    yield return item;
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        #endregion
    }
}
于 2009-04-30T01:19:20.943 回答
0

我只是使用扩展方法来遍历树。

哦，等等，我已经在这样做了！:)

于 2009-04-30T04:30:12.157 回答