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.