Gibt es einen bestimmten Zweck für heterogene Listen?

Ich komme aus C # und Java und bin es gewohnt, dass meine Listen homogen sind, und das macht für mich Sinn. Als ich anfing, Lisp aufzunehmen, bemerkte ich, dass die Listen heterogen sein können. Als ich anfing, mit dem dynamicSchlüsselwort in C # herumzuspielen, bemerkte ich, dass es ab C # 4.0 auch heterogene Listen geben kann:

List<dynamic> heterogeneousList

Meine Frage ist, worum geht es? Es scheint, als würde eine heterogene Liste bei der Verarbeitung viel mehr Aufwand verursachen. Wenn Sie verschiedene Typen an einem Ort speichern müssen, benötigen Sie möglicherweise eine andere Datenstruktur. Bringt meine Naivität ihr hässliches Gesicht zur Geltung oder gibt es wirklich Zeiten, in denen es nützlich ist, eine heterogene Liste zu haben?

Die Veröffentlichung Stark typisierte heterogene Sammlungen von Oleg Kiselyov, Ralf Lämmel und Keean Schupke enthält nicht nur eine Implementierung heterogener Listen in Haskell, sondern auch ein motivierendes Beispiel dafür, wann, warum und wie Sie HLists verwenden würden. Insbesondere verwenden sie es für den typsicheren, zur Kompilierungszeit überprüften Datenbankzugriff. (Denken Sie LINQ, in der Tat, das Papier , das sie verweisen, ist das Haskell Papier von Erik Meijer et al, die LINQ geführt.)

Zitat aus dem einleitenden Absatz des HLists-Papiers:

Hier ist eine offene Liste typischer Beispiele, die heterogene Sammlungen erfordern:

• Eine Symboltabelle, in der Einträge unterschiedlichen Typs gespeichert werden sollen, ist heterogen. Es ist eine endliche Karte, bei der der Ergebnistyp vom Argumentwert abhängt.
• Ein XML-Element ist heterogen typisiert. Tatsächlich sind XML-Elemente verschachtelte Auflistungen, die durch reguläre Ausdrücke und die 1-Ambiguity-Eigenschaft eingeschränkt sind.
• Jede Zeile, die von einer SQL-Abfrage zurückgegeben wird, ist eine heterogene Zuordnung von Spaltennamen zu Zellen. Das Ergebnis einer Abfrage ist ein homogener Strom heterogener Zeilen.
• Das Hinzufügen eines erweiterten Objektsystems zu einer funktionalen Sprache erfordert heterogene Sammlungen, die erweiterbare Datensätze mit Untertypen und einer Aufzählungsschnittstelle kombinieren.

Beachten Sie, dass die Beispiele, die Sie in Ihrer Frage angegeben haben, keine heterogenen Listen in dem Sinne sind, dass das Wort allgemein verwendet wird. Sie sind schwach typisierte oder untypisierte Listen. Tatsächlich handelt es sich um homogene Listen, da alle Elemente vom gleichen Typ sind: objectoder dynamic. Sie sind dann gezwungen, Casts oder ungeprüfte instanceofTests oder ähnliches durchzuführen, um tatsächlich mit den Elementen sinnvoll arbeiten zu können, wodurch sie schwach getippt werden.

Lange Rede, kurze, heterogene Container tauschen Laufzeitleistung gegen Flexibilität aus. Wenn Sie eine „Liste von Dingen“ ohne Rücksicht auf die jeweilige Art von Dingen haben möchten, ist Heterogenität der richtige Weg. Lisps sind charakteristisch dynamisch typisiert, und fast alles ist ohnehin eine Liste von Box-Werten, so dass der kleinere Performance-Hit erwartet wird. In der Lisp-Welt ist die Produktivität von Programmierern wichtiger als die Laufzeitleistung.

In einer dynamisch typisierten Sprache hätten homogene Container tatsächlich einen geringen Overhead im Vergleich zu heterogenen Containern, da alle hinzugefügten Elemente typüberprüft werden müssten.

Ihre Intuition, eine bessere Datenstruktur zu wählen, ist klar. Im Allgemeinen gilt: Je mehr Verträge Sie für Ihren Code einrichten können, desto mehr wissen Sie über die Funktionsweise des Codes und desto zuverlässiger, wartbarer und c. es wird. Manchmal möchten Sie jedoch wirklich einen heterogenen Container, und es sollte Ihnen gestattet sein, einen zu haben, wenn Sie ihn benötigen.

In funktionalen Sprachen (wie lisp) verwenden Sie den Mustervergleich, um zu bestimmen, was mit einem bestimmten Element in einer Liste geschieht. Das Äquivalent in C # wäre eine Kette von if ... elseif-Anweisungen, die den Typ eines Elements prüfen und eine darauf basierende Operation ausführen. Es erübrigt sich zu erwähnen, dass der funktionale Mustervergleich effizienter ist als die Überprüfung des Laufzeit-Typs.

