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)})) 

以下に示すように、2つのツリー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 

で共有しかし、ことは明らかである一つは左のサブツリーに新しい値を「1」挿入することにより、新しいツリーT3を作成した場合

この結果、すべての値がコピーされ、構造共有は全く行われない、まったく新しいツリーが作成されるのでしょうか。もし左の枝が2→3→4→5→6→7（*ルート）となり、1が左のサブツリーに挿入されたとすると、構造の共有は維持されますか？

Answer 1

新しい値が置き換えられます挿入する場所へのパス上のノードが、少なくとも二つのことは1つが全体のストーリーを取得するために気づくべきあります

1. の交換をxconj操作の途中のノードは、そのサブツリーとその値の1つを保持します。 1つのサブツリーのみがスワップアウトされます。 （左、左、左のパスに沿ってノードを置き換えると、左、右、右の位置のノードが共有されます）。したがって、多くの構造が共有される可能性があります。いずれかの葉へのパスが置き換えられます。

2. 置き換えられるノードはマップです。彼らは3つのキーよりも大きかった場合は、新しいマップを作成するのではなく、assoc/assoc-in/update-inを使用するように理にかなって：新しいノードマップより

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

   を古いノードマップと構造を共有することができるだろう。 （ノードがどれほど小さいかによってもう一度ここでは意味をなさないが、異なる状況ではこれが大きな違いを生むことができる）。