Bellow is my answer but also note that John Skeet spoke about it today on his blog an about the fact that he is not totally ok with the MSDN meaning of "Lazy" as MSDN isn't really clear of what lazy exactly mean when they use it in Just how lazy are you ? his post make for an interesting read.
Additionally Wikipedia assume that three rules should be maintained for lazy evaluation and third point isn't respected in MSDN meaning as the expression will be evaluated more than once if GetEnumerator is called again (By the spec Reset is not implemented on enumerator objects generated using the "yield" keyword and most of linq use it currently)
Considering a function
int Computation(int index)
Immediate execution :
IEnumerable<int> GetComputation(int maxIndex)
{
var result = new List<int>(maxIndex);
for(int i = 0; i <= maxIndex; i++)
{
result[i] = Computation(i);
}
return result;
}
- When the function is called Computation is executed maxIndex+1 times
- GetEnumerator return a new instance of the enumerator doing nothing more.
- Each call to GetNext return directly the value stored in the next Array cell that List uses internally.
Deferred but eager execution :
IEnumerable<int> GetComputation(int maxIndex)
{
var result = new List<int>(maxIndex);
for(int i = 0; i <= maxIndex; i++)
{
result[i] = Computation(i);
}
foreach(var value in result)
{
yield return value;
}
}
- When the function is called an instance of an auto generated class (called "enumerable object" in the spec) implementing IEnumerable is created and a copy of the argument (maxIndex) is stored in it.
- GetEnumerator return a new instance of the enumerator doing nothing more.
- The first call to GetNext execute maxIndex+1 times the compute method, store the result in a list and return the first value
- Each subsequent call to GetNext return a value stored in the internal Array instance of the List
Deferred and lazy execution :
IEnumerable<int> GetComputation(int maxIndex)
{
for(int i = 0; i <= maxIndex; i++)
{
yield return Computation(i);
}
}
- When the function is called the same thing as the lazy execution case happens.
- GetEnumerator return a new instance of the enumerator doing nothing more.
- Each call to GetNext execute once the Compute code and let the caller immediately act on the result.
Most of linq use deferred and lazy execution but some functions can't be so like sorting.
To summarize:
- Immediate mean that the computation/execution is done in the function and finished once the function return. (Fully eager evaluation as most C# code does)
- Deferred/Eager mean that most of the work will be done on the first MoveNext() or when the IEnumerator instance is created (For IEnumerable it is when GetEnumerator is called)
- Deferred/Lazy mean that the work will be done each time GetNext() is called but nothing before.
Parallel LINQ does it a little differently as the computation could be considered deferred/Lazy from the point of view of the caller but internally the computation of some number of elements begin in parallel as soon as the enumeration begin.