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

也许我所拥有的已经尽善尽美了？对于这个特定的代码，显式 foreach 内的 yield return 确实是正确的解决方案？

Answer 1

我认为你的实施很好。但是，如果您想使用 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();
} 

正如 Jon 提到的，没有使用查询编写递归方面的好方法（您可以使用 lambda 函数而不是方法来编写递归查询 - 但这也好不了多少）。

Answer 2

LINQ 通常不擅长使用标准查询运算符进行递归。您可以编写上述内容的更通用的形式，但您找不到执行此遍历的简洁标准 LINQ 方式。

Answer 3

也许我所拥有的已经尽善尽美了？

非常好。我们可以让它稍微好一点。

对于这个特定的代码，在显式 foreach 中yield return 确实是正确的解决方案？

这是一个合理的解决方案。它很容易阅读并且清晰正确。正如我之前提到的，缺点是如果树非常深，性能可能会不好。

我将这样做：

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

现在堆栈是空的，所以我们完成了，并且我们以“预序遍历”顺序获取项目。如果你不关心顺序，如果你需要的只是确保获得所有这些，那么就不必费心反转子级，你会按照 Alpha、Delta、Omega、Zeta 的顺序获得它们，伽玛，贝塔。

有道理吗？