在LINQ中表达递归
我正在为一个分层数据源编写一个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
什么是最直观的方式来表达查询获得轻型卡车下面的所有项目或只有直接项目的意图？ 区分两种意图的最少侵入性，摩擦最小的方法？
我的第一个目标是能够将这个LINQ提供者转变为对LINQ有一个平均理解的其他开发人员，并允许他们编写递归和列表查询，而不给他们编写递归lambda的教程。 鉴于用法看起来不错，我可以针对该代码对代码进行编码。
另外澄清:(我真的很想通信这个！） – 这个LINQ提供程序是一个外部系统，它不是简单地走一个对象图，也不是在这种特定情况下，递归表达式实际上转换成任何类型的真正的递归活动在引擎盖下。 只需要一种方法来区分“深层”查询和“浅层”查询。
那么，您认为表达它的最佳方式是什么？ 或者是否有一种标准的表达方式我错过了？
Linq-toXml处理这个很好，有一个XElement.Elements（）/。Nodes（）操作来获取直接子节点，并有一个XElement.Descendents（）/ DescendentNodes（）操作来获取所有后代。 你会认为这是一个例子吗？
总结Linq-to-Xml的行为……每个导航函数对应于XPath中的轴类型（ http://www.w3schools.com/xpath/xpath_axes.asp ）。 如果导航function选择“元素”，则使用轴名称。 如果导航function选择节点，则轴名称将与附加的节点一起使用。
例如，函数Descendants（）和DescendantsNode（）对应于XPath的后代轴，返回XElement或XNode。
例外情况并不奇怪，最常用的情况是儿童轴。 在XPath中，如果未指定轴，则使用此轴。 为此，linq-to-xml导航function不是Children（）和ChildrenNodes（），而是Elements（）和Nodes（）。
XElement是XNode的子类型。 XNode包括HTML标签，还包括HTML注释，cdata或文本。 XElements是一种XNode，但特指HTML标签。 因此，XElements具有标记名称，并支持导航function。
现在，在Linq-to-XML中链接导航并不像XPath那么容易。 问题是导航function返回集合对象，而导航function则应用于非集合。 考虑XPath表达式，它选择一个表标记作为直接子项，然后选择任何后代表数据标记。 我认为这看起来像“./children::table/descendants::td”或“./table/descendants::td”
使用IEnumerable <> :: SelectMany（）可以调用集合上的导航函数。 等同于上面的内容类似于.Elements（“table”）。SelectMany（T => T.Descendants（“td”））
嗯，首先要注意的是，实际上，lambda表达式可以是递归的。 不，老实说！ 这样做并不容易， 当然也不容易阅读 – 大多数LINQ提供程序（除了LINQ-to-Objects，它更简单）只会看着它咳嗽……但它是可能 。 请看这里的完整，血腥的细节（警告 – 很可能是脑痛）。
然而！！ 这可能无济于事……对于一个实用的方法，我会看看XElement等的方式…注意你可以使用Queue或Stack删除一些递归：
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 Children { get; private set; } public Node(string name) { Name = name; Children = new List (); } } static class NodeExtensions { public static IEnumerable 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 SelectDeep ( this IEnumerable source, Func> 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 Descendents(this Node node) { if (node == null) throw new ArgumentNullException("node"); return node.Children.SelectDeep(n => n.Children); } }
同样，我没有对此进行优化以避免递归，但它可以很容易地完成。
我会以这样的方式实现它，以便控制我想要查询的深度。
像Descendants（）这样的东西会通过所有级别检索后代，而Descendants（0）会检索直接的孩子，Descendants（1）会得到孩子和孙子等等……
我只想实现两个函数来清楚地区分两个选项（Children vs. FullDecendants），或者重载GetChildren（bool returnDecendants）。 每个都可以实现IEnumerable，因此它只是将它们传递到LINQ语句中的函数。
您可能希望为您的类型实现FlattenRecusively（扩展）方法。
from item in list.FlattenRecusively() where ... select item
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
我不得不同意弗兰克。 看看LINQ-to-XML如何处理这些场景。
实际上，我完全模仿LINQ-to-XML实现，但是对于任何Data类型都要进行更改。 为什么重新发明轮子？
您是否可以在物体中进行繁重的操作？ （它甚至不那么沉重）
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 { 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 _children; public List Children { get { if (_children == null) _children = new List (); return _children; } } public override string ToString() { return Name + " " + _id.ToString(); } #region IEnumerable Members public IEnumerator 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 } }
我只是使用扩展方法来遍历树。
哦等等，我已经这样做了 ！ 🙂