clojure - Clojure 中的结构共享

Question

我不清楚 Clojure 中的结构共享。下面是一个取自 Clojure 的乐趣(顺便说一句好书)的函数 xconj。

;;Building a naive binary search tree using recursion
(defn xconj [t v]
      (cond 
          (nil? t) {:val v :L nil :R nil}
          (< v (:val t)) {:val (:val t) :L (xconj (:L t) v) :R (:R t)}
          :else {:val (:val t) :L (:L t) :R (xconj (:R t) v)}))

如果定义两棵树 t1 和 t2 如下所示。

(def t1 (xconj (xconj (xconj nil 5) 3) 2))
(def t2 (xconj t1 7))

很明显，左子树由 t1 & t2 共享

user> (identical? (:L t1) (:L t2))
true

但是如果要创建一棵新树 t3，通过在 t1 的左子树中插入一个新值“1”，如下所示:

(def t3 (xconj t1 1))

这会导致一个全新的树，所有值都被复制并且没有结构共享，还是仍然会共享一些结构？如果左分支更大，比如 2->3->4->5->6->7(*root) 并且 1 被插入到左子树中，那么一些结构共享会持续吗？

Answer 1

到要插入新值的位置的路径上的节点将被替换，但是要了解整个故事，至少应该注意两件事:

更换非 nil xconj 过程中的节点操作保留其子树之一及其值；只有一个子树被换出。 (如果你沿路径“左、左、左”替换节点，那么位置“左、左、右”的节点将被共享。)因此，即使沿路径的所有节点，很多结构也可能被共享其中一片叶子的路径被替换。

被替换的节点是 map 。如果它们大于三个键，则使用 assoc 是有意义的。/assoc-in/update-in而不是构建新 map :

...
(< v (:val t)) (update-in t [:L] xconj v)
...

新节点映射将能够与旧节点映射共享结构。 (再一次，这里没有意义，因为节点有多小；但在不同的上下文中，这可能会产生巨大的差异。)