Hat ein Iterator einen zerstörungsfreien impliziten Vertrag?

11

Angenommen, ich entwerfe eine benutzerdefinierte Datenstruktur wie einen Stapel oder eine Warteschlange (z. B. könnte dies eine andere willkürlich geordnete Sammlung sein, die das logische Äquivalent von pushund popMethoden aufweist - dh destruktive Zugriffsmethoden).

Wenn Sie einen Iterator (speziell in .NET IEnumerable<T>) über diese Sammlung implementieren würden, der bei jeder Iteration auftauchte, würde dies IEnumerable<T>den impliziten Vertrag brechen ?

Hat IEnumerable<T>dieser implizite Vertrag?

z.B:

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

Antworten:

12

Ich glaube, ein destruktiver Enumerator verstößt gegen das Prinzip des geringsten Erstaunens . Stellen Sie sich als erfundenes Beispiel eine Geschäftsobjektbibliothek vor, die allgemeine Komfortfunktionen bietet. Ich schreibe unschuldig eine Funktion, die eine Sammlung von Geschäftsobjekten aktualisiert:

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

Ein anderer Entwickler, der nichts über meine Implementierung oder Ihre Implementierung weiß, entscheidet sich unschuldig für beide. Es ist wahrscheinlich, dass sie vom Ergebnis überrascht sein werden:

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

Selbst wenn dem Entwickler die destruktive Aufzählung bekannt ist, kann es sein, dass er bei der Übergabe der Sammlung an eine Black-Box-Funktion nicht an die Auswirkungen denkt. Als Autor von UpdateStatuswerde ich in meinem Entwurf wahrscheinlich keine destruktive Aufzählung berücksichtigen.

Es handelt sich jedoch nur um einen impliziten Vertrag. .NET-Sammlungen, einschließlich Stack<T>, erzwingen einen expliziten Vertrag mit ihrer InvalidOperationException- "Sammlung wurde geändert, nachdem der Enumerator instanziiert wurde". Sie könnten argumentieren, dass ein echter Profi eine Vorbehaltshaltung gegenüber jedem Code hat, der nicht sein eigener ist. Die Überraschung eines zerstörerischen Enumerators würde mit minimalen Tests entdeckt werden.

Corbin März
quelle
1
+1 - für 'Prinzip des geringsten Erstaunens' werde ich das bei Leuten zitieren.
+1 Dies ist im Grunde auch das, was ich dachte. Destruktiv zu sein könnte das erwartete Verhalten der LINQ IEnumerable-Erweiterungen beeinträchtigen. Es fühlt sich einfach seltsam an, diese Art der geordneten Sammlung zu durchlaufen, ohne die normalen / destruktiven Operationen auszuführen.
Steven Evers
1

Eine der interessantesten Codierungsherausforderungen, die mir für ein Interview gestellt wurden, war die Erstellung einer funktionalen Warteschlange. Die Anforderung bestand darin, dass bei jedem Aufruf der Warteschlange eine neue Warteschlange erstellt wurde, die die alte Warteschlange und das neue Element am Ende enthielt. Dequeue würde auch eine neue Warteschlange und das in die Warteschlange gestellte Element als Out-Parameter zurückgeben.

Das Erstellen eines IEnumerators aus dieser Implementierung wäre zerstörungsfrei. Und lassen Sie mich Ihnen sagen, dass das Implementieren einer funktionalen Warteschlange, die eine gute Leistung erbringt, viel schwieriger ist als das Implementieren eines performanten funktionalen Stapels (Stack Push / Pop funktioniert beide am Tail, bei einer Queue Enqueue am Tail, Dequeue am Kopf).

Mein Punkt ist ... es ist trivial, einen zerstörungsfreien Stapel-Enumerator zu erstellen, indem Sie Ihren eigenen Zeigermechanismus (StackNode <T>) implementieren und die funktionale Semantik im Enumerator verwenden.

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

Einige Dinge zu beachten. Ein Aufruf zum Drücken oder Popen vor der Anweisung current = _head; Durch Vervollständigungen erhalten Sie einen anderen Stapel für die Aufzählung als ohne Multithreading (möglicherweise möchten Sie ein ReaderWriterLock verwenden, um sich dagegen zu schützen). Ich habe die Felder in StackNode schreibgeschützt gemacht, aber wenn T ein veränderliches Objekt ist, können Sie natürlich seine Werte ändern. Wenn Sie einen Stapelkonstruktor erstellen, der einen StackNode als Parameter verwendet (und den Kopf auf den im Knoten übergebenen Wert setzt). Zwei auf diese Weise konstruierte Stapel wirken sich nicht gegenseitig aus (mit Ausnahme eines veränderlichen T, wie ich bereits erwähnt habe). Sie können alles, was Sie wollen, in einen Stapel schieben und einfügen, der andere ändert sich nicht.

