8
votes

Cycles de pointeur dans le clojure

J'écris un programme de clojure qui analyse XML. Dans le cadre de cela, je souhaite créer un arbre des nœuds dans le document XML, en fonction de la fonction CLOJURE.XML / Payse. Cependant, j'aimerais que l'arbre soit bi-directionnel - c'est-à-dire que chaque nœud a une liste d'enfants et un pointeur à son parent. Il n'y a qu'un problème: toutes les données sont immuables, et donc je ne peux donc pas «ajouter» un pointeur au parent sans changer l'enfant, rendant ainsi le pointeur du parent inutile.

J'ai trouvé cette réponse: Comment créer des structures de données cycliques (et immuables) dans le clojure sans indirection supplémentaire?

La solution suggérée Il semble créer une carte d'index distincte, qui fait référence aux objets à l'intérieur. Cela semble être une énorme quantité de travail pour une solution bien pire. Je n'aurais aucun problème pour que l'arbre soit mutable pendant la construction, mais je ne peux pas comprendre comment cela peut-il être fait. N'a-t-il vraiment aucun moyen d'obtenir un pointeur cyclique à Clojure?

Merci!

pointers data-structures clojure immutability

1 commentaires

La manière appropriée de la manipulation de XML dans un paramètre PURE FP est d'utiliser des fermetures à glissière. clojuredocs.org/clojure_core/clojure.zip/xml-zip

3 Réponses :

5
votes

Il est logiquement impossible de faire des structures immuables pures cycliques, car en ajoutant un pointeur parent ou enfant, vous allez muter la structure.

Il y a un piratage qui fonctionne si je ne suis pas sûr de le recommander: vous le recommandez Peut mettre des atomes à l'intérieur des structures de données de clojure, puis les muter pour apporter les liens nécessaires. E.g. P>

(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

Cela fera de la pile de votre réplique si vous essayez d'en imprimer l'une d'entre elles, car la redevance ne s'attend pas à des structures de données cycliques. Li>
Il est mutable, vous perdez donc toutes les prestations de maintenabilité et de concurrence des structures de données immuables (qui est l'une des plus belles choses sur le clojure!) Li>
Vous devrez prendre une copie complète d'un nœud si vous souhaitez le dupliquer (par exemple, construire un nouveau document XML), puisqu'il n'est plus une valeur immuable. LI>
Déroferience Tous les atomes peuvent devenir désordonnés lorsque vous naviguez sur la structure. LI>
Vous allez confondre des personnes qui sont habituées à la clojure idiomatique. LI> ul>
Donc, il est possible si vous voulez vraiment le faire ......... si je pense personnellement que vous êtes encore beaucoup mieux à long terme si vous faites votre représentation de votre document correctement immuable . Vous pouvez peut-être utiliser quelque chose de plus comme des emplacements de style XPath dans le document si vous souhaitez naviguer dans la structure. P> P>

4 commentaires

Merci - cela semble être ce que je voulais. Bien que je ne sois pas vraiment satisfait de la façon dont la clojure gère cela ...

Clojure est une jolie langue «opinionnée» et vous êtes vivement encouragé à descendre de la route immuable. Mieux vaut l'embrasser que de la combattre si vous voulez profiter des avantages complètes de Clojure, je pense que ..... et à long terme, je crois que cette approche nous aidera à faire de meilleurs logiciels.

"Il est logiquement impossible de faire des structures immuables pures cycliques" - dans le clojure, peut-être. À Haskell, cela est possible, du moins dans une mesure limitée. Mais +1 pour le reste de la réponse.

Hey @Mikera, quel serait le problème de l'utilisation (transitoire []) pour les deux: enfants et: parent tout en construisant le graphique et avant de le renvoyer, il suffit de tout définir (persistant)? En plus de ne pas pouvoir imprimer une telle structure, cela ne devrait pas être un problème, non?

0
votes

Quelque chose comme ça pourrait fonctionner:

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

0 commentaires

2
votes

Avez-vous envisagé d'utiliser Zippers ?

Les fermetures à glissière sont conçues pour permettre de travailler efficacement avec des arbres comme des structures. Il comprend des opérations de base telles que regarder enfants et au Parent d'un nœud tout en permettant Itération facilement à travers la structure. P >

Les fermetures à glissière sont des fonctions assez génériques et incluses permettent déjà de les créer de XML. Un exemple sur le Les autres bibliothèques Page propose une bonne image initiale de la façon de travailler avec eux. P>

Pour une fermeture à glissière XML, vous voudrez utiliser P>

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

0 commentaires