Welcome! Please see the About page for a little more info on how this works.

0 votes
in Collections by

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))
> (class x)
> 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))
> (class xw)
> xw
{:e 5, :g 7, :c 3, :j 10, :h 8, :b 2, :d 4, :f 6, :i 9, :a 1}

1 Answer

0 votes

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

"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]
        (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=> (def xw (clojure.walk/postwalk identity x))
    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)
    clojure.walk=> (= (seq xw) (seq x))
    clojure.walk=> (type xw)

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):


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):