Ich möchte einen Typ verwenden, der sich wie eine einfache Liste von Paaren [(a,b)] verhält, die als Wörterbuch dienen und Schlüssel vom Typ a auf Werte vom Typ b abbilden, während ein "benutzerdefinierter" Wert beibehalten wird. , 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.) Ich möchte jedoch eine zufällige Zugriffssuche auf Keys mit besser als linearer Performance, also was Data.Map bietet. Eine Option wäre, neben einer Liste von Schlüsseln, die ihre Reihenfolge definieren, lediglich eine gewöhnliche Karte beizubehalten:
und definieren Sie dann append -Operationen usw., die die beiden Schlüsselsammlungen synchron 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 effizienter Random-Access-Suche nach Schlüssel kombiniert?
Sofern ich Ihre Frage nicht völlig falsch verstanden habe, tut Data.Map genau das, indem er die Ord -Instanz des Schlüsseltyps für die 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 zum Beispiel map , einer Map rein funktional sind, ist die Reihenfolge der Traversierung irrelevant, und alle Möglichkeiten, eine Folge von Schlüsseln oder Schlüssel / Wert-Paaren aus einer Map zu erhalten, ergeben eine geordnete Liste.
Wenn Sie nur eine feste Reihenfolge (z. B. die Einfügezeit) beibehalten und zusätzlich O (log n) suchen / einfügen möchten, können Sie einfach mehrere Maps verwenden und diese gleichzeitig aktualisieren:
Map a b zum Speichern der eigentlichen Daten und Map Int a , die Ihnen den i-ten Schlüssel in der Reihenfolge gibt. (Wenn Sie auch den Index eines bestimmten Schlüssels abfragen müssen, können Sie ein Map a Int hinzufügen) Tags und Links haskell