Un tipo di dizionario con un ordine definito di chiavi

Question

Vorrei utilizzare un tipo che si comporta come un semplice elenco di coppie [(a,b)] che funge da dizionario, associando chiavi di tipo a a valori di tipo b, mantenendo un "utente" -specificato ", definito l'ordine delle chiavi. (vale a dire, proprio come con le liste ordinarie, mi piacerebbe poter "aggiungere" un elemento che viene riconosciuto come "ultimo elemento"). Tuttavia, mi piacerebbe che la ricerca di accesso casuale sui tasti fosse migliore delle prestazioni lineari, ovvero cosa,fornisce. Una possibilità sarebbe quella di mantenere solo una carta ordinaria, oltre a un elenco di chiavi che definisce il loro ordine:

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

e quindi definire append operazioni, ecc che mantengono le due collezioni principali in sincronia. Sembra brutto però mantenere due raccolte separate delle stesse chiavi. Esiste un tipo di dati già pronto che combina già le chiavi ordinate con una ricerca di accesso casuale efficiente per chiave?

Answer 1

A meno che non abbia completamente frainteso la tua domanda, Data.Map fa esattamente questo, usando l'istanza Ord del tipo di chiave per l'ordine. Essendo un albero binario, l'implementazione mantiene anche le chiavi ordinate.

Data.Map.keys fornisce le chiavi di una mappa in ordine crescente; Poiché le trasformazioni, come ad esempio map, di una Carta sono puramente funzionali, l'ordine di attraversamento è irrilevante e tutti i modi per ottenere una sequenza di chiavi o coppie chiave/valore da una Mappa forniscono una lista ordinata.

Answer 2

Se si desidera solo per preservare alcuni fisso ordine (ad esempio, il tempo di inserimento) oltre ad avere O (log n) di ricerca/inserzioni, si può semplicemente utilizzare più mappe e aggiornarli contemporaneamente:

1. Map a b per la memorizzazione dei dati effettivi e
2. Map Int a che fornisce la chiave i-es nell'ordine. (Se hai bisogno anche di interrogare l'indice di una data chiave si potrebbe aggiungere un Map a Int)

Answer 3

Date un'occhiata a ixset biblioteca - permette di mantenere set indicizzate da più colonne (da a e Int nella vostra Astuccio). Questo è molto più gestibile che mantenere le mappe coerenti a mano