Compartir Estructural en Clojure

Question

No tengo claro sobre el intercambio estructural en Clojure. A continuación se muestra una función xconj tomada de la Alegría de Clojure (Gran libro por cierto).

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

Si uno define dos árboles t1 y t2 como se muestra a continuación.

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

Está claro que el subárbol izquierdo es compartida por t1 & t2

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

Pero si uno fuera a crear un nuevo t3 árbol, mediante la inserción de un nuevo valor '1' en el subárbol izquierdo t1, así:

(def t3 (xconj t1 1)) 

será este resultado en un nuevo árbol con todos los valores copiados y sin compartir estructural, o habrá algún tipo de estructura todavía ser compartida? ¿Qué sucede si la rama izquierda es más grande, digamos 2-> 3-> 4-> 5-> 6-> 7 (* raíz) y 1 se insertó en el subárbol izquierdo, entonces persistirá algún intercambio de estructura?

Answer 1

Los nodos en el camino hacia el lugar donde el nuevo valor se va a insertar será reemplazado, pero hay por lo menos dos cosas que uno debe darse cuenta de obtener toda la historia:

1. Sustitución de una el nodo no nil en el curso de una operación xconj conserva uno de sus subárboles y su valor; solo un subárbol se intercambia. (Si reemplaza los nodos a lo largo de la ruta "izquierda, izquierda, izquierda", el nodo en la posición "izquierda, izquierda, derecha" se va a compartir). Por lo tanto, se puede compartir mucha estructura incluso si todos los nodos a lo largo del el camino a una de las hojas es reemplazado.

2. Los nodos que se reemplazan son mapas. Si fueran más grande que sólo tres teclas, tendría sentido utilizar assoc/assoc-in/update-in en lugar de construir nuevos mapas:

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

   Que el nuevo mapa de nodos sería capaz de compartir estructura con el viejo mapa de nodos. (Una vez más, aquí no tiene sentido debido a cuán pequeños son los nodos, pero en diferentes contextos esto puede marcar una gran diferencia.)