Udostępnianie strukturalne w Clojure

Question

Nie mam jasności co do strukturalnego udostępniania w Clojure. Poniżej znajduje się funkcja xconj zaczerpnięta z Joy of Clojure (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)})) 

Jeśli zdefiniowano dwa drzewa t1 i t2, jak pokazano poniżej.

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

Jest oczywiste, że lewica poddrzewo jest dzielona przez t1 & t2

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

Ale jeśli jeden z nich, aby utworzyć nowe drzewo t3, wkładając nową wartość „1” w lewym poddrzewie t1, na przykład:

(def t3 (xconj t1 1)) 

Spowoduje to w zupełnie nowym drzewie ze wszystkich wartości skopiowane i nie dzielenie strukturalny, czy będzie jakiś struktura nadal być udostępniane? Co jeśli lewy oddział był większy, powiedzmy 2-> 3-> 4-> 5-> 6-> 7 (* root), a 1 został wstawiony w lewy poddrzewo, czy pozostanie jakaś struktura podziału?

Answer 1

Węzły na drodze do miejsca, w którym nowa wartość ma zostać wstawiony zostanie zastąpiony, ale istnieją co najmniej dwie rzeczy, jeden powinien zauważyć dostać całą historię:

1. Wymiana węzeł inny niż nil w trakcie operacji xconj zachowuje jeden ze swoich poddrzew i jego wartość; tylko jedno poddrzewo zostaje zamienione. (Jeśli zamienisz węzły wzdłuż ścieżki "lewa, lewa, lewa", wówczas węzeł na pozycji "lewo, prawo, lewo" zostanie udostępniony.) Tak więc wiele struktur może potencjalnie być udostępnionych, nawet jeśli wszystkie węzły wzdłuż ścieżka do jednego z liści zostaje zastąpiona.

2. Wymieniane węzły to mapy. Gdyby były większe niż tylko trzy klucze, byłoby sensu używać assoc/assoc-in/update-in zamiast budować nowe mapy:

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

   od nowego węzła mapie będzie mógł podzielić strukturę ze starego węzła mapie. (Ponownie, tutaj nie ma to sensu ze względu na to, jak małe są węzły, ale w różnych kontekstach może to zrobić dużą różnicę.)