Infinite series in .NET

Functional languages such as Haskell have a very cool concept of lazy expansion. Basically, Haskell will put off doing work until it knows that the result will absolutely, definitely be required. I admire Haskell for this, as it is the way I tend to work as well (although I suspect you don’t have to feed Haskell beer and pizza, and then wait until a marathon midnight coding session has been done).

This is very useful, as it allows you to easily do operations on infinite series in Haskell. For example, to get the first 20 even numbers, you’d do something like:

take 20 [2,4..]

Haskell is then smart enough to know that you want to take 20 results from the list of even numbers, with no limits on the length of the list. What’s cool is that it will not create the list items until they are requested, so you don’t need infinite amounts of storage for that list (I don’t think I have enough DIMM slots for infinite RAM…)

So how would you do something similar in .NET? Well, .NET provides the yield keyword. This is used to create and return the items in a list dynamically so, rather than creating a list then iterating through it, you create the current item only as and when it’s required.

Let’s look at the equivalent C# code (note that it’s a lot longer than Haskell!!)

        public static IEnumerable EvenIntegers(int count)
        {
            int result = 0;
            while (count > 0)
            {
                result += 2;
                count--;
                yield return result;
            }
        }

        static void Main(string[] args)
        {
            foreach (int i in EvenIntegers(20))
            {
                Console.WriteLine(i);
            }
        }

Note that I am never storing the full list of integers – I only ever have one in memory at a time. Obviously, with a list of 20 integers, this makes little difference, but if you want to print out all the integers to Int64.MaxValue, this could make a *huge* difference. Also, if you don’t know how many items you are using, it’s going to be a lot quicker, as you will only create the list items you are definitely using, not the ones you could possibly be using.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s