bug in walker with array-maps

Question

The walker doesn't handle array-maps properly, IMO. It converts them to regular maps and loses the ordering information.

> (def x (array-map :a 1 :b 2 :c 3 :d 4 :e 5 :f 6 :g 7 :h 8 :i 9 :j 10))
#'x
> (class x)
clojure.lang.PersistentArrayMap
> x
{:e 5, :g 7, :c 3, :j 10, :h 8, :b 2, :d 4, :f 6, :i 9, :a 1}
> (def xw (clojure.walk/postwalk identity x))
#'xw
> (class xw)
clojure.lang.PersistentHashMap
> xw
{:e 5, :g 7, :c 3, :j 10, :h 8, :b 2, :d 4, :f 6, :i 9, :a 1}

Answer 1

Maps are unordered and in general map “modifying” operations make no guarantees about ordering. So, I do not see this as a bug.

Comments

"When doing code form manipulation it is often desirable to have a map which maintains key order. An array map is such a map -"  https://clojure.org/reference/data_structures#ArrayMaps

---

Also, I'd argue that if array-map is in the language it ought to be there for a reason, and if it doesn’t preserve order its just an inefficient version of a regular map (and it DOES preserve order; it's the walker that doesn't).

---

It is not just postwalk, it is N other functions that take a map as input and return a map that are not promised to return an array-map, and thus not preserve the order, e.g.: conj (if you go over 8 keys), merge, assoc, etc.  The list of those that promise nothing about returning an array-map with the same order (and do not in the current implementation) is very very long.

---

You quote the official Clojure.org docs on array maps, where it also says in the same paragraph you quoted: "Note that an array map will only maintain sort order when un-'modified'. Subsequent assoc-ing will eventually cause it to 'become' a hash-map."

---

The confounding factor is the general auto-promotion of array maps in the implementation.  Even user-defined array maps will auto-promote on assoc.  By default array-maps (possibly constructed via normal hash-map reader literals, or hash-map constructor supplied with 8 key vals), will auto promote to hash maps if their size changes to > 8.  Even a user defined array map is not immune; if you keep the count the same you can update existing keys while retaining the array-map implementation, but as soon as you grow a new entry, the structure is promoted to a hashmap (for efficiency).

To be fair, walking with identity, I would expect the input to be unchanged and not return a hashmap (that's my assumption though).  As implemented, walk will change the array map even though nothing is really being done to modify it:

This is what happens in the implementation in `walk`, which falls through the conditions in `cond` until it hits the catch-all collection implementation:

    (coll? form) (outer (into (empty form) (map inner form)))

`empty` creates an ampty array map, which is then grown via `conj` (actually transiently with `conj!`) which eventually hits the array-map's limit at 8 and bumps over to a hashmap.

A simple work around is to provide a custom case for walk that detects array-maps and leaves them as is.  To do this, you have to construct the array-map explicitly though:

    (defn walk
      [inner outer form]
      (cond
        (list? form) (outer (apply list (map inner form)))
        (instance? clojure.lang.IMapEntry form)
        (outer (clojure.lang.MapEntry/create (inner (key form)) (inner (val form))))
        (seq? form) (outer (doall (map inner form)))
    
        (instance? clojure.lang.PersistentArrayMap form)
        (outer (apply array-map (reduce (fn [acc [k v]] (conj acc (inner k) (inner v))) [] form)))
    
        (instance? clojure.lang.IRecord form)
        (outer (reduce (fn [r x] (conj r (inner x))) form form))
        (coll? form) (outer (into (empty form) (map inner form)))
        :else (outer form)))

If you monkey-patch core.walk it seems to work:

    clojure.walk=> (def x (array-map :a 1 :b 2 :c 3 :d 4 :e 5 :f 6 :g 7 :h 8 :i 9 :j 10))
    #'clojure.walk/x
    clojure.walk=> (def xw (clojure.walk/postwalk identity x))
    #'clojure.walk/xw
    clojure.walk=> xw
    {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :g 7, :h 8, :i 9, :j 10}
    clojure.walk=> (= xw x)
    true
    clojure.walk=> (= (seq xw) (seq x))
    true
    clojure.walk=> (type xw)
    clojure.lang.PersistentArrayMap

However, the promotion is still possible, e.g. if `outer` does something to grow the resulting map.

---

Thanks for all the comments! The patch to the walker is just what I had in mind.

Array-map doesn't seem to be very useful or used as defined. But an ordered map is a useful abstraction in some rare cases; perhaps that should be added to the language. Unlike array-maps, they would retain their nature under pseudo-mutation.

---

Here's an implementation of ordered maps (and sets):

https://github.com/clj-commons/ordered

Also, relevant is CLJ-1239, which proposes a protocol-based clojure.walk (I believe you could get the behavior you desire by extending its Walkable protocol to array maps):

https://clojure.atlassian.net/browse/CLJ-1239