Ein Dictionary-Typ mit einer definierten Reihenfolge der Schlüssel

Question

Ich möchte einen Typ verwenden, der sich wie eine einfache Liste von Paaren [(a,b)], die als ein Wörterbuch dient, Tasten des Typs a auf Werte des Typs b, unter Beibehaltung eines "Benutzers "spezifizierte", definierte Reihenfolge der Schlüssel. (also wie bei gewöhnlichen Listen - ich würde gerne ein Element "anhängen" können, das dann als "letztes Element" erkannt wird.) Allerdings möchte ich auf Tasten mit besserer als linearer Performance nach dem Zufallsprinzip suchen, also was Data.Map bietet. Eine Möglichkeit wäre, nur eine gewöhnliche Karte zusätzlich zu einer Liste von Schlüsseln zu halten, die ihre Reihenfolge definiert:

data OrderedDict a b = OrderedDict (Map a b) [a] 

und dann append Operationen definieren, etc., die die beiden wichtigsten Sammlungen synchron zu halten. Es scheint jedoch hässlich, zwei getrennte Sammlungen derselben Schlüssel zu verwalten. Gibt es einen vorgefertigten Datentyp, der bereits geordnete Schlüssel mit effizientem wahlfreiem Zugriff nach Schlüsseln kombiniert?

Answer 1

Sofern ich Ihre Frage nicht völlig falsch verstanden habe, macht Data.Map genau das, indem sie die Ord Instanz des Schlüsseltyps zur Bestellung verwendet. Da es sich um einen Binärbaum handelt, enthält die Implementierung auch die bestellten Schlüssel.

Data.Map.keys gibt Ihnen die Schlüssel einer Karte in aufsteigender Reihenfolge; Da Transformationen, wie map, einer Map rein funktional sind, ist die Reihenfolge der Traversierung irrelevant, und alle Möglichkeiten, eine Sequenz von Schlüsseln oder Schlüssel/Wert-Paaren aus einer Map zu erhalten, ergeben eine geordnete Liste.

Answer 2

Wenn Sie nur einige feste Bestellung (zB Einführungszeit) erhalten wollen zusätzlich von O mit (log n) Lookup/Einfügungen Sie einfach mehrere Karten verwenden könnte und aktualisieren sie gleichzeitig:

1. Map a b zum Speichern der tatsächlichen Daten und
2. Map Int a, die Sie den i-ten Schlüssel in der Reihenfolge gibt. (Wenn Sie auch den Index eines bestimmten Schlüssel abfragen müssen könnten Sie ein Map a Int hinzufügen)

Answer 3

Werfen Sie einen Blick auf ixset Bibliothek - es Sie nach mehreren Spalten indiziert Sätze pflegen können (durch a und von Int in Ihrem Fall). Dies ist viel wartungsfreundlicher als Karten konsistent per Hand zu halten