Выражение рекурсии в LINQ

Question

Я пишу провайдеру 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 или только непосредственные? Наименее навязчивый способ различения двух намерений с наименьшим трением?

Моя цель № 1 - предоставить этого провайдера LINQ другим разработчикам, которые в среднем понимают LINQ, и позволяют им писать как рекурсивные, так и списочные запросы, не давая им учебника по написанию рекурсивных лямбд. Учитывая использование, которое выглядит хорошо, я могу закодировать провайдера против этого.

Дополнительные пояснения: (Я действительно отстой, когда сообщаю об этом!) - Этот поставщик LINQ предназначен для внешней системы, он не просто просматривает граф объектов, а в данном конкретном случае рекурсивен выражение фактически переводится в любой реальный рекурсивный вид деятельности под капотом. Просто нужен способ различить «глубокий» запрос и «неглубокий».

Итак, что, по вашему мнению, является лучшим способом выразить это? Или есть стандартный способ выразить это, что я пропустил?

Answer 1

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 () позволяет вызывать функции навигации в коллекции. Эквивалент вышеупомянутого выглядит примерно так:

Answer 2

Ну, первое, что нужно отметить, это то, что на самом деле лямбда-выражения могут быть рекурсивными. Нет, честно! Это нелегко сделать, и , конечно, нелегко прочитать - черт, у большинства поставщиков 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);
    }
}

Опять же, я не оптимизировал это, чтобы избежать рекурсии, но это можно сделать достаточно легко.

Answer 3

Я бы хотел реализовать его таким образом, чтобы контролировать, насколько глубоко я хочу делать запросы.

Что-то вроде Descendants () будет извлекать Descendants через все уровни, тогда как Descendants (0) будет извлекать непосредственных детей, Descendants (1) получит детей, внуков и т. Д.

Answer 4

Рекс, вы, конечно, открыли интересную дискуссию, но вы, кажется, исключили все возможности - то есть, вы, кажется, отвергли оба (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

Answer 5

Возможно, вы захотите реализовать метод (расширение), такой как FlattenRecusively для вашего типа.

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

Answer 6

Я бы просто реализовал две функции, чтобы четко различать два параметра («Дети» против «FullDecendants») или перегрузку GetChildren (bool returnDecendants). Каждый из них может реализовывать IEnumerable, поэтому вопрос о том, какую функцию они передадут в свой оператор LINQ, будет зависеть.

Answer 7

Я бы согласился с Фрэнком. посмотрите, как LINQ-to-XML обрабатывает эти сценарии.

Фактически, я бы полностью эмулировал реализацию LINQ-to-XML, но изменил бы ее для любого типа данных. Зачем изобретать велосипед правильно?

Answer 8

Вы в порядке с выполнением тяжелой работы на вашем объекте? (это даже не так тяжело)

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

Answer 9

Я бы просто использовал метод расширения для обхода дерева.

Ой, подождите, я делаю , что уже ! :)