Clojure中的结构共享

Question

我不清楚Clojure中的结构共享.下面是一个取自Clojure的欢乐的函数xconj(Great book BTW).

;;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(*根),并且在左子树中插入1,那么结构的某些共享会持续存在怎么办？

Answer 1

将替换插入新值的位置的路径上的节点,但至少有两件事需要注意才能得到整个故事:

1. nil在xconj操作过程中替换非节点会保留其中一个子树及其值; 只换出一个子树.(如果沿"左,左,左"路径替换节点,则"左,左,右"位置的节点将被共享.)因此,即使沿着所有节点,也可能共享许多结构.其中一片叶子的路径被替换.

2. 被替换的节点是地图.如果它们大于三个键,那么使用assoc/ assoc-in/ update-in而不是构建新映射是有意义的:

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

   比新节点映射能够与旧节点映射共享结构.(再一次,这里没有意义,因为节点有多小;但在不同的情况下,这会产生巨大的差异.)