C# Yield Keyword, IEnumerable<T>, and Infinite Enumerations

Visual Studio 2005 came with a slew of .net and .net compiler features. One of those features that I particularly enjoy is the yield keyword. It was Microsoft's way of building IEnumerable (or IEnumerator) classes and generic classes around your iterator code block. I'm not going to discuss the yield keyword much in this post because the feature has been around a long time now and the internet is replete with discussions on the topic.

Despite the long life of the yield keyword, I still find it conspicuous when I see it in projects I work on. I suppose it's just rare that I find myself writing my own enumerable. As a result, when I see yield return, it tends to stand out. I started looking around to see how the rest of the programming world uses the yield keyword wondering if I was under-utilizing the flexibility provided.

Specifically, I wondered if I was missing out on the lazy nature of the iterator and the numerous linq extension methods optimized to take advantage of that aspect of iterators. What I mean by that is that an iterator doesn't need to store each sequential value in memory the way a collection would and thus you can use each value without necessarily increasing the memory overhead. Further, you can take advantage of calculations which tend to already be sequential in nature (like the Fibbonacci sequence for example).

The second thing I thought about was an infinite (well, sort of infinite) enumerable. I'm not sure if I feel like it's a bad idea or not so I wrote these examples to be unending? I may eventually find a use for such an iterator and then get burned when someone tries to call Fibbonacci.Min() and the application throws an overflow exception, but I suppose at that point I'll make it a method and take a sanity check variable.

In the meantime, here are a few examples of some iterators I thought were interesting and fun challenges:

static IEnumerable<ulong> Fibbonacci
{
    get
    {
        yield return 0;
        yield return 1;

        ulong previous = 0, current = 1;
        while (true)
        {
            ulong swap = checked(previous + current);
            previous = current;
            current = swap;
            yield return current;
        }
    }
}

static IEnumerable<long> EnumerateGeometricSeries(long @base)
{
    yield return 1;

    long accumulator = 1;
    while (true)
        yield return accumulator = checked(accumulator * @base);
}

static IEnumerable<ulong> PrimeNumbers
{
    get
    {
        var prime = 0UL;
        while (true)
            yield return prime = prime.GetNextPrime();
    }
}

static IEnumerable<List<uint>> PascalsTriangle
{
    get
    {
        var row = new List<uint> { 1 };
        yield return row;

        while (true)
        {
            var last = row[0];
            for (var i = 1; i < row.Count; i++)
            {
                var current = row[i];
                row[i] = current + last;
                last = current;
            }

            row.Add(1);
            yield return row;
        }
    }
}

Some of these methods use a few extension methods I adapted from places in the .net framework:

public static ulong GetNextPrime(this ulong from)
{
    for (var j = from + 1 | 1UL; j < ulong.MaxValue; j += 2)
        if (j.IsPrime())
            return j;

    return from;
}

public static bool IsPrime(this ulong value)
{
    if ((value & 1) != 0)
    {
        var squareRoot = (ulong)Math.Sqrt((double)value);
        for (ulong i = 3; i <= squareRoot; i += 2)
            if (value % i == 0)
                return false;

        return true;
    }
    return value == 2;
}

To keep the test console app clean, of course, I used my favorite IEnumerable.Each() extension method:

public static void Each<T>(this IEnumerable<T> enumerable, Action<T> action)
{
    foreach (var element in enumerable)
        action(element);
}

Here's the sample code:

static void Main()
{
    Fibbonacci.Skip(10).Take(10).Each(Console.WriteLine);
    Console.WriteLine();

    EnumerateGeometricSeries(2).Take(10).Each(Console.WriteLine);
    Console.WriteLine();

    PrimeNumbers.Where(p => p > 600).Take(10).Each(Console.WriteLine);
    Console.WriteLine();

    foreach (var row in PascalsTriangle.Take(10))
    {
        row.Each(element => Console.Write("{0} ", element)); 
        Console.WriteLine();
    }

    Console.ReadLine();
}

// The second set of 10 elements in the Fibbonacci sequence
// 55 89 144 233 377 610 987 1597 2584 4181

// Base of 2 to the first 10 powers
// 1 2 4 8 16 32 64 128 256 512

// The first 10 prime numbers greater than 600
// 601 607 613 617 619 631 641 643 647 653

// The first 10 rows of Pascal's Triangle
// 1
// 1 1
// 1 2 1
// 1 3 3 1
// 1 4 6 4 1
// 1 5 10 10 5 1
// 1 6 15 20 15 6 1
// 1 7 21 35 35 21 7 1
// 1 8 28 56 70 56 28 8 1
// 1 9 36 84 126 126 84 36 9 1