Ciclos de puntero en clojure

Question

Estoy escribiendo un programa clojure que analiza XML. Como parte de esto, deseo crear un árbol de nodos en el documento XML, basado en la función clojure.xml/parse. Sin embargo, me gustaría que el árbol sea bidireccional, es decir, cada nodo tiene una lista de elementos secundarios y un puntero a su elemento principal. Solo hay un problema: todos los datos son inmutables, por lo que no puedo 'agregar' un puntero al padre sin cambiar el niño, lo que hace que el puntero del padre sea inútil.

He encontrado esta respuesta: How can one create cyclic (and immutable) data structures in Clojure without extra indirection?

La solución propuesta no parece ser la creación de un mapa índice separado, que se refiere a los objetos en el interior. Esto parece una gran cantidad de trabajo para una solución mucho peor. No tengo ningún problema para que el árbol sea mutable durante la construcción, sin embargo, no puedo entender cómo se puede hacer. ¿Realmente no hay forma de obtener un puntero cíclico en clojure?

Gracias!

Answer 1

Es lógicamente imposible hacer que las estructuras inmutables sean cíclicas, ya que al agregar un puntero principal o secundario, estaría mutando la estructura.

Hay un truco que funciona aunque no estoy seguro de que lo recomiende: puedes poner átomos dentro de estructuras de datos Clojure y luego mutarlos para hacer los enlaces necesarios. p.ej.

(def parent {:id 1 :children (atom nil) :parent (atom nil)}) 

(def child {:id 2 :children (atom nil) :parent (atom nil)}) 

(swap! (:children parent) conj child) 
(reset! (:parent child) parent) 

;; test it works 
(:id @(:parent child)) 
=> 1 

Esto es desagradable en todo tipo de formas:

• Se hará que su REPL a desbordamiento de pila si se intenta imprimir y uno de ellos ya que el REPL no espera estructuras de datos cíclicos.
• Es mutable, por lo que pierde todos los beneficios de mantenibilidad y simultaneidad de las estructuras de datos inmutables (que es una de las mejores cosas de Clojure!)
• Tendrá que tomar una copia completa de un nodo si lo desea para duplicarlo (por ejemplo, construir un nuevo documento XML), ya que ya no es un valor inmutable.
• La desreferenciación de todos los átomos puede desordenarse a medida que navega por la estructura.
• Confundirá a las personas que están acostumbradas a la idiomática Clojure.

Por lo tanto, es posible si realmente quieres hacerlo ......... aunque personalmente creo que todavía estás mucho mejor a largo plazo si haces que tu representación del documento sea inmutable. Tal vez pueda usar algo más como ubicaciones de estilo XPath en el documento si desea navegar por la estructura.

Answer 2

Algo como esto podría funcionar:

(defprotocol TreeItemConstruction 
    (add-child [this child])) 

(deftype MyTree 
    [parent ^:unsynchronized-mutable children] 
    TreeItemConstruction 
    (add-child [this child] 
    (locking this 
     (set! children (conj children child))))) 

(defn my-tree 
    [parent] 
    (->MyTree parent [])) 

(def root (my-tree nil)) 
(def children (repeatedly 5 #(my-tree root))) 
(doseq [child children] (add-child root child)) 

que el Protocolo no forma parte de la API pública y nunca toque el campo mutable después de la construcción y que, básicamente, tener un árbol inmutable. Sin embargo, modificar dicho árbol después de la construcción será difícil. YMMV.

Answer 3

¿Ha considerado usar zippers?

Las cremalleras están diseñadas para trabajar eficazmente con estructuras similares a árboles. Incluye operaciones básicas como mirar children y en el parent de un nodo, mientras que también permite easily iterating a través de la estructura.

Las cremalleras son bastante genéricas y las funciones incluidas ya permiten crearlas desde XML. Un ejemplo en la página Other Libraries ofrece una buena imagen inicial de cómo trabajar con ellos.

Para una cremallera XML, tendrá que utilizar

(clojure.zip/xml-zip (clojure.xml/parse file)) 

para crear la estructura inicial. Cuando haya terminado, simplemente llame al root para obtener la estructura final.