Un tipo de diccionario con un orden definido de claves

Question

Me gustaría utilizar un tipo que se comporta como una lista simple de pares [(a,b)] que sirve como diccionario, asignando claves del tipo a a valores del tipo b, mientras se mantiene un "usuario -specified ", orden definido de claves. (es decir, al igual que con las listas ordinarias, me gustaría poder "agregar" un elemento que luego se reconoce como el "último elemento"). Sin embargo, me gustaría buscar acceso aleatorio en claves con un rendimiento mejor que lineal, es decir, qué Data.Map proporciona. Una opción sería la de simplemente mantener un mapa ordinaria, además de una lista de claves que define su orden:

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

y luego definir append operaciones, etc., que mantienen las dos colecciones principales sincronizados. Sin embargo, parece feo mantener dos colecciones separadas de las mismas claves. ¿Hay un tipo de datos ya preparado que ya combine teclas ordenadas con búsqueda de acceso aleatorio eficiente por clave?

Answer 1

A menos que malinterprete por completo su pregunta, Data.Map hace exactamente esto, utilizando la instancia del tipo de clave Ord para ordenar. Como es un árbol binario, la implementación también mantiene las claves ordenadas.

Data.Map.keys le da las teclas de un mapa en orden ascendente; como las transformaciones, como map, de un mapa son puramente funcionales, el orden de recorrido es irrelevante, y todas las formas de obtener una secuencia de claves o pares clave/valor de un mapa le dan una lista ordenada.

Answer 2

Si lo que desea es conservar algunas fija fin (por ejemplo, tiempo de inserción), además de tener O (log n) operaciones de búsqueda/inserciones, simplemente podría utilizar múltiples mapas y actualizar de forma simultánea:

1. Map a b para almacenar los datos reales, y
2. Map Int a que le proporciona la i-ésima clave en el pedido. (Si también necesita consultar el índice de una clave dada se podría añadir un Map a Int)

Answer 3

Tome un vistazo a ixset biblioteca - que le permite mantener conjuntos indexados por múltiples columnas (por a y por Int en su caso). Esto es mucho más fácil de mantener que mantener los mapas consistentes a mano