Und mein Freund ist, wie Sie eine zerstörungsfreie Aufzählung eines Stapels durchführen.

Michael Brown
quelle
+1: Meine zerstörungsfreien Stack- und Queue-Enumeratoren sind ähnlich implementiert. Ich habe mehr nach dem Vorbild von PQs / Heaps mit benutzerdefinierten Vergleichern gedacht.
Steven Evers
1
Ich würde sagen, verwenden Sie den gleichen Ansatz ... ich kann jedoch nicht sagen, dass ich zuvor einen funktionalen PQ implementiert habe ... dieser Artikel schlägt vor, geordnete Sequenzen als nichtlineare Näherung zu verwenden
Michael Brown
0

In einem Versuch, die Dinge "einfach" zu halten, verfügt .NET nur über ein generisches / nicht generisches Schnittstellenpaar für Dinge, die durch Aufrufen GetEnumerator()und anschließendes Verwenden MoveNextund Verwenden Currentdes daraus empfangenen Objekts aufgelistet werden, obwohl es mindestens vier Arten von Objekten gibt die nur diese Methoden unterstützen sollten:

  1. Dinge, die mindestens einmal aufgezählt werden können, aber nicht unbedingt mehr.
  2. Dinge, die in Kontexten mit freiem Thread beliebig oft aufgezählt werden können, aber jedes Mal willkürlich unterschiedliche Inhalte liefern können
  3. Dinge, die in Free-Thread-Kontexten beliebig oft aufgezählt werden können, aber garantieren können, dass alle Aufzählungen denselben Inhalt zurückgeben, wenn Code, der sie wiederholt auflistet, keine mutierenden Methoden aufruft.
  4. Dinge, die beliebig oft aufgezählt werden können und garantiert jedes Mal den gleichen Inhalt zurückgeben, solange sie existieren.

Jede Instanz, die eine der höher nummerierten Definitionen erfüllt, erfüllt auch alle niedrigeren, aber Code, der ein Objekt erfordert, das eine der höheren Definitionen erfüllt, kann brechen, wenn eine der niedrigeren Definitionen angegeben wird.

Es scheint, dass Microsoft entschieden hat, dass Klassen, die implementieren IEnumerable<T>, die zweite Definition erfüllen sollten, aber nicht verpflichtet sind, etwas Höheres zu erfüllen. Es gibt wohl nicht viel Grund, warum etwas, das nur die erste Definition erfüllen könnte, IEnumerable<T>eher implementiert werden sollte als IEnumerator<T>; Wenn foreachSchleifen akzeptieren könnten IEnumerator<T>, wäre es sinnvoll, Dinge, die nur einmal aufgezählt werden können, einfach die letztere Schnittstelle zu implementieren. Leider sind Typen, die nur implementiert IEnumerator<T>werden, in C # und VB.NET weniger bequem zu verwenden als Typen, die über eine GetEnumeratorMethode verfügen .

In jedem Fall gibt es noch IEnumerable<T>keine solchen Typen , obwohl es nützlich wäre, wenn es verschiedene Aufzählungstypen für Dinge gäbe, die unterschiedliche Garantien geben könnten, und / oder eine Standardmethode, um eine Instanz zu fragen, die implementiert, welche Garantien sie geben kann.

Superkatze
quelle
0

Ich denke, dies wäre ein Verstoß gegen das Liskov-Substitutionsprinzip, das besagt:

Objekte in einem Programm sollten durch Instanzen ihrer Untertypen ersetzt werden können, ohne die Richtigkeit dieses Programms zu ändern.

Wenn ich eine Methode wie die folgende hätte, die in meinem Programm mehr als einmal aufgerufen wird,

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

Ich sollte in der Lage sein, alle IEnumerable auszutauschen, ohne die Richtigkeit des Programms zu ändern, aber die Verwendung der destruktiven Warteschlange würde das Verhalten des Programms erheblich verändern.

Despertar
quelle