2024 Clojure现状调查!中分享您的想法。

欢迎!请参阅关于页面以了解该服务的工作方式。

0
集合

在我看来,walker没有正确处理数组映射。它将它们转换为普通映射并丢失了排序信息。

> (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}

1 个答案

0

映射是无序的,并且在一般情况下,映射“修改”操作不会保证排序。因此,我认为这不是一个bug。

"在执行代码形式操作时,通常希望有一个能够保持键排序的映射。数组映射就是这样的映射 -"  https://clojure.org/reference/data_structures#ArrayMaps
我也认为,如果语言中包含了array-map,那肯定有它的原因。如果它不保留顺序,那它就只是常规map的低效版本,而且它确实保留了顺序;是walker没有保留。
这不仅是对后序遍历有所考虑,还有许多其他接受map作为输入并返回map的函数(并不保证返回顺序一致的array-map),例如: conj(如果你有超过8个键),merge,assoc等。那些承诺返回与顺序一致的array-map的列表(在当前实现中也不这么做)非常非常长。
你引用了Clojure.org官方文档中关于array-map的部分,其中也提到你引用的同一段话:"请注意,只有在未进行'unmodified'操作时,数组映射才会维护排序顺序。随后的assoc操作最终会使其变为哈希表。"
困扰的因素是在实现中普遍自动将array-map提升到哈希表。即使是用户定义的array-map在assoc时也会自动提升。默认情况下,array-maps(可能是由普通哈希表reader字面量或包含8个键值的哈希表构造器创建的)如果大小变为>8,将自动提升为哈希表。即使是用户定义的array-map也无法幸免;如果你保持计数不变,你可以在保留array-map实现的情况下更新现有键,但一旦添加新条目,结构将提升为哈希表(以提高效率)。

公平起见,使用恒等函数进行遍历,我预计输入不会改变,并且不返回哈希表(但这只是我的假设)。按照当前的实现,walk甚至会更改array map,尽管实际上并没有做任何修改。

这是`walk`实现中的情况,它会在`cond`中的条件中遍历,直到遇到通用的集合实现。

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

`empty`创建一个空的数组映射,然后通过`conj`(实际上是临时使用`conj!`)来增长,最终达到了数组映射的8个键限制,然后提升到哈希表。

一个简单的解决方案是为“行走”提供一个自定义的情况,它能检测到数组映射并保持其原样。为了实现这一点,您必须显式地构造数组映射。

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

如果对core.walk进行猴.patch,似乎可以工作

    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

但是,提升仍然可能,例如如果 `outer` 对生成的映射做了某些事情以扩大它。
by
感谢所有评论!对行走器的修补正是我想要的。

数组映射似乎没有太大用途或使用,但有序映射在某些罕见的情况下是一个有用的抽象;也许应该将其添加到语言中。与数组映射不同,它们在伪变异下会保留其性质。
by
以下是有序映射(和集合)的实现

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

还有 CLJ-1239,它建议使用基于协议的 clojure.walk(我相信您可以通过扩展其 Walkable 协议到数组映射来获得您想要的行为)

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