Czy iterator ma dorozumianą nieniszczącą umowę?

Powiedzmy, że projektuję niestandardową strukturę danych, taką jak stos lub kolejka (na przykład - może to być inna dowolna kolekcja uporządkowana, która ma logiczny odpowiednik pushi popmetody - tj. Niszczące metody akcesora).

Jeśli wdrażasz iterator (szczególnie w .NET IEnumerable<T>) w tej kolekcji, która pojawia się przy każdej iteracji, czy byłoby to złamanie IEnumerable<T>dorozumianej umowy?

Czy IEnumerable<T>ma to dorozumianą umowę?

na przykład:

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

Wierzę, że niszczyciel wyliczający narusza zasadę najmniejszego zdziwienia . Jako wymyślony przykład wyobraź sobie bibliotekę obiektów biznesowych, która oferuje ogólne funkcje wygody. Niewinnie piszę funkcję, która aktualizuje zbiór obiektów biznesowych:

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

Inny programista, który nic nie wie o mojej implementacji lub Twojej implementacji niewinnie, decyduje się na użycie obu. Prawdopodobnie będą zaskoczeni wynikiem:

//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);

Nawet jeśli programista jest świadomy niszczącego wyliczenia, może nie myśleć o konsekwencjach przekazania kolekcji do funkcji czarnej skrzynki. Jako autor UpdateStatusprawdopodobnie nie będę rozważał destrukcyjnego wyliczenia w moim projekcie.

Jest to jednak tylko domniemana umowa. Kolekcje .NET, w tym Stack<T>wymuszają wyraźną umowę z ich InvalidOperationException- „Kolekcja została zmodyfikowana po utworzeniu instancji modułu wyliczającego”. Można argumentować, że prawdziwy profesjonalista ma zastrzeżenie wobec jakiegokolwiek kodu, który nie jest ich własnym. Zaskoczenie niszczycielskiego modułu wyliczającego zostanie odkryte przy minimalnym testowaniu.

Jednym z najciekawszych wyzwań programistycznych, jakie otrzymałem na rozmowę, było stworzenie funkcjonalnej kolejki. Wymagano, aby każde wywołanie w kolejce tworzyło nową kolejkę, która zawierała starą kolejkę i nowy element na końcu. Dequeue zwróciłoby również nową kolejkę i odkażony element jako parametr wyjściowy.

Utworzenie IEnumeratora z tej implementacji byłoby nieniszczące. I pozwól, że powiem ci, że wdrożenie kolejki funkcjonalnej, która działa dobrze, jest o wiele trudniejsze niż wdrożenie wydajnego stosu funkcjonalnego (stosy Push / Pop działają na ogonie, ponieważ kolejka kolejki działa na ogonie, a kolejka działa na głowie).

Chodzi mi o to ... to, że stworzenie nieniszczącego modułu wyliczającego stos jest trywialne, poprzez wdrożenie własnego mechanizmu wskaźnika (StackNode <T>) i zastosowanie semantyki funkcjonalnej w module wyliczającym.

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;
    }
  }    
}

Kilka rzeczy do odnotowania. Wywołanie push lub pop przed instrukcją current = _head; uzupełnienia dałoby ci inny stos do wyliczenia niż gdyby nie było wielowątkowości (możesz użyć ReaderWriterLock, aby się przed tym zabezpieczyć). Pola w StackNode zrobiłem tylko do odczytu, ale oczywiście jeśli T jest obiektem zmiennym, możesz zmienić jego wartości. Jeśli miałbyś stworzyć konstruktor Stack, który wziął StackNode jako parametr (i ustaw head na ten przekazany w węźle). Dwa skonstruowane w ten sposób stosy nie będą na siebie oddziaływać (z wyjątkiem zmiennego T, jak wspomniałem). Możesz pchać i strzelać ile chcesz na jednym stosie, drugi się nie zmieni.

I że mój przyjaciel jest tym, jak robisz nieniszczące wyliczanie stosu.

Starając się, aby rzeczy były „proste”, .NET ma tylko jedną ogólną / nie-ogólną parę interfejsów dla rzeczy, które są wyliczane przez wywołanie, GetEnumerator()a następnie użycie MoveNexti Currentna otrzymanym z nich obiekcie, mimo że istnieją co najmniej cztery rodzaje obiektów które powinny obsługiwać tylko te metody:

1. Rzeczy, które można wymienić przynajmniej raz, ale niekoniecznie więcej.
2. Rzeczy, które można wyliczyć dowolną liczbę razy w kontekstach o swobodnym wątku, ale mogą dowolnie dawać różne treści za każdym razem
3. Rzeczy, które można wyliczyć dowolną liczbę razy w kontekstach o swobodnym wątku, ale mogą zagwarantować, że jeśli kod, który je wylicza wielokrotnie, nie wywoła żadnych metod mutacji, wszystkie wyliczenia zwrócą tę samą treść.
4. Rzeczy, które można wyliczyć dowolną liczbę razy, i gwarantują, że zwrócą tę samą treść za każdym razem, o ile istnieją.

Każde wystąpienie, które spełnia jedną z definicji o wyższym numerze, spełni również wszystkie niższe, ale kod, który wymaga obiektu spełniającego jedną z wyższych definicji, może ulec awarii, jeśli zostanie podany jeden z niższych.

Wydaje się, że Microsoft zdecydował, że klasy, które implementują, IEnumerable<T>powinny spełniać drugą definicję, ale nie są zobowiązane do spełnienia niczego wyższego. Prawdopodobnie nie ma zbyt wielu powodów, aby coś, co mogłoby spełnić tylko pierwszą definicję, powinno IEnumerable<T>raczej zostać wprowadzone IEnumerator<T>; jeśli foreachpętle mogłyby zaakceptować IEnumerator<T>, sensownym byłoby, aby rzeczy, które można wymienić tylko raz, wystarczy zaimplementować ten ostatni interfejs. Niestety typy, które tylko implementują, IEnumerator<T>są mniej wygodne w użyciu w C # i VB.NET niż typy, które mają GetEnumeratormetodę.

W każdym razie, chociaż byłoby użyteczne, gdyby istniały różne wyliczalne typy rzeczy, które mogłyby dawać różne gwarancje i / lub standardowy sposób, aby zapytać instancję, która implementuje IEnumerable<T>jakie gwarancje może uczynić, żadne takie typy jeszcze nie istnieją.

Myślę, że byłoby to naruszeniem zasady substytucji Liskowa, która stwierdza:

obiekty w programie powinny być zastępowalne instancjami ich podtypów bez zmiany poprawności tego programu.

Gdybym miał metodę podobną do następującej, która jest wywoływana w moim programie więcej niż jeden raz,

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

Powinienem być w stanie zamienić dowolną IEnumerable bez zmiany poprawności programu, ale użycie destrukcyjnej kolejki znacznie zmieniłoby zachowanie programów.