Clojure 中的指针循环

Question

我正在编写一个解析 XML 的 clojure 程序。作为其中的一部分，我希望基于 clojure.xml/parse 函数在 XML 文档中创建节点树。但是我希望树是双向的 - 也就是说，每个节点都有一个子节点列表和一个指向其父节点的指针。只有一个问题：所有数据都是不可变的，因此我无法在不更改子项的情况下“添加”指向父项的指针，从而使父项的指针毫无用处。

我找到了这个答案： 如何在 Clojure 中创建循环（且不可变）数据结构而不需要额外的间接？

建议的解决方案似乎是创建一个单独的索引映射，它引用内部的对象。对于一个更糟糕的解决方案来说，这似乎是一项巨大的工作量。我对树在构造过程中可变没有问题，但我不知道如何做到这一点。 clojure 中真的没有办法获取循环指针吗？

谢谢！

Answer 1

从逻辑上讲，不可能使纯不可变结构成为循环结构，因为通过添加父指针或子指针将会改变结构。

有一个可行的技巧，但我不确定我是否会推荐它：您可以将原子放入 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 样式位置的内容。

Answer 2

您是否考虑过使用拉链？

拉链的设计目的是为了有效地处理树状结构。它包括基本操作，例如查看 子项 和在节点的 父 节点，同时还允许<一href="http://clojure.github.com/clojure/clojure.zip-api.html#clojure.zip/next" rel="nofollow">轻松迭代结构。

拉链是相当通用的，并且包含的​​功能已经允许从 XML 创建它们。 上的示例其他库页面提供了如何使用它们的良好初步图片。

对于 XML 拉链，您需要使用它

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

来创建初始结构。完成后，只需调用 root 即可获取最终结构。

Answer 3

像这样的事情是可行的：

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