Exprimant récursion dans LINQ

Question

Je suis en train d'écrire un fournisseur de LINQ à une source de données hiérarchisé. Je trouve qu'il est plus facile de concevoir mon API en écrivant des exemples montrant comment je veux l'utiliser, puis de codage pour soutenir les cas d'utilisation.

Une chose que je ne parviens pas à avec un moyen facile / réutilisable / élégant pour exprimer « une requête en profondeur » ou récursion dans un communiqué LINQ. En d'autres termes, quelle est la meilleure façon de faire la distinction entre:

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

par rapport à:

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

( Edit:. S'il vous plaît noter qu'aucun de ces exemples ci-dessus reflètent pas nécessairement la structure de la requête que je veux, je suis intéressé par une bonne moyen d'exprimer récursion / profondeur )

S'il vous plaît noter Je ne demande pas comment mettre en œuvre un tel fournisseur, ou comment écrire mon IQueryable ou IEnumerable de telle manière à permettre récursivité. Je demande du point de vue d'une personne qui écrit la requête LINQ et d'utiliser mon fournisseur - ce qui est une manière intuitive pour eux d'exprimer si elles veulent ou non récursif

La structure de données ressemble à un système de fichiers typique: un dossier peut contenir une collection de sous-dossiers et un dossier peut également contenir une collection d'éléments. Alors myFolder.Folders représente tous les dossiers qui sont des enfants immédiats de myFolder et MyFolder.Items contient tous les éléments immédiatement dans myFolder. Voici un exemple de base d'un hierachy site, tout comme un système de fichiers avec des dossiers et pages:

(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 je vous écris:

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

Quelle est la manière la plus intuitive pour exprimer une intention que la requête obtenir tous les éléments en dessous des camions légers, ou seulement ceux immédiats? Le moins intrusif, façon de distinguer le plus bas coefficient de frottement entre les deux intentions?

Mon objectif n ° 1 est d'être en mesure de transformer ce fournisseur de LINQ à d'autres développeurs qui ont une compréhension moyenne de LINQ et leur permettent d'écrire à la fois des requêtes récursives et la liste sans leur donner un tutoriel sur l'écriture lambdas récursives. Étant donné un usage qui semble bon, je peux coder le fournisseur contre cela.

Des précisions supplémentaires: (je suis en train de sucer vraiment à communiquer cela!) - Le fournisseur de LINQ est à un système externe, il ne marche pas simplement un objet graphique, ni dans ce cas précis fait un récursif expression se traduisent effectivement une sorte de véritable activité récurrente sous le capot. Juste besoin d'un moyen de faire la distinction entre une requête « profonde » et une « superficielle ».

Alors, que pensez-vous est la meilleure façon de l'exprimer? Ou est-il un moyen standard de l'exprimer que je l'ai raté?

Answer 1

LINQ toXml gère cette amende, il y a un XElement.Elements () /. Opération Nodes () pour obtenir les enfants immédiats, et une opérations XElement.Descendents () / DescendentNodes () pour obtenir tous les descendants. Voulez-vous considérer cela comme un exemple?

Pour résumer le comportement de Linq à Xml ... Les fonctions de navigation correspondent chacune à un type d'axe XPath ( http://www.w3schools.com/xpath/xpath_axes.asp ). Si la fonction de navigation sélectionne les éléments, le nom de l'axe est utilisé. Si la fonction de navigation sélectionne les nœuds, le nom de l'axe est utilisé avec nœud en annexe.

Par exemple, il existe des fonctions Descendants () et DescendantsNode () correspondent à des descendants de XPath axe, soit un retour XElement ou un XNode.

Le cas d'exception est sans surprise le cas le plus utilisé, les enfants axe. Dans XPath, c'est l'axe utilisé si aucun axe est spécifié. Pour cela, les fonctions de navigation LINQ-to-xml ne sont pas des enfants () et ChildrenNodes () mais plutôt des éléments () et noeuds ().

XElement est un sous-type de XNode. de XNode comprennent des choses comme des balises HTML, mais aussi les commentaires HTML, CDATA ou texte. XElements sont un type de XNode, mais se réfèrent spécifiquement à des balises HTML. XElements ont donc un nom de tag, et prennent en charge les fonctions de navigation.

Maintenant, ce ne est pas aussi facile à la chaîne dans LINQ navigations à XML comme il est XPath. Le problème est que les fonctions de navigation renvoient des objets de collection, tandis que les fonctions de navigation sont appliqués aux non-collections. Considérez l'expression XPath qui sélectionne une étiquette de table comme un enfant immédiat alors une étiquette de données de table descendant. Je pense que cela ressemblerait « ./children::table/descendants::td » ou « ./table/descendants::td »

Utilisation IEnumerable <> :: SelectMany () permet d'appeler les fonctions de navigation sur une collection. L'équivalent à l'air au-dessus de quelque chose comme .elements ( "table"). SelectMany (T => T.Descendants ( "td"))

Answer 2

Eh bien, la première chose à noter est que en fait, les expressions lambda peuvent être récursive. Non, honnêtement! Il est pas facile à faire, et certainement n'est pas facile à lire - Heck, la plupart des fournisseurs LINQ (sauf LINQ-à-objets, ce qui est beaucoup plus simple) aura un ajustement toux juste regarder ... mais il est possible . Voir ici pour l'ensemble, gore détails (avertissement - mal au cerveau est probable)

.

Cependant !! Ce ne sera probablement pas beaucoup d'aide ... pour une approche pratique, je regarde la façon XElement etc ... il ne Notez que vous pouvez retirer une partie de la récursivité en utilisant un Queue<T> ou 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;
                }
            }
        }
    }
}

