F# yield! operator - Implementation and possible C# equivalents

Question

I'm currently learning F# and I really love the yield! (yield-bang) operator. Not only for its name but also for what it does of course.

The yield! operator basically allows you to yield all elements of a sequence from a sequence expression. This is useful for composing enumerators. Since I regularly encounter big, complicated enumerators I am interested in strategies we can use to break them up and compose them from simpler enumerators.

Unfortunatetely, the yield! operator is not available in C#. As far as I understand, what it does is like a foreach (var x in source) yield x; but the book I'm reading (Petricek's Real World F# - Manning) suggests that it has better performance...

• So what exactly does the F# compiler do here? (Yes, I can look at it using Reflector too but I'd like to have a more detailed description of the mechanism).

In order to achieve a similar construct in C# I have explored multiple ways, but none of them is as concise as the yield! operator and I'm also not sure about the complexity of them. Could someone please provide input if my BigO numbers are correct?

• Decompose enumerator into multiple private enumerators and then yield each element from the public enumerator:

  foreach (var x in part1()) yield x
  foreach (var x in part2()) yield x
  

  This will effectively result in a "double yield" on each element. Is that O(2n) then? (or possibly worse?) Anyway, using this approach stops me from using yield break; from any of my subparts.

• Decompose enumerator into multiple private enumerators and then concat all private enumerators from the public enumerator:

  return part1().Concat(part2())
  

  I believe this is no different from the aforementioned solution because Concat() is implemented the way I outlined above.

Any other options?

Answer 1

In the current version of C#, I don't think you have other options than foreach... yield return and Concat. I agree it would be nice to have the yield! operator in C#, it would make certain constructs much more elegant, but I doubt this feature will ever make it to the "must-have" list, since we can easily do without it.

You might be interested in this MS research paper, which introduces a new yield foreach construct :

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

Regarding your question about complexity: in both cases it's O(n). O(2n) is not used, because it denotes the same complexity as O(n) (linear). I don't think you can do better than that with the current C# features...

Answer 2

There is no direct counterpart to yield! in C#. You're currently stuck with a combination of foreach and yield return.

However, IIRC, LINQ offers something similar, namely the SelectMany query operator, which translates to C# as multiple from .. in .. clauses.

(I'm hoping I'm not mixing up two different concepts, but IIRC, both yield! and SelectMany are essentially "flattening" projections; ie. a hierarchy of objects is "flattened" into a list.)

Answer 3

Regarding how the compiler translates the yield! operation, the paper cited by Thomas Levesque in his answer illustrates one implementation technique in section 4.3 (in particular, their example spanning figures 7-9 is illustrative of the general strategy). I don't think that there's any good way to do this from within an iterator block in C# - as I understand your proposed solutions, they could both result in quadratic behavior when used recursively. You could always manually create a NestedEnumerable<T> subclass to achieve the performance benefits, but this will be quite ugly compared to using a normal iterator block.