Does an iterator have a non-destructive implied contract?

Question

Let's say I'm designing a custom data structure like a stack or a queue (for example - could be some other arbitrary ordered collection that has the logical equivalent of push and pop methods - ie destructive accessor methods).

If you were implementing an iterator (in .NET, specifically IEnumerable<T>) over this collection that popped on each iteration, would that be breaking IEnumerable<T>'s implied contract?

Does IEnumerable<T> have this implied contract?

eg:

public IEnumerator<T> GetEnumerator()
{
    if (this.list.Count > 0)
        yield return this.Pop();
    else
        yield break;
}

Answer 1

I believe a destructive Enumerator violates the Principle of Least Astonishment. As a contrived example, imagine a business object library that offers generic convenience functions. I innocently write a function that updates a collection of business objects:

static void UpdateStatus<T>(IEnumerable<T> collection) where T : IBusinessObject
{
    foreach (var item in collection)
    {
        item.Status = BusinessObjectStatus.Foo;
    }
}

Another developer who knows nothing about my implementation or your implementation innocently decides to use both. It's likely they'll be surprised by the result:

//developer uses your type without thinking about the details
var collection = GetYourEnumerableType<SomeBusinessObject>();

//developer uses my function without thinking about the details
UpdateStatus<SomeBusinessObject>(collection);

Even if the developer is aware of the destructive enumeration, they may not think about the repercussions when handing the collection to a black-box function. As the author of UpdateStatus, I'm probably not going to consider destructive enumeration in my design.

However, it is only an implied contract. .NET collections, including Stack<T>, enforce an explicit contract with their InvalidOperationException - "Collection was modified after the enumerator was instantiated". You could argue that a true professional has a caveat emptor attitude toward any code that is not their own. The surprise of a destructive enumerator would be discovered with minimal testing.

Answer 2

One of the most interesting coding challenges given to me for an interview was to create a functional queue. The requirement was that each call to enqueue would create a new queue that containted the old queue and the new item at the tail. Dequeue would also return a new queue and the dequeued item as an out param.

Creating an IEnumerator from this implementation would be nondestructive. And let me tell you implementing a Functional Queue that performs well is a lot more difficult than implementing a performant Functional Stack (stack Push/Pop both work on the Tail, for a Queue Enqueue works on the tail, dequeue works on the head).

My point being...it's trivial to create a nondestructive Stack Enumerator by implementing your own Pointer mechanism (StackNode<T>) and using functional semantics in the Enumerator.

public class Stack<T> implements IEnumerator<T>
{
  private class StackNode<T>
  {
    private readonly T _data;
    private readonly StackNode<T> _next;
    public StackNode(T data, StackNode<T> next)
    {
       _data=data;
       _next=next;
    }
    public <T> Data{get {return _data;}}
    public StackNode<T> Next{get {return _Next;}}
  }

  private StackNode<T> _head;

  public void Push(T item)
  {
    _head =new StackNode<T>(item,_head);
  }

  public T Pop()
  {
    //Add in handling for a null head (i.e. fresh stack)
    var temp=_head.Data;
    _head=_head.Next;
    return temp;
  }

  ///Here's the fun part
  public IEnumerator<T> GetEnumerator()
  {
    //make a copy.
    var current=_head;
    while(current!=null)
    {
       yield return current.Data;
       current=_head.Next;
    }
  }    
}

Some things to note. A call to push or pop before the statement current=_head; completes would give you a different stack for enumeration than if there were no multithreading (you might want to use a ReaderWriterLock to safeguard against this). I made the fields in StackNode readonly but of course if T is a mutable object, you can change its values. If you were to create a Stack constructor that took a StackNode as a parameter (and set head to that passed in node). Two stacks constructed in this way will not impact each other (with the exception of a mutable T as I mentioned). You can Push and Pop all you want in one stack, the other will not change.

And that my friend is how you do non-destructive enumeration of a Stack.

Answer 3

In an attempt to keep things "simple", .NET only has one generic/non-generic pair of interfaces for things which are enumerated by calling GetEnumerator() and then using MoveNext and Current on the object received therefrom, even though there are at least four kinds of objects which should support only those methods:

1. Things which can be enumerated at least once, but not necessarily more than that.
2. Things which can be enumerated an arbitrary number of times in free-threaded contexts, but may arbitrarily yield different content each time
3. Things which can be enumerated an arbitrary number of times in free-threaded contexts, but can guarantee that if code which enumerates them repeatedly doesn't call any mutating methods, all enumerations will return the same content.
4. Things which can be enumerated an arbitrary number of times, and are guaranteed to return the same content every time as long as they exist.

Any instance which satisfies one of the higher-numbered definitions will also satisfy all the lower ones, but code which requires an object satisfying one of the higher definitions may break if given one of the lower ones.

It appears that Microsoft has decided that classes which implement IEnumerable<T> should satisfy the second definition, but are under no obligation to satisfy anything higher. Arguably, there's not much reason that something which could only meet the first definition should implement IEnumerable<T> rather than IEnumerator<T>; if foreach loops could accept IEnumerator<T>, it would make sense for things that can only be enumerated once to simply implement the latter interface. Unfortunately, types which only implement IEnumerator<T> are less convenient to use in C# and VB.NET than types which have a GetEnumerator method.

In any case, even though it would be useful if there were different enumerable types for things that could make different guarantees, and/or a standard way to ask an instance that implements IEnumerable<T> what guarantees it can make, no such types as yet exist.

Answer 4

I think this would be a violation of the Liskov substitution principle which states,

objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program.

If I had a method like the following which is called more than once in my program,

PrintCollection<T>(IEnumerable<T> collection)
{
    foreach (T item in collection)
    {
        Console.WriteLine(item);
    }
}

I should be able to swap out any IEnumerable without altering the correctness of the program, but using the destructive queue would alter the programs behavior extensively.