Función de recursividad LINQ?

Question

Tomemos esta estructura profunda de n niveles, por ejemplo:

public class SomeItem 
{ 
    public Guid ID { get;set; } 
    public string Name { get; set; } 
    public bool HasChildren { get;set; } 
    public IEnumerable<SomeItem> Children { get; set; } 
} 

Si yo estoy mirando para conseguir un artículo en particular por ID (en cualquier parte de la estructura) ¿hay algo de bondad LINQ que puedo utilizar para obtener fácilmente en un solo estado o tengo que utilizar alguna función recursiva de la siguiente manera:

private SomeItem GetSomeItem(IEnumerable<SomeItem> items, Guid ID) 
    { 
     foreach (var item in items) 
     { 
      if (item.ID == ID) 
      { 
       return item; 
      } 
      else if (item.HasChildren) 
      { 
       return GetSomeItem(item.Children, ID); 
      } 
     } 
     return null; 
    } 

Answer 1

LINQ en realidad no "hacer" recursividad muy bien. Su solución parece apropiada, aunque no estoy seguro de que HasChildren realmente se requiera ... ¿por qué no usar una lista vacía para un artículo sin hijos?

Una alternativa es escribir un método DescendantsAndSelf que devolverá todos de los descendientes (incluyendo el propio objeto), algo como esto;

// Warning: potentially expensive! 
public IEnumerable<SomeItem> DescendantsAndSelf() 
{ 
    yield return this; 
    foreach (var item in Children.SelectMany(x => x.DescendantsAndSelf())) 
    { 
     yield return item; 
    } 
} 

Sin embargo, si el árbol es profunda que termina siendo muy ineficiente, ya que cada elemento tiene que "pasar por" todos los iteradores de sus ancestros. Wes Dyer tiene blogged about this, mostrando una implementación más eficiente.

De todos modos, si tienes un método como este (aunque esté implementado) puedes usar una cláusula "donde" para encontrar un elemento (o First/FirstOrDefault, etc.).

Answer 2

Si bien hay métodos de extensión que permiten la recursión en LINQ (y probablemente se parezcan a su función), ninguno se proporciona de fábrica.

Ejemplos de estos métodos de extensión se pueden encontrar here o here.

Diría que su función está bien.

Answer 3

espero que esta ayuda

public static IEnumerable<Control> GetAllChildControls(this Control parent) 
{ 
    foreach (Control child in parent.Controls) 
    { 
    yield return child; 

    if (child.HasChildren) 
    { 
     foreach (Control grandChild in child.GetAllChildControls()) 
     yield return grandChild; 
    } 
    } 
} 

Answer 4

Aquí hay uno sin recursividad. Esto evita el costo de pasar a través de varias capas de iteradores, por lo que creo que es tan eficiente como vienen.

public static IEnumerable<T> IterateTree<T>(this T root, Func<T, IEnumerable<T>> childrenF) 
    { 
     var q = new List<T>() { root }; 
     while (q.Any()) 
     { 
      var c = q[0]; 
      q.RemoveAt(0); 
      q.AddRange(childrenF(c) ?? Enumerable.Empty<T>()); 
      yield return c; 
     } 
    } 

invocación de este modo:

  var subtree = root.IterateTree(x => x. Children).ToList(); 

Answer 5

Es importante recordar que no es necesario hacer todo con LINQ, o por defecto a la recursividad. Hay opciones interesantes cuando usa estructuras de datos. La siguiente es una función de aplanamiento simple en caso de que alguien esté interesado.

public static IEnumerable<SomeItem> Flatten(IEnumerable<SomeItem> items) 
    { 
     if (items == null || items.Count() == 0) return new List<SomeItem>(); 

     var result = new List<SomeItem>(); 
     var q = new Queue<SomeItem>(collection: items); 

     while (q.Count > 0) 
     { 
      var item = q.Dequeue(); 
      result.Add(item); 

      if (item?.Children?.Count() > 0) 
       foreach (var child in item.Children) 
        q.Enqueue(child); 
     } 

     return result; 
    }