IEnumerable is Lazy… And That’s Cool
January 14, 2011 6 Comments
We tend to think of IEnumerable<T> as this thing in C# collections which allows foreach to iterate a collection without having to deal with a counter. There’s another semantic feature of IEnumerable that is different from an Array or List<T> or any other concrete collection. IEnumerable is lazy while an array or list is implicitly eager.
Consider an array. First, you have to define its size which is fixed. Then you have to loop over the array and populate it with values. Then you can use it in some other loop later. Array is conducive to eager evaluation because you have to define its size in advance and you have to fill it up before you can use it. Lists are similar conceptually and are actually implemented with arrays internally. The main advantage of a list is that it is dynamically expandable.
IEnumerable is a very different thing. At its core IEnumerable is a contract to provide a factory for an IEnumerator<T> object. IEnumerator then just provides a mechanism to get the current element of the enumeration, move to the next element and reset. IEnumerator only has to know how to get the next element or start over. It doesn’t actually need a collection to exist. MoveNext() only has to get the next value. There’s no requirement that all values are known at any give time and there’s no requirement that the values are finite. This is the essence of lazy evaluation. Only enough work needs to be done to get the next answer. Nothing more.
Fibonacci: An infinite IEnumberable<T>
To illustrate that IEnumerable is a lazy evaluation pattern, I implemented the Fibonacci Sequence as an enumerable type in C#. I can pass a FibonacciSequence object to things that understand IEnumerable and it works. If IEnumerable were an eager implementation my code would spin in an infinite loop but it doesn’t because MoveNext() only calculates the next number in the series if it is asked.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace LazyFibonacci
{
class Program
{
static void Main( string[] args )
{
int i = -1;
if( args.Length > 0 )
{ int.TryParse( args[0], out i ); }
else
{ i = 100; }
var fibonacci = new FibonacciSequence();
/***
* fibonacci is infinite.
* Don't try operations that require the entire set to be enumerated:
* - fibinacci.ToList() --> NO!
* - fibonacci.Reverse() --> NO!
*
* Using .Skip(int) and .Take(int) is a good way to get slices of fibonacci, though.
***/
foreach( var item in fibonacci.Take( i ) )
{
Console.WriteLine( item );
}
}
}
//FibonnacciSequence has no state.
//It's just a factory for FibonacciEnumerator.
public class FibonacciSequence : IEnumerable<BigInteger>
{
public IEnumerator<BigInteger> GetEnumerator()
{
return new FibonacciEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
public class FibonacciEnumerator : IEnumerator<BigInteger>
{
public FibonacciEnumerator()
{
Reset();
}
BigInteger Last { get; set; }
public BigInteger Current { get; private set; }
object IEnumerator.Current { get { return Current; } }
public void Dispose() { /*do nothing*/}
public void Reset()
{
Current = -1;
}
public bool MoveNext()
{
if( Current == -1 )
{
//State after first call to MoveNext() before the first element is read
//Fibonacci is defined to start with 0.
Current = 0;
}
else if( Current == 0 )
{
//2nd element in the Fibonacci series is defined to be 1.
Current = 1;
}
else
{
//Fibonacci infinite series algorithm.
BigInteger next = Current + Last;
Last = Current;
Current = next;
}
//infinite series. there is always another.
return true;
}
}
}
The moment of truth. If IEnumerable is lazy this will work.
PS> csc -nologo -r:System.Numerics.dll -out:fibonacci.exe ./program.cs
PS> $fib = (./fibonacci.exe 25); [string]::join(', ', $fib)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368
Brian Reiter's Thoughtful Code 
This is cool, but it’s much easier to do using “yield return”:
static IEnumerable LazyFib()
{
int a = 1;
yield return a;
int b = 1;
yield return b;
for (;;)
{
int c = a + b;
yield return c;
a = b;
b = c;
}
}
Both are excellent, but Brian’s example illustrates the usage of yield more concisely. Love it Brian.
Pingback: IEnumerable VS. IList with LINQ – dtbiedrzycki.com
Pingback: Searching Collections with Linq – sparkyandsusi
Excellent post! I’ve liked to it from my own blog: https://sparkyandsusi.wordpress.com/2016/12/10/searching-collections-with-linq/
Pingback: [C#] Iteration – 5. Lazy Evaluation – 칸칸치호 스터디 자료저장소