C# 在 LINQ 中表达递归

Expressing recursion in LINQ

提问by Rex M

I am writing a LINQ provider to a hierarchal data source. I find it easiest to design my API by writing examples showing how I want to use it, and then coding to support those use cases.

我正在为分层数据源编写 LINQ 提供程序。我发现通过编写示例展示我想如何使用它来设计我的 API 是最简单的，然后编码以支持这些用例。

One thing I am having trouble with is an easy/reusable/elegant way to express "deep query" or recursion in a LINQ statement. In other words, what is the best way to distinguish between:

我遇到的一件事是在 LINQ 语句中用一种简单/可重用/优雅的方式来表达“深度查询”或递归。换句话说，区分的最佳方法是什么：

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

versus:

相对：

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

(Edit: please note neither of those examples above necessarily reflect the structure of the query I want. I am interested in anygood way to express recursion/depth)

（编辑：请注意上面的那些例子都不一定反映我想要的查询的结构。我对任何表达递归/深度的好方法感兴趣）

Please noteI am not asking how to implement such a provider, or how to write my IQueryable or IEnumerable in such a way that allows recursion. I am asking from the standpoint of a person writing the LINQ query and utilizing my provider - what is an intuitive way for them to express whether they want to recurse or not?

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

The data structure resembles a typical file system: a folder can contain a collection of subfolders, and a folder can also contain a collection of items. So myFolder.Folders represents all the folders who are immediate children of myFolder, and myFolder.Items contains all the items immediately within myFolder. Here's a basic example of a site hierachy, much like a filesystem with folders and pages:

数据结构类似于典型的文件系统：文件夹可以包含子文件夹的集合，文件夹也可以包含项目的集合。因此，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 

If I write:

如果我写：

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

What is the most intuitive way to express an intent that the query get all items underneath Light Trucks, or only the immediate ones? The least-intrusive, lowest-friction way to distinguish between the two intents?

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

My #1 goal is to be able to turn this LINQ provider over to other developers who have an average understanding of LINQ and allow them to write both recursive and list queries without giving them a tutorial on writing recursive lambdas. Given a usage that looks good, I can code the provider against that.

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

Additional clarification:(I am really sucking at communicating this!) - This LINQ provider is to an external system, it is not simply walking an object graph, nor in this specific case does a recursive expressionactually translate into any kind of true recursive activity under the hood. Just need a way to distinguish between a "deep" query and a "shallow" one.

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

So, what do you think is the best way to express it? Or is there a standard way of expressing it that I've missed out on?

那么，你认为最好的表达方式是什么？或者有没有我错过的标准表达方式？

采纳答案by Frank Schwieterman

Linq-toXml handles this fine, there is an XElement.Elements()/.Nodes() operation to get immediate children, and a XElement.Descendents()/DescendentNodes() operations to get all descendents. Would you consider that as an example?

Linq-toXml 可以很好地处理这个问题，有一个 XElement.Elements()/.Nodes() 操作来获取直接子元素，还有一个 XElement.Descendents()/DescendentNodes() 操作来获取所有后代。你会认为这是一个例子吗？

To summarize Linq-to-Xml's behavior... The navigation functions each correspond to an axis type in XPath (http://www.w3schools.com/xpath/xpath_axes.asp). If the navigation function selects Elements, the axis name is used. If the navigation function selects Nodes, the axis name is used with Node appended.

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

For instance, there are functions Descendants() and DescendantsNode() correspond to XPath's descendants axis, returning either an XElement or an XNode.

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

The exception case is not surprisingly the most used case, the children axis. In XPath, this is the axis used if no axis is specified. For this, the linq-to-xml navigation functions are not Children() and ChildrenNodes() but rather Elements() and Nodes().

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

XElement is a subtype of XNode. XNode's include things like HTML tags, but also HTML comments, cdata or text. XElements are a type of XNode, but refer specifically to HTML tags. XElements therefore have a tag name, and support the navigation functions.

XElement 是 XNode 的子类型。XNode 包括 HTML 标签之类的内容，但也包括 HTML 注释、cdata 或文本。XElements 是一种 XNode，但特指 HTML 标签。XElements 因此有一个标签名，并支持导航功能。

Now its not as easy to chain navigations in Linq-to-XML as it is XPath. The problem is that navigation functions return collection objects, while the navigation functions are applied to non-collections. Consider the XPath expression which selects a table tag as an immediate child then any descendant table data tag. I think this would look like "./children::table/descendants::td" or "./table/descendants::td"

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

Using IEnumerable<>::SelectMany() allows one to call the navigation functions on a collection. The equivalent to the above looks something like .Elements("table").SelectMany(T => T.Descendants("td"))

使用 IEnumerable<>::SelectMany() 允许在集合上调用导航函数。相当于上面的看起来像 .Elements("table").SelectMany(T => T.Descendants("td"))

回答by Reed Copsey

I would just implement two functions to clearly differentiate between the two options (Children vs. FullDecendants), or an overload GetChildren(bool returnDecendants). Each can implement IEnumerable, so it would just be a matter of which function they pass into their LINQ statement.

我只会实现两个函数来清楚地区分这两个选项（Children 与 FullDecendants），或者重载 GetChildren(bool returnDecendants)。每个都可以实现 IEnumerable，所以这只是它们传递到 LINQ 语句中的函数的问题。

回答by SirDemon

I'd go with implementing it in such a way as to have control over how deeply I want to query as well.

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

Something like Descendants() would retrieve Descendants through all levels while Descendants(0) would retrieve immediate children, Descendants(1) would get children and grandchildren and so on...

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

回答by andy

I'd have to agree with Frank. have a look at how LINQ-to-XML handles these scenarios.

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

In fact, I'd emulate the LINQ-to-XML implementation entirely, but change it for any Data type. Why reinvent the wheel right?

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

回答by Marc Gravell

Well, the first thing to note is that actually, lambda expressions can be recursive. No, honestly! It isn't easy to do, and certainlyisn't easy to read - heck, most LINQ providers (except LINQ-to-Objects, which is much simpler) will have a coughing fit just looking at it... but it is possible. See herefor the full, gory details (warning - brain-ache is likely).

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

However!! That probably won't help much... for a practical approach, I'd look at the way XElementetc does it... note you can remove some of the recursion using a Queue<T>or Stack<T>:

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

---

---

An alternative would be to write something like SelectDeep(to mimic SelectManyfor single levels):

另一种方法是编写类似的内容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);
    }
}

Again, I haven't optimised this to avoid recursion, but it could be done easily enough.

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

回答by Thomas Danecker

You might want to implement a (extension) Method like FlattenRecusively for your type.

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

from item in list.FlattenRecusively() where ... select item

回答by Matthew Whited

Are you okay with doing the heavy lifting in your object? (it's not even that heavy)

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

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

回答by Av Pinzur

Rex, you've certainly opened an interesting discussion, but you seem to have eliminated all possibilities - that is, you seem to reject both (1) having the consumer write recursive logic, and (2) having your node class expose relationships of greater than one degree.

Rex，您确实开启了一个有趣的讨论，但您似乎排除了所有可能性——也就是说，您似乎拒绝 (1) 让消费者编写递归逻辑，以及 (2) 让您的节点类公开更大的关系比一个学位。

Or, perhaps you haven't entirely ruled out (2). I can think of one more approach which is nearly as expressive as the GetDescendents method (or property), but might not be quite so 'ponderous' (depending on the shape of your tree)...

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

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

and

和

from item in AllItems where item.Ancestors.Contains(currentNode) select item

回答by leppie

I simply would use an extension method to traverse the tree.

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

Oh wait, I am doing that already! :)

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