Expresando recursion en LINQ

Estoy escribiendo un proveedor LINQ a una fuente de datos jerárquica. Me resulta más fácil diseñar mi API escribiendo ejemplos que muestren cómo quiero usarla, y luego codificando para admitir esos casos de uso.

Una cosa con la que estoy teniendo problemas es con una manera fácil / reutilizable / elegante de express “consulta profunda” o recursión en una statement LINQ. En otras palabras, cuál es la mejor manera de distinguir entre:

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

versus:

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

( Editar: tenga en cuenta que ninguno de los ejemplos anteriores refleja necesariamente la estructura de la consulta que quiero. Estoy interesado en cualquier buena forma de express recursión / profundidad )

Tenga en cuenta que no estoy preguntando cómo implementar dicho proveedor, o cómo escribir mi IQueryable o IEnumerable de tal manera que permita la recursión. Estoy preguntando desde el punto de vista de una persona que escribe la consulta de LINQ y utiliza a mi proveedor: ¿cuál es una forma intuitiva para que ellos expresen si quieren o no recetar?

La estructura de datos se parece a un sistema de archivos típico: una carpeta puede contener una colección de subcarpetas, y una carpeta también puede contener una colección de elementos. Así que myFolder.Folders representa todas las carpetas que son hijos inmediatos de myFolder, y myFolder.Items contiene todos los elementos inmediatamente dentro de myFolder. Este es un ejemplo básico de una jerarquía de sitios, como un sistema de archivos con carpetas y páginas:

 (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 

Si escribo:

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

¿Cuál es la forma más intuitiva de express la intención de que la consulta obtenga todos los elementos debajo de Light Trucks, o solo los inmediatos? ¿La forma menos intrusiva y de menor fricción para distinguir entre los dos bashs?

Mi objective # 1 es poder entregar este proveedor de LINQ a otros desarrolladores que tienen un conocimiento promedio de LINQ y permitirles escribir consultas tanto recursivas como de listas sin darles un tutorial sobre cómo escribir lambdas recursivas. Dado un uso que se ve bien, puedo codificar al proveedor contra eso.

Aclaración adicional: (¡Realmente estoy chupando en comunicar esto!) – Este proveedor de LINQ es para un sistema externo, no es simplemente un gráfico de objetos, ni en este caso específico la expresión recursiva se traduce en ningún tipo de actividad recursiva real. bajo el capó. Solo necesita una forma de distinguir entre una consulta “profunda” y una “superficial”.

Entonces, ¿cuál crees que es la mejor manera de expresslo? ¿O hay una forma estándar de expresslo que me he perdido?

Linq-toXml maneja esta multa, hay una operación XElement.Elements () /. Nodes () para obtener hijos inmediatos, y una operación XElement.Descendents () / DescendentNodes () para obtener todos los descendientes. ¿Considerarías eso como un ejemplo?

Para resumir el comportamiento de Linq-to-xml … Cada una de las funciones de navegación corresponde a un tipo de eje en XPath ( http://www.w3schools.com/xpath/xpath_axes.asp ). Si la función de navegación selecciona Elementos, se utiliza el nombre del eje. Si la función de navegación selecciona Nodos, el nombre del eje se usa con el nodo adjunto.

Por ejemplo, hay funciones Descendants () y DescendantsNode () que corresponden al eje de descendientes de XPath, y devuelven un XElement o un XNode.

El caso de excepción no es sorprendentemente el caso más usado, el eje de los niños. En XPath, este es el eje utilizado si no se especifica ningún eje. Para esto, las funciones de navegación de linq-to-xml no son Children () y ChildrenNodes () sino más bien Elements () y Nodes ().

XElement es un subtipo de XNode. Los XNodos incluyen cosas como tags HTML, pero también comentarios HTML, datos o texto. Los XElementos son un tipo de XNodo, pero se refieren específicamente a tags HTML. Por lo tanto, XElements tiene un nombre de etiqueta y admite las funciones de navegación.

Ahora no es tan fácil encadenar navegaciones en Linq-to-XML como lo es XPath. El problema es que las funciones de navegación devuelven objetos de colección, mientras que las funciones de navegación se aplican a las no colecciones. Considere la expresión XPath que selecciona una etiqueta de tabla como un hijo inmediato y luego cualquier etiqueta de datos de la tabla descendiente. Creo que esto se vería como “./children::table/descendants::td” o “./table/descendants::td”

El uso de IEnumerable <> :: SelectMany () permite llamar a las funciones de navegación en una colección. El equivalente a lo anterior se parece a algo como .Elementos (“tabla”). SelectMany (T => T.Descendants (“td”))

Bueno, lo primero que se debe tener en cuenta es que, en realidad, las expresiones lambda pueden ser recursivas. ¡No, honestamente! No es fácil de hacer y, desde luego, no es fácil de leer. Caray, la mayoría de los proveedores de LINQ (excepto LINQ-to-Objects, que es mucho más simple) tendrán un ataque de tos con solo mirarlo … pero es posible Vea aquí los detalles completos y sangrientos (advertencia: es probable que tenga dolor de cerebro).

¡¡Sin embargo!! Eso probablemente no ayude mucho … para un enfoque práctico, vería la forma en que XElement etc. lo hace … tenga en cuenta que puede eliminar parte de la recursión usando una Queue o 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; } } } } } 

Una alternativa sería escribir algo como SelectDeep (para imitar a SelectMany para niveles individuales):

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

Nuevamente, no he optimizado esto para evitar la recursión, pero podría hacerse con la suficiente facilidad.

Me gustaría implementarlo de tal manera que tenga control sobre qué tan profundamente quiero consultar también.

Algo así como Descendientes () recuperaría Descendientes en todos los niveles, mientras que Descendientes (0) recuperaría hijos inmediatos, Descendientes (1) obtendría hijos y nietos y así sucesivamente …

Simplemente implementaría dos funciones para diferenciar claramente entre las dos opciones (Hijos vs. FullDecendants), o una sobrecarga GetChildren (bool returnDecendants). Cada uno puede implementar IEnumerable, por lo que sería solo una cuestión de qué función pasan a su statement LINQ.

Es posible que desee implementar un método (extensión) como FlattenRecusively para su tipo.

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

Rex, ciertamente ha abierto una discusión interesante, pero parece haber eliminado todas las posibilidades, es decir, parece rechazar ambas (1) que el consumidor escriba la lógica recursiva, y (2) que su clase de nodo exponga relaciones de mayor de un grado.

O, quizás no lo hayas descartado por completo (2). Puedo pensar en un enfoque más que sea casi tan expresivo como el método (o propiedad) de GetDescendents, pero podría no ser tan ‘pesado’ (dependiendo de la forma de su árbol) …

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

y

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

Tendría que estar de acuerdo con Frank. Eche un vistazo a cómo LINQ-to-XML maneja estos escenarios.

De hecho, emularía la implementación de LINQ-to-XML por completo, pero la cambiaría por cualquier tipo de datos. ¿Por qué reinventar la rueda a la derecha?

¿Estás de acuerdo con hacer el trabajo pesado en tu objeto? (Ni siquiera es tan pesado)

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

Simplemente usaría un método de extensión para atravesar el árbol.

Oh, espera, ya estoy haciendo eso ! 🙂