I want to write a blog article on the inner-workings of iterators. If you’re writing C# code, chances are you’ve consumed an iterator with the foreach keyword. However, if you’re not familiar with writing iterators, here’s an introduction on writing them.
The first example is of a simple counter iterator. Here’s the code in its entirety:
This produces fairly predictable results:
1 2 3 4 5 6 7 8 9 10
Press any key to continue…
If you’re new to this, all you really need to notice is the yield return statement. You can think of this as a normal return keyword, except it leaves the function “hanging”. Next time the function is used, it will resume from this point – counter will be incremented and the while loop continues. Under the hood, it’s not exactly like that – but it’s a useful approximation of what is going on. You will notice that the return type for the function is actually IEnumerable<int>, however, you need to return the primitive type specified within the angled brackets <> when using the yield return keyword.
One of the classic computer-science problems to solve is reporting prime-numbers. Here’s a version that uses an iterator to report all primes up to a number specified:
Which produces the output:
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Press any key to continue…
The mathematicians may want to argue over whether or not 1 and 2 are actual prime numbers, but doing so misses the point of this post! Looking at the IsPrime function, you’ll notice a for loop and think: “Hey! Our counter iteration from earlier would do the same thing!” . So in the next version, that’s exactly what I’ve done!
I have one final “optimisation” to make. I use the term loosely, because I have done no performance testing to vouch that it makes the program any more optimal… It’s really done to show that you can combine recursion and iterators. To test for a prime number, you need to see if a number has any divisors other than 1 and itself. Furthermore, if you can’t divide a number (y)evenly by a different number (x), then any multiple of x will also not be a divisor of y. Therefore, when testing for prime numbers, there’s no point testing divisors unless they are prime numbers themselves.
Have a look at our IsPrime function again. Rather than using the counter iterator to go through every possible denominator, we can use our prime iterator to only go through denominators that are prime numbers! We do have to tweak it a little, as “1” becomes a special case… (Can anyone say “endless loop”?) Here’s the final version:
The point is, iterators are really cool. (Well, in a nerdy sense at least) If you’re not using them in your C# coding, then you should be! I guess it depends on how often you write code that conforms to an iterator type construct, but there’s a lot of scope there, so get thinkin’! I don’t think C# iterators can quite match the power of python’s generators, but I’m not a python coder… Python allows you to append results to the set of results the generator “yields”. There’s a good demonstration of prime number producers written in python on Wikipedia demonstrating this concept.