Die Verwendung von Polymorphismus wäre eine engere Übereinstimmung mit der Musterübereinstimmung. Das heißt, die Objekte einer Liste stimmen mit einer bestimmten Schnittstelle überein, und für jedes Objekt wird eine Funktion für diese Schnittstelle aufgerufen. Eine andere Alternative wäre die Bereitstellung einer Reihe überladener Methoden, die einen bestimmten Objekttyp als Parameter verwenden. Die Standardmethode, die Object als Parameter verwendet.

public class ListVisitor
{
  public void DoSomething(IEnumerable<dynamic> list)
  {
    foreach(dynamic obj in list)
    {
       DoSomething(obj);
    }
  }

  public void DoSomething(SomeClass obj)
  {
    //do something with SomeClass
  }

  public void DoSomething(AnotherClass obj)
  {
    //do something with AnotherClass
  }

  public void DoSomething(Object obj)
  {
    //do something with everything els
  }
}

Dieser Ansatz liefert eine Annäherung an den Lisp-Musterabgleich. Das Besuchermuster (wie hier implementiert, ist ein großartiges Anwendungsbeispiel für heterogene Listen). Ein weiteres Beispiel wäre das Versenden von Nachrichten, bei dem sich Listener für bestimmte Nachrichten in einer Prioritätswarteschlange befinden und die Verantwortungskette verwendet wird. Der Dispatcher übergibt die Nachricht und der erste Handler, der mit der Nachricht übereinstimmt, verarbeitet sie.

Die Kehrseite benachrichtigt alle, die sich für eine Nachricht registrieren (z. B. das Ereignisaggregatormuster, das häufig für die lose Kopplung von ViewModels im MVVM-Muster verwendet wird). Ich benutze das folgende Konstrukt

IDictionary<Type, List<Object>>

Die einzige Möglichkeit, dem Wörterbuch etwas hinzuzufügen, ist eine Funktion

Register<T>(Action<T> handler)

(und das Objekt ist eigentlich eine WeakReference zum übergebenen Handler). Hier MUSS ich also List <Object> verwenden, da ich zur Kompilierungszeit nicht weiß, wie der geschlossene Typ aussehen wird. Zur Laufzeit kann ich jedoch erzwingen, dass es der Typ ist, der den Schlüssel für das Wörterbuch darstellt. Wenn ich das Ereignis auslösen möchte, rufe ich an

Send<T>(T message)

und wieder löse ich die liste auf. Die Verwendung von List <dynamic> bietet keinen Vorteil, da ich sie ohnehin umsetzen muss. Wie Sie sehen, haben beide Ansätze ihre Vorzüge. Wenn Sie ein Objekt mithilfe der Methode "Überladen" dynamisch versenden möchten, können Sie dies mithilfe der Methode "Dynamisch" tun. Wenn Sie trotzdem gezwungen sind, zu zaubern, können Sie auch Object verwenden.

Sie haben Recht, dass Heterogenität die Laufzeit überfordert, aber was noch wichtiger ist, sie schwächt die Garantie für die Kompilierungszeit, die der Typechecker bietet. Trotzdem gibt es einige Probleme, bei denen die Alternativen noch teurer sind.

Nach meiner Erfahrung stoßen Sie beim Umgang mit unformatierten Bytes über Dateien, Netzwerk-Sockets usw. häufig auf solche Probleme.

Um ein reales Beispiel zu geben, betrachten Sie ein System für die verteilte Berechnung unter Verwendung von Futures . Ein Worker auf einem einzelnen Knoten kann Arbeit von jedem serialisierbaren Typ erzeugen, was eine Zukunft dieses Typs ergibt. Hinter den Kulissen sendet das System die Arbeit an einen Kollegen und speichert dann einen Datensatz, in dem diese Arbeitseinheit mit der jeweiligen Zukunft verknüpft ist, die ausgefüllt werden muss, sobald die Antwort auf diese Arbeit zurückkehrt.

Wo können diese Aufzeichnungen aufbewahrt werden? Intuitiv ist das, was Sie wollen, so etwas wie ein Dictionary<WorkId, Future<TValue>>, aber dies beschränkt Sie auf die Verwaltung nur einer Art von Futures im gesamten System. Der geeignetere Typ ist Dictionary<WorkId, Future<dynamic>>, da der Arbeiter den geeigneten Typ wählen kann, wenn er die Zukunft erzwingt.

Hinweis : Dieses Beispiel stammt aus der Haskell-Welt, in der wir keine Untertypen haben. Es würde mich nicht wundern, wenn es in C # eine idiomatischere Lösung für dieses spezielle Beispiel gibt, die aber hoffentlich immer noch illustrativ ist.

ISTR, dass Lisp keine anderen Datenstrukturen als eine Liste hat. Wenn Sie also einen Typ eines aggregierten Datenobjekts benötigen, muss es sich um eine heterogene Liste handeln. Wie bereits erwähnt, sind sie auch nützlich, um Daten für die Übertragung oder Speicherung zu serialisieren. Ein nettes Feature ist, dass sie auch offen sind, sodass Sie sie in einem System verwenden können, das auf einer Pipes-and-Filter-Analogie basiert, und aufeinanderfolgende Verarbeitungsschritte ausführen, um die Daten zu erweitern oder zu korrigieren, ohne dass entweder ein festes Datenobjekt oder eine Workflow-Topologie erforderlich ist .