List processing using Yield and Delegates

• Download source files - 0.842 Kb
• Old source files (For people curious about how much more messy the original article code was) - 1.01 Kb

Introduction

This article will describe how we can use iterators to process IEnumerable lists. This method is not used very often in imperative programming languages like C#, Java so it is interesting to see how it works. Since this code uses yield (iterators) as well as anonymous delegates, it will only run with C# 2.0.

A simple yield method (iterator)

class PositiveNumbers : System.Collections.IEnumerable
{
  public System.Collections.IEnumerator GetEnumerator()
  {
    int a = 1;
    while (true)
    {
      yield return a;
      a = a + 1;
    }
  }
}
...
foreach (int num in new PositiveNumbers())
{
  .. Do something with each positive number ..
}

Instead of writing a class implementing the three IEnumerator methods, we can now in C# 2.0 write a single method using the yield terminology. This method can be accessed from outside using the IEnumerator methods, MoveNext, Reset, Current. (Note: yield does not support Reset).

So how does it work? The answer is quite simple actually. The first time the MoveNext method is called, our method runs from the beginning. The variable a is set to 1, we enter the while loop and it returns a which equals 1. The next time MoveNext is called, we continue with the statement after the yield statement, a=a+1. This increases a to 2, we loop and again run the yield return statement. This time however a is increased to two. The following code demonstrates this more clearly:

public System.Collections.IEnumerator GetEnumerator()
{
  yield return "First element";
  yield return "Second element";
  yield return "Third element";
  yield return "Last element";
}

This yield method (iterator) represents a list that always contains four string elements.

Some syntactic sugar

A problem with the above approach is that we need one class for each iterator. Fortunately C# 2.0 provides a solution for this. If the yield statement is put into a method which is declared to return an IEnumerable, the compiler will do everything for you:

class Iterators
{
  public static System.Collections.IEnumerable PositiveNumbers()
  {
    int a = 1;
    while (true)
    {
      yield return a;
      a = a + 1;
    }
  }
}

Not only does this mean that we can put several iterators in the same class, but also access each iterator by their class and method name instead of using the new statement:

foreach (int num in IteratorsPositiveNumbers()){}

Finally, since our iterator only returns integers, we can optimize it by using the generic version of IEnumerable. It is a simple change in the method header that could both increase the execution speed as well as reduce the amount of casts needed.

public static System.Collections.Generic.IEnumerable<INT> PositiveNumbers()

Cutting the infinite list short

The PositiveNumbers enumerator above runs forever. If we only want some of the PositiveNumbers, what should we do? The answer is to create another iterator. This iterator will have three arguments:

• The index of the first element we want.
• The index of the last element we want.
• An IEnumerable instance containing the source list.

public static System.Collections.IEnumerable SubList(int start, 
                               int end, IEnumerable enumerable)
{
  int count = 0;
  foreach (object o in enumerable)
  {
    count++;
    if (count < start)
      continue;
    else if (count <= end)
      yield return o;
    else
      yield break;
  }
}
...
//This gives us a list containing number 5 through 15
IEnumerable numbers =
  Iterators.SubList(5, 15, Iterators.PositiveNumbers()))

Our iterator simply skips elements in the list we take in the argument until we reach the 5^th element. We then yield return until we get to the 16^th element. There we call yield break. Calling yield break is the same as saying that our collection doesn't contain any more elements and it terminates the method.

Mapping

The final iterator that we will study in this article is named from a function originally found in the LISP language. What Map will do is to take a method and a list. It will return a list where the method has been applied on each element in that list:

 public delegate object MapFunction(object o);

  /// <summary>
  /// Runs the function on each element in the enumerable list
  /// </summary>
  public static IEnumerable Map(MapFunction mapFunction, 
                                 IEnumerable enumerable)
  {
    foreach (object o in enumerable)
    {
      yield return mapFunction(o);
    }
  }
...
foreach (int num in
        I.Map(
        /* Multiply each element by 2 */
        delegate(object o){  return ((int)o) * 2; },
        I.SubList(5, 15, I.PositiveNumbers())))
    {
      Console.Write("{0} ", num); //Print number 10 12 14 .. 28 30
    }

The code was pretty simple to write. We simply apply the MapFunction to each object and then yield return the result.

Some final thoughts

While most of what has been written in this article can be implemented in other ways, it is still interesting to see how it works when approaching it from the side of functional programming. It is especially interesting to notice how we can work on a list containing all positive numbers while only generating elements on demand, making it possible to use infinite lists.

Credits

Many thanks to Kris Vandermotten for pointing to me the fact that IEnumerable functions may contain yield. This, while forcing me to rewrite most of the article, increased its readability significantly and reduced the amount of code needed.

History

• 2005-04-29: Posted the original article.
• 2005-04-29: Reduced a few lines of code and fixed a minor error.
• 2005-05-04: Big change due to new knowledge about yield and its syntactic sugar.