Clojure中的結構共享

Question

我不清楚Clojure中的結構共享。下面是來自Joy of Clojure（Great book BTW）的函數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內，在左子樹中插入新的值「1」 T1，像這樣的：

(def t3 (xconj t1 1)) 

請問這個結果在一個完全新的樹，所有的值複製，並沒有結構性共享，或將一些結構仍然能夠共享？如果左分支比較大，說明如果2-> 3-> 4-> 5-> 6-> 7（*根），並且在左子樹中插入了1，那麼結構的某些共享是否會持續？

Answer 1

的路徑，其中新價值要插入將被替換的位置上的節點，但至少有兩件事是一個應該注意讓整個故事：

1. 更換在xconj操作過程中的非nil節點保留其子樹及其值之一;只有一個子樹被換出。 （如果沿路徑「left，left，left」替換節點，那麼位置「left，left，right」處的節點將被共享。）因此，即使節點沿着其中一個葉子的路徑被替換。

2. 被替換的節點是地圖。如果他們比只有三個按鍵較大，這將是有意義的使用assoc/assoc-in/update-in而不是建立新地圖：

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

   比新節點地圖將能夠與舊節點地圖分享結構。 （再一次，這裏沒有意義，因爲節點有多小;但是在不同的上下文中，這可能會產生巨大的差異。）