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;
}
}
...
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 5th element. We then yield return
until we get to the 16th 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);
public static IEnumerable Map(MapFunction mapFunction,
IEnumerable enumerable)
{
foreach (object o in enumerable)
{
yield return mapFunction(o);
}
}
...
foreach (int num in
I.Map(
delegate(object o){ return ((int)o) * 2; },
I.SubList(5, 15, I.PositiveNumbers())))
{
Console.Write("{0} ", num);
}
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.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.