Chia sẻ cấu trúc trong Clojure

Question

Tôi không rõ ràng về chia sẻ cấu trúc trong Clojure. Dưới đây là một chức năng xconj lấy từ Joy of Clojure (cuốn sách tuyệt vời 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)})) 

Nếu một định nghĩa hai cây t1 và t2 như được hiển thị bên dưới.

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

Rõ ràng là các cây con trái được chia sẻ bởi t1 & t2

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

Nhưng nếu ai đó để tạo ra một t3 cây mới, bằng cách chèn một giá trị mới '1' trong cây con trái của t1, như thế này:

(def t3 (xconj t1 1)) 

Điều này sẽ tạo ra một cây hoàn toàn mới với tất cả các giá trị được sao chép và không chia sẻ cấu trúc hoặc một số cấu trúc vẫn được chia sẻ? Điều gì sẽ xảy ra nếu nhánh bên trái lớn hơn 2-> 3-> 4-> 5-> 6-> 7 (* root) và 1 được chèn vào trong cây con trái, khi đó một số cấu trúc sẽ tồn tại?

Answer 1

Các nút trên đường dẫn đến nơi mà giá trị mới sẽ được chèn sẽ được thay thế, nhưng có ít nhất hai điều người ta phải chú ý để có được toàn bộ câu chuyện:

1. Thay thế một nút phi nil trong quá trình hoạt động xconj duy trì một trong các subtrees và giá trị của nó; chỉ có một cây con được hoán đổi. (Nếu bạn thay thế các nút dọc theo đường dẫn "trái, trái, trái", thì nút ở vị trí "trái, trái, phải" sẽ được chia sẻ.) Vì vậy, rất nhiều cấu trúc có thể được chia sẻ ngay cả khi tất cả các nút dọc theo đường dẫn đến một trong các lá được thay thế.

2. Các nút được thay thế là bản đồ. Nếu họ lớn hơn chỉ có ba phím, nó sẽ làm cho tinh thần để sử dụng assoc/assoc-in/update-in thay vì xây dựng bản đồ mới:

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

   Thần bản đồ mới nút sẽ có thể chia sẻ cấu trúc với các bản đồ cũ nút. (Một lần nữa, ở đây nó không có ý nghĩa bởi vì làm thế nào nhỏ các nút được, nhưng trong bối cảnh khác nhau này có thể làm cho một sự khác biệt rất lớn.)