Выражение рекурсии в 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
Какой самый интуитивно понятный способ выразить намерение, чтобы запрос получил все элементы под Light Trucks или только непосредственные? Наименьший навязчивый способ различения двух намерений?
Моя главная цель - предоставить этого провайдера LINQ другим разработчикам, которые в среднем понимают LINQ, и позволяют им писать как рекурсивные, так и списочные запросы, не давая им учебника по написанию рекурсивных лямбд. Учитывая использование, которое выглядит хорошо, я могу закодировать провайдера против этого.
Дополнительное пояснение: (я действительно отстой в сообщении этого!) - Этот поставщик LINQ предназначен для внешней системы, он не просто просматривает граф объектов, и в данном конкретном случае рекурсивное выражение фактически не переводится в какую-либо реальную рекурсивную деятельность. под капотом. Просто нужен способ отличить "глубокий" запрос от "мелкого".
Итак, что вы думаете, это лучший способ выразить это? Или есть стандартный способ выразить это, что я пропустил?
9 ответов
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("таблица").SelectMany(T => T.Descendants("td"))
Ну, во-первых, стоит отметить, что на самом деле лямбда-выражения могут быть рекурсивными. Нет, честно! Это нелегко сделать и, конечно же, не легко прочитать - черт, у большинства провайдеров 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);
}
}
Опять же, я не оптимизировал это, чтобы избежать рекурсии, но это можно сделать достаточно легко.
Я хотел бы реализовать его таким образом, чтобы контролировать, насколько глубоко я хочу делать запросы.
Нечто подобное Descendants() будет извлекать Descendants через все уровни, в то время как Descendants(0) будет извлекать непосредственных детей, Descendants(1) получит детей и внуков и так далее...
Возможно, вы захотите реализовать (расширение) метод, как FlattenRecusively для вашего типа.
from item in list.FlattenRecusively() where ... select item
Я бы просто реализовал две функции, чтобы четко различать эти две опции (Children vs. FullDecendants) или перегружать GetChildren(bool returnDecendants). Каждый может реализовать IEnumerable, так что было бы просто вопрос, какую функцию они передадут в оператор LINQ.
Рекс, ты, конечно, открыл интересную дискуссию, но ты, кажется, упустил все возможности - то есть, ты, кажется, отвергаешь и (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, но изменил бы ее для любого типа данных. Зачем изобретать велосипед правильно?
Вы в порядке с выполнением тяжелой работы на вашем объекте? (это даже не так тяжело)
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
}
}