F# 产量！运算符 - 实现和可能的 C# 等效项

Question

我目前正在学习 F#，我真的很喜欢 yield! (yield-bang) 运算符。不仅是因为它的名字，当然也因为它的作用。

yield! 运算符基本上允许您从序列表达式中生成序列的所有元素。这对于编写枚举器很有用。由于我经常遇到大型、复杂的枚举器，因此我对可以用来分解它们并由更简单的枚举器组合它们的策略感兴趣。

不幸的是，yield! 运算符在 C# 中不可用。据我了解，它的作用类似于 foreach (var x in source) Yield x; 但我正在读的书 (Petricek 的真实世界 F# - Manning) 表明它具有更好的性能...

• 那么 F# 编译器在这里到底做了什么？ （是的，我也可以使用 Reflector 查看它，但我想更详细地描述该机制）。

为了在 C# 中实现类似的构造，我探索了多种方法，但没有一种方法像 yield! 运算符那样简洁，而且我也不确定它们的复杂性。如果我的 BigO 号码正确，有人可以提供意见吗？

• 将枚举数分解为多个私有枚举数，然后从公共枚举数中生成每个元素：

  foreach（第 1 部分（）中的 var x）yield x
  foreach (part2() 中的 var x) 产生 x
  

  这将有效地导致每个元素的“双倍收益”。那是 O(2n) 吗？ （或者可能更糟？）无论如何，使用这种方法会阻止我从任何子部分使用 yield break;。

• 将枚举数分解为多个私有枚举数，然后将公共枚举数中的所有私有枚举数连接起来：

  返回part1().Concat(part2())
  

  我相信这与上述解决方案没有什么不同，因为 Concat() 是按照我上面概述的方式实现的。

还有其他选择吗？

Answer 1

在当前版本的 C# 中，我认为除了 foreach...yield return 和 Concat 之外，您没有其他选择。我同意在 C# 中使用 yield! 运算符会很好，它会使某些构造更加优雅，但我怀疑此功能是否会进入“必备”列表，因为没有它我们也能轻松做到。

您可能对这篇MS 研究论文感兴趣，其中介绍了新的 yield foreach 构造：

IEnumerable<XmlNode> Traverse(XmlNode n)
{
    yield return n;
    foreach (XmlNode c in n.ChildNodes)
        yield foreach Traverse(c);
}

关于您关于复杂性的问题：在这两种情况下都是O(n)。未使用 O(2n)，因为它表示与 O(n) （线性）相同的复杂度。我不认为使用当前的 C# 功能可以做得更好......

Answer 2

关于编译器如何转换 yield! 操作， Thomas Levesque 在其回答中引用的论文在第 4.3 节中说明了一种实现技术（特别是，他们跨越图 7-9 的示例说明了总体策略）。我认为没有任何好的方法可以从 C# 中的迭代器块中执行此操作 - 据我了解您提出的解决方案，它们在递归使用时都可能导致二次行为。您始终可以手动创建一个 NestedEnumerable 子类来实现性能优势，但这与使用普通迭代器块相比会非常难看。

Answer 3

C# 中没有与 yield! 直接对应的东西。您目前陷入了 foreach 和 yield return 的组合。

然而，IIRC、LINQ 提供了类似的功能，即 SelectMany 查询运算符，它在 C# 中转换为多个 from .. in .. 子句。

（我希望我没有混淆两个不同的概念，但是 IIRC，yield! 和 SelectMany 本质上都是“扁平化”投影；即对象的层次结构被“扁平化”到一个列表中。）