clojure - 如何在没有额外间接的情况下在 Clojure 中创建循环(和不可变)数据结构？

Question

我需要在 Clojure 中表示有向图。我想将图中的每个节点表示为一个对象(可能是一条记录)，其中包含一个名为 :edges 的字段。即可以从当前节点直接到达的节点的集合。希望这是不言而喻的，但我希望这些图表是不可变的。

只要我进行拓扑排序并“从叶子向上”构建每个图，我就可以使用这种方法构建有向无环图。

但是，这种方法不适用于循环图。我能想到的一种解决方法是对整个图形的所有边进行单独的集合(可能是 map 或矢量)。 :edges然后每个节点中的字段将具有进入图的边集合的键(或索引)。添加这种额外的间接级别是可行的，因为我可以在它们(将)引用的东西存在之前创建键(或索引)，但感觉就像是一个杂物。不仅每次要访问相邻节点时都需要进行额外的查找，而且还必须绕过全局边缘集合，感觉非常笨拙。

我听说有些 Lisps 可以创建循环列表，而无需借助变异函数。有没有办法在 Clojure 中创建不可变的循环数据结构？

Answer 1

您可以将每个节点包装在 ref 中，为其提供一个稳定的句柄来指向(并允许您修改可以从 nil 开始的引用)。然后就有可能以这种方式构建循环图。当然，这确实有“额外的”间接性。

我不认为这是一个很好的主意。您的第二个想法是更常见的实现。我们构建了类似的东西来保存 RDF 图，并且可以在不费力的情况下从核心数据结构和层索引构建它。