Order-respecting Map?

[ovatsus]

Time and time again I face the issue of having to replace a Map with a list of pairs, because I need the original order to be preserved.
Would be nice to have a collection like that, even if it's just having both Map and a list of keys under the hood

[mausch]

Maybe just a few functions around a list of key/value pairs? (as in http://hackage.haskell.org/package/hxt-8.3.2/docs/Data-AssocList.html or http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#6_Associationlists )

[ovatsus]

That's what I usually do, but that way you loose the performance of the lookups

[kspeakman]

I find myself needing this too. I trivial implementation would be to wrap a PersistentVector (or a basic List that you just know is in reverse order) together with a Map. Using the first for key ordering and the second for value lookup. But it would be nice not to double up on memory usage for keys.