When a colleague attempted to explain to me the benefits of internal iteration, I genuinely did not understand why he thought it was such a big deal. Now that I get it, kind of, I'm going to explain it to you.

Let's start by defining our terms, because that was a major sticking point for me.

  • External iteration: iteration of a collection is commanded from outside the iterable.

  • Internal iteration: iteration of a collection is directed by the iterable itself.

Let me give an example.

for (var index = 0; index < collection.Length; i++)
{
    Console.WriteLine(collection[index]);
}

This is the basic form of an external iterator: we have an iterable sequence called collection and this sequence is iterated using an external iterator—one more commonly referred to as a "for loop." Of course, you wouldn't normally think of a for loop as an iterator, but that's exactly what we're doing with it in this situation.

Here's the same code written using one of C#'s internal iterators:

collection.ForEach(Console.WriteLine);

"Much smaller!" you say, but that's not really the important benefit, because that just happens to be the case this time. The significant difference is that, in the first example, you write the code that decides how to advance to the next item and so forth—and by that I mean you wrote i++—but, in this example, the iterable collection makes that determination for you, and all you can do is tell it what to do on each iteration.

"Big whoop," you say. "Who cares?"

Who cares

You do. You just don't know it yet. Let's talk about why.

Here's a real (ish) iterator object in C#:

class ArrayIterator<T> : IEnumerator<T>
{
    T[] _array;
    int _index;
    
    public T Current => _array[_index];
    
    public bool MoveNext()
    {
        if ((_index + 1) < _array.Length)
        {
            _index++;
            return true;
        }
        return false;
    }
}

(Note: I've skipped constructors and additional, pointless interface implementations.)

Now, to be clear, you would never write this code. Even if you had a custom collection, odds are this would never come up. We'll get into why in a minute, but the point is that this is how you'd write an iterator if you were to do so.

What if you had a somewhat more complicated job? What if you needed to write an iterator for a tree of some kind?

"Come on, Bob, that's easy! Here, I'll show you..."

public IEnumerator<T> GetEnumerator()
{
    foreach (var item in YieldNode(_root))
        yield return item;
}

private IEnumerable<T> YieldNode(Node<T> node)
{
    if (node == null)
        yield break;

    foreach (var item in YieldNode(node.Left))
        yield return item;

    yield return node.Item;

    foreach (var item in YieldNode(node.Right))
        yield return item;
}

All right, admittedly, it was easy. I just wrote that. It compiled and worked correctly on the very first try, no big freaking deal. This, by the way, is much, much closer to what you'd actually write if you wanted to hand-code an iterator: you would let the compiler rewrite a sequence of yield returns into a generated enumerator.

But how would you write this the hard way?

...Yeah, I have no damned idea. That's the point. In C#, we don't need to worry about this because we have the ability to yield these objects from what is effectively an internal iterator to the outside. Here's what this would look like without yield:

public void ForEach(Action<T> action)
{
    ApplyToNode(_root, action);
}

private void ApplyToNode(Node<T> node, Action<T> action)
{
    if (node == null)
        return;

    ApplyToNode(node.Left, action);
    action(node.Item);
    ApplyToNode(node.Right, action);
}

The code is actually simpler, but it works pretty much the same way; it's just inside out. It is internal iteration. Obviously, there are some disadvantages. For instance, it's not possible to return early this way... Except that it kind of is. Here, check this out.

public void ForEach(Func<T, bool> f)
{
    ApplyToNode(_root, f);
}

private void ApplyToNode(Node<T> node, Func<T, bool> f)
{
    if (node == null)
        return;

    ApplyToNode(node.Left, f);

    if (!f(node.Item))
        return;

    ApplyToNode(node.Right, f);
}

See how this works? Instead of accepting a function that returns void, we take a function that returns a boolean value indicating whether or not we should continue, which mostly makes it possible to do all the things we'd usually want to do, but with an internal rather than an external iterator.

When does this matter?

Mostly when writing complex iterators, and mostly when you're not writing C#. Rust is in the process of adding something called generators that work along the same lines as C#'s coroutine-based yield enumerator thingies, but they aren't here yet. In the meantime, maybe this is something you could use in Rust when you're faced with the world's ugliest tree iteration situation?

However, internal iteration also sports potentially different performance characteristics. Calling MoveNext() et. al on an external iterator can incur function call overhead, which may be undesirable. In fact, ForEach(action) is the fastest way to iterate an instance of List<T> in C# by a decent, albeit usually unimportant, margin. I am not able to offer any greater insight regarding the performance advantages or disadvantages of internal or external iteration beyond my knowledge that there are some, and that other, more qualified persons have opined on those at length.

...In particular, I believe John Carmack had something to say on this at one point. If I can remember where, I'll add a link.

That said, I don't think performance matters here. I think what matters is the ability to express the idea that one should go through all of the things in a group of things and do something with those things. Where it is possible to yield, this becomes largely irrelevant—except in that yielding is generally slower than the alternative. Anyway, my hope is that you now understand the difference and can make the choice for yourself.

Code here:

I was going to write an external iterator for the Rust version to see how it looked, but screw that. Literally could not figure out how. I also wound up with a cyclic reference of some kind when I tried creating a generator to do it. :)