---

Une alternative serait d'écrire quelque chose comme SelectDeep (pour imiter SelectMany pour les niveaux individuels):

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

Encore une fois, je ne l'ai pas optimisé cela pour éviter récursion, mais il pourrait être fait assez facilement.

Answer 3

Je partirais avec la mise en œuvre de telle manière à avoir le contrôle sur à quel point je veux interroger aussi bien.

Quelque chose comme Descendants () récupérerait Descendants à tous les niveaux en Descendants (0) récupérerait les enfants immédiats, les descendants (1) obtiendraient les enfants et les petits-enfants et ainsi de suite ...

Answer 4

Je voudrais juste mettre en œuvre deux fonctions de distinguer clairement entre les deux options (enfants contre FullDecendants), ou un GetChildren de surcharge (de returnDecendants booléens). Chacun peut mettre en œuvre IEnumerable, il serait donc juste une question de fonction qu'ils passent dans leur déclaration LINQ.

Answer 5

Vous pouvez mettre en œuvre une (extension) Méthode comme FlattenRecusively pour votre type.

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

Answer 6

Rex, vous avez certainement ouvert une discussion intéressante, mais vous semblez avoir éliminé toutes les possibilités - qui est, vous semblez rejeter à la fois  (1) ayant le consommateur écrire logique récursive, et  (2) ayant votre classe de noeud exposer les relations de plus d'un degré.

Ou, vous avez peut-être pas tout à fait exclu (2). Je peux penser à une approche plus qui est presque aussi expressive que la méthode GetDescendents (ou bien), mais peut-être pas tout à fait aussi « pesante » (selon la forme de votre arbre) ...

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

et

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

Answer 7

Je suis d'accord avec Frank. un coup d'oeil sur la façon dont LINQ à XML gère ces scénarios.

En fait, j'émulent la mise en œuvre LINQ à XML entièrement, mais changer pour tout type de données. Pourquoi réinventer la roue droite?

Answer 8

Êtes-vous d'accord avec le fait soulever des objets lourds dans votre objet? (Il est même pas lourd)

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

Je voudrais simplement utiliser une méthode d'extension pour parcourir l'arborescence.

Oh, attends, je fais déjà ! :)