Take the 2-minute tour ×

I would like to use a type that behaves like a simple list of pairs [(a,b)] that serves as a dictionary, mapping keys of type a to values of type b, while maintaining a "user-specified", defined order of keys. (i.e. just as with ordinary lists - I would like to be able to "append" an item which is then recognized as the "last element".) However I would like random access lookup on keys with better than linear performance, i.e. what Data.Map provides. One option would be to just maintain an ordinary map in addition to a list of keys that defines their order:

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

and then define append operations, etc. that keep the two key collections in sync. It seems ugly though to maintain two separate collections of the same keys. Is there a ready-made data type that already combines ordered keys with efficient random-access lookup by key?

share|improve this question
Java's LinkedHashMap seems to do something similar: thread a list of keys through the map. Python's OrderedDict is simply a list of pairs, so they're no help here. –  Lambda Fairy Jun 8 '12 at 4:07
What do you mean with "defined order"? Given two keys a1 and a2, is it a priori fixed whether a1 precedes a2 or is the precedence determined at runtime? –  Peter Jun 8 '12 at 6:46
@peter I mean 'defined order' in the same sense as with ordinary lists - if I append a2 after I append a1, then a1 precedes a2 –  gcbenison Jun 8 '12 at 13:54
add comment

3 Answers

Take a look at ixset library - it allows you to maintain sets indexed by multiple columns (by a and by Int in your case). This is much more maintainable than keeping maps consistent by hand

share|improve this answer
Thanks - ixset is cool. I don't think it quite matches the bill in this case because it can allow inconsistent state (multiple entries with the same Int field) and it would require a caller performing an append operation to explicitly specify the index - something not required by ordinary lists. –  gcbenison Jun 8 '12 at 15:13
add comment

Unless I completely misunderstand your question, Data.Map does exactly this, using the key type's Ord instance for ordering. As it's a binary tree, the implementation keeps the keys ordered as well.

Data.Map.keys gives you the keys of a map in ascending order; as transformations, such as map, of a Map are purely functional the order of traversal is irrelevant, and all ways of getting a sequence of keys or key/value pairs out of a Map gives you an ordered list.

share|improve this answer
I believe gcbenison is asking for something like Data.Map but with the added property of preserving the order in which the keys are inserted. –  dbaupp Jun 8 '12 at 7:05
add comment

If you just want to preserve some fixed order (e.g. insertion time) in addition of having O(log n) lookup/insertions, you could simply use multiple maps and update them simultaneously:

  1. Map a b for storing the actual data, and
  2. Map Int a that gives you the i-th key in the order. (If you also need to query the index of a given key you could add a Map a Int)
share|improve this answer
add comment

Your Answer


