bloc itérateur à LINQ

Question

Je vais avoir du mal à trouver la bonne syntaxe LINQ à utiliser pour le bloc itérateur suivant:

class Program 
{ 
    class Operation 
    { 
     public IEnumerable<Operation> NextOperations { get; private set; } 
    } 
    class Item { } 

    static Item GetItem(Operation operation) 
    { 
     return new Item(); 
    } 

    static IEnumerable<Item> GetItems(IEnumerable<Operation> operations) 
    { 
     foreach (var operation in operations) 
     { 
      yield return GetItem(operation); 

      foreach (var item in GetItems(operation.NextOperations)) // recursive 
       yield return item; 
     } 
    } 

    static void Main(string[] args) 
    { 
     var operations = new List<Operation>(); 
     foreach (var item in GetItems(operations)) 
     { 
     } 
    } 
} 

Peut-être ce que je suis est aussi bon qu'il obtient? Pour ce code particulier, yield return à l'intérieur d'un foreach explicite est en effet la bonne solution?

Answer 1

Peut-être que ce que j'ai est aussi bon que possible?

C'est plutôt bien. Nous pouvons le rendre légèrement meilleur.

Pour ce code particulier, le rendement de rendement dans une foreach explicite est-il vraiment la bonne solution?

C'est une solution raisonnable. C'est facile à lire et à corriger clairement. L'inconvénient est, comme je l'ai mentionné plus tôt, que la performance n'est potentiellement pas bonne si l'arbre est extrêmement profond.

Voilà comment je ferais ceci:

static IEnumerable<T> AllNodes(this T root, Func<T, IEnumerable<T>> getChildren) 
{ 
    var stack = new Stack<T>(); 
    stack.Push(root); 
    while(stack.Count > 0) 
    { 
     var current = stack.Pop(); 
     yield return current; 
     foreach(var child in getChildren(current).Reverse()) 
      stack.Push(child); 
    } 
} 

static void Main()  
{  
    var operation = whatever; 
    var items = from op in operation.AllNodes(x=>x.NextOperations) 
       select GetItem(op); 
    foreach (var item in items)  
    {  
    }  
} 

Notez que l'appel à la marche arrière() est nécessaire que si vous vous souciez que l'itération go « pour ». Par exemple, supposons que l'opération Alpha ait des opérations enfants Beta, Gamma et Delta, et Delta a des enfants Zeta et Omega. Le parcours se présente comme suit:

push Alpha 
pop Alpha 
yield Alpha 
push Delta 
push Gamma 
push Beta 
pop Beta 
yield Beta 
pop Gamma 
yield Gamma 
pop Delta 
yield Delta 
push Omega 
push Zeta 
pop Zeta 
yield Zeta 
pop Omega 
yield Omega 

et maintenant la pile est vide donc nous avons fini, et nous obtenons les éléments dans l'ordre « précommande traversal ». Si vous ne vous souciez pas de la commande, si tout ce dont vous avez besoin est de vous assurer que vous les obtenez tous, alors ne vous embêtez pas à Inverser les enfants, et vous les obtiendrez dans l'ordre Alpha, Delta, Omega, Zeta , Gamma, Beta.

Avez-vous du sens?

Answer 2

Je pense que votre implémentation est bonne. Cependant, si vous voulez utiliser LINQ (et le raccourcir un peu - mais pas de manière significative), vous pouvez implémenter GetItems en utilisant une requête qui répète toutes les opérations et retourne l'élément courant suivi de tous les autres éléments générés récursivement:

static IEnumerable<Item> GetItems(IEnumerable<Operation> operations) 
{ 
    return from op in operations 
      from itm in (new[] { GetItem(op) }).Concat 
         (GetItems(op.NextOperations)); 
      select itm; 
} 

Pour chaque opération, nous générons une séquence contenant l'élément pour le courant suivi de tous les éléments générés récursivement. En utilisant une clause from imbriquée, vous pouvez itérer sur cette collection pour obtenir une structure "plate".

Je pense que vous pourriez rendre un peu plus agréable en utilisant une liste fonctionnelle (immuable) qui supporte l'opération pour "ajouter un élément à l'avant" - ce qui est exactement ce que nous faisons dans le from imbriqué. L'utilisation FuncList from my functional programming livre (ce n'est plus séquence paresseux cependant):

static FuncList<Item> GetItems(IEnumerable<Operation> operations) 
{ 
    return (from op in operations 
      from itm in FuncList.Cons(GetItem(op), GetItems(op.NextOperations)); 
      select itm).AsFuncList(); 
} 

Comme Jon mentionné, il n'y a pas de bonne façon d'écrire l'aspect récursif en utilisant la requête (vous pouvez écrire requête récursive en utilisant des fonctions lambda au lieu des méthodes - mais ce n'est pas beaucoup mieux).

Answer 3

LINQ n'est généralement pas bon en récursivité, en utilisant les opérateurs de requête standard. Vous pouvez écrire un formulaire d'objectif plus général de ce qui précède, mais vous ne trouverez pas un moyen standard LINQ propre à faire cette traversée.