How to get a clojure array-map to maintain insertion order after assoc?

Question

I have an array-map which I am associng some values into it. After a certain size the returned value is a PersistentHashMap rather than the original PersistentArrayMap. I've read about this behavior on a few web sites. Is there any way to force the insertion order even after assoc?

I do have a separate function which will take a ash-map and a vector of keys, and return a "fresh" array-map with keys in this order, but it means that for each assoc, I have to extract the keys first, cons/conj the new key to the vector, then create a new array-map. Seems kludgey, even if written in a separate function.

Is there a more direct language-supported way of keeping insertion order even on large-ish (>10, but < 50) keys array-map?

In case it's relevant, I'm using a list of array-maps as data into an incanter dataset and then outputting to excel. The save-xls function keeps the order of the keys/columns.

Thanks

Philomel

Answer 1

You can use an ordered map: https://github.com/flatland/ordered

Trinl

I was going to suggest keeping both a map of entries and a vector of the keys so that you can keep track of the order in which the keys were inserted—but it looks like that's exactly what the data structures in this library do under the hood. Thanks for sharing! – Shakeup

There's actually an unsolved problem here, in that this approach is pretty efficient for everything but dissoc - you can't just remove an entry from the vector. I tried a number of different approaches, like keeping a sorted-map from index to value; that's good for dissoc but slow for everything else. If you come up with a cool solution, let me know! – Trinl

Scala has a LinkedHashMap that does this efficiently—but it's mutable so it's able to unlink nodes in the middle of its doubly-linked list. Maybe you could apply that methodology to the transient versions of the data structures, but it's not going to be that easy to find a good answer for an immutable map. I bet a good solution to this problem would actually be publishable. – Shakeup

Thanks, now that I think about it, I think I have used this before. I was getting confused with sorted-map. So why does clojure have an array-map at all if it's not going to maintain insertion order? – Philomel

For small maps you can avoid paying the fixed overhead of a hash table; when the map gets larger, array map is no longer more efficient. – Trinl

@amalloy, Have you tried to promote this to clojure? Or at least to contrib? Flimsy array-map is the most frustrating thing in clojure for me so far. – Doze

For the record, LinkedHashMap is a standard map from Java itself, explaining why it's mutable. – Heflin