блок итератора в LINQ

Question

Мне трудно найти правильный синтаксис LINQ для использования в следующем блоке итератора:

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

Может быть, то, что у меня есть, так же хорошо, как и получается?Для этого конкретного кода yield return внутри явного foreach действительно правильное решение?

Answer 1

Может быть, то, что я имею, так же хорошо, как и получается?

Это довольно хорошо. Мы можем сделать это немного лучше.

Для этого конкретного кода возвращение доходности внутри явного foreach действительно является правильным решением?

Это разумное решение. Это легко читать и четко исправить. Недостатком является, как я уже говорил ранее, производительность потенциально не очень хорошая, если дерево очень глубокое.

Вот как бы я это сделал:

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

Обратите внимание, что вызов метода Reverse () необходим, только если вы заботитесь о том, чтобы итерация прошла «по порядку». Например, предположим, что у операции Alpha есть дочерние операции Beta, Gamma и Delta, а у Delta есть дети Zeta и Omega. Обход идет так:

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

и теперь стек пуст, так что мы закончили, и мы получаем элементы в порядке «предварительного заказа». Если вас не волнует порядок, если все, что вам нужно, это убедиться, что вы получите их все, не стесняйтесь поменять местами детей, и вы получите их в порядке Альфа, Дельта, Омега, Зета , Гамма, бета.

Имеет смысл?

Answer 2

LINQ не очень хорош в рекурсии, используя стандартные операторы запросов.Вы могли бы написать более общую форму вышеупомянутого, но вы не найдете аккуратный стандартный способ LINQ для выполнения этого обхода.

Answer 3

Я думаю, что ваша реализация хороша.Однако, если вы хотите использовать LINQ (и сделать его немного - но не значительно - короче), тогда вы можете реализовать GetItems, используя запрос, который повторяет все операции и возвращает текущий элемент, за которым следуют все другие рекурсивно сгенерированные элементы:

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

Для каждой операции мы генерируем последовательность, содержащую элемент для текущего, за которым следуют все рекурсивно сгенерированные элементы.Используя вложенное предложение from, вы можете перебирать эту коллекцию, чтобы получить «плоскую» структуру.

Я думаю, что вы могли бы сделать его немного лучше, используя функциональный (неизменяемый) список, который поддерживает операцию «добавления элемента вперед» - это именно то, что мы делаем во вложенном from,Используя FuncList из моей книги по функциональному программированию (это уже не ленивая последовательность):

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

Как упоминал Джон, нет хорошего способа написания рекурсивного аспекта с использованием запроса(вы можете написать рекурсивный запрос, используя лямбда-функции вместо методов - но это не намного лучше).