Указатель циклов в clojure - PullRequest
Новая
       35

Указатель циклов в clojure

8 голосов
/ 14 февраля 2012

Я пишу программу clojure, которая анализирует XML. В качестве части этого я хочу создать дерево узлов в документе XML на основе функции clojure.xml / parse. Однако я бы хотел, чтобы дерево было двунаправленным, то есть каждый узел имел список дочерних элементов и указатель на своего родителя. Есть только одна проблема: все данные неизменны, и поэтому я не могу «добавить» указатель на родителя без изменения дочернего элемента, что делает бесполезным указатель родителя.

Я нашел ответ: Как можно создать циклические (и неизменные) структуры данных в Clojure без лишних косвенных указаний?

Предполагается, что решение заключается в создании отдельной индексной карты, которая ссылается на объекты внутри. Это похоже на огромный объем работы для гораздо худшего решения. У меня не было бы проблем с изменчивостью дерева во время строительства, однако я не могу понять, как это можно сделать. Неужели нет способа получить циклический указатель в clojure?

Спасибо!

Ответы [ 3 ]

5 голосов
/ 14 февраля 2012

Логически невозможно сделать циклически чистые неизменяемые структуры, поскольку при добавлении родительского или дочернего указателя вы изменили бы структуру.

Существует способ, который работает, хотя я не уверен, что рекомендуюэто: вы можете поместить атомы в структуры данных Clojure, а затем изменить их, чтобы получить необходимые ссылки.например, 

(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

Это неприятно во всех отношениях:

  • Это приведет к переполнению стека в вашем REPL, если вы попытаетесь распечатать один из них, потому что REPL не являетсяожидая циклические структуры данных.
  • Это изменчиво, поэтому вы теряете все преимущества удобства поддержки и параллелизма неизменяемых структур данных (что является одной из самых приятных вещей в Clojure!)
  • Вам понадобитсявзять полную копию узла, если вы хотите продублировать его (например, создать новый документ XML), так как это больше не является неизменным значением.
  • Разыменование всех атомов может стать грязным при навигацииструктура.
  • Вы будете путать людей, которые привыкли к идиоматической Clojure.

Итак, это возможно, если вы действительно хотите это сделать ........хотя лично я думаю, что в конечном итоге вам будет намного лучше, если вы сделаете свое представление документа должным образом неизменным.Возможно, вы могли бы использовать что-то более похожее на расположение в стиле XPath в документе, если вы хотите перемещаться по структуре.

2 голосов
/ 15 февраля 2012

Рассматривали ли вы использование застежек-молний ?

Застежки-молнии предназначены для эффективной работы с древовидными структурами.Он включает в себя базовые операции, такие как просмотр потомков и родителя узла, а также позволяет легко перебирать через структуру.

Молниидовольно общие и включенные функции уже позволяют создавать их из XML.Пример на странице Другие библиотеки дает хорошее начальное представление о том, как с ними работать.

Для XML-молнии вам понадобится 

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

создать исходную структуру.Когда вы закончите, просто позвоните root, чтобы получить конечную структуру.

0 голосов
/ 14 февраля 2012

Примерно так может работать: 

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

Сделайте протокол не частью общедоступного API и никогда не трогайте изменяемое поле после создания, и у вас в основном будет неизменное дерево. Однако модифицировать указанное дерево после постройки будет сложно. YMMV.

...