Структурный обмен в Clojure

Question

Я не понимаю о структурном разделении в Clojure. Ниже приведена функция xconj, взятая из Радости Clojure (Великая книга 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, вставляя новое значение «1» в левом поддереве t1, как это:

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

   Чем новая карта узла будет иметь возможность разделить структуру со старой картой узла. (И снова здесь это не имеет смысла из-за того, насколько малы узлы, но в разных контекстах это может иметь огромное значение.)