如何在Clojure数据结构中“标记”一个节点？

Question

6

我有一个Clojure数据结构，称为dom，它是一个无限深度的向量和映射的树；

其中有一个特定的节点，我们称之为焦点节点focus，它被视为路径进入树：一系列键的序列，比如你可以提供给get-in

我将在一个函数中决定聚焦节点，并希望以某种方式表示聚焦节点的选择，以便可以将其传递给另一个函数，而不会违反不可变性，并且不会与Clojure的持久数据结构发生冲突。

当我遍历树时，我想要特别对待focus节点：例如，如果我正在打印树，则可能希望以粗体方式打印focus节点。

如果我使用C或Java，我可以保存指向focus节点的指针/引用，然后在遍历树时与当前节点进行比较。我认为这不是正确的Clojure实现方式：它感觉很巧妙，并且我相信有一些方法可以利用Clojure的持久数据结构来实现它。

解决方案必须适用于Clojure和ClojureScript。

我能想到的选项是：

存储引用并进行比较。
将标记附加到相关节点上。
同时递归进入树和路径到达有标记的节点。
- 选项（1）不太好，如我所解释的。
- 选项（2）似乎最好，并且在使用持久数据结构时是轻松的。
- 选项（3）类似于选项（2），只是它组合了标记和遍历步骤。

我相信这是一个常见的问题。是否有标准的解决方案呢？

- Joe

我猜你可以使用元数据来实现第二个问题，但我不知道一般的解决方案。 - HMM

谢谢。我可以使用元数据，但可能不会这样做。问题比实现要广泛一些。 - Joe

重新阅读一遍从来不会有坏处，但我认为我提出的问题并不是基于主观看法的。完全有可能（而且我也不知道）有一种标准的惯用模式来解决这个问题。如果答案是否定的，那也是一个有效的答案。 - Joe

听起来像是函数镜头的一个使用案例。也许可以用Clojure.zip实现？ - omiel

2个回答

1

关于这类问题，可以查看Brandon Bloom的Dendrology talk，会有很好的概述。

我认为，将树形结构数据“标记”或更新起来更容易，这是他强烈建议始终将节点表示为嵌套映射而不是向量（或向量和映射的混合）的原因。基于由键向量描述的路径的标记就像这样简单：

 (update-in tree-data path assoc :is-focussed true)

你的原始数据结构保持不变，而通过 update-in 返回的新数据结构与原始数据结构在结构上共享所有内容，除了更新后的节点现在可以在遍历时轻松测试 :is-focussed 属性。

- Alex Stoddard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thumbnail · Accepted Answer

我建议您重新考虑@MerceloMorales的建议：使用元数据。您的节点对象应该有一个意外属性，不会影响其正常功能。这就是元数据的设计目的。它在ClojureScript中起作用。我能想到不使用元数据的唯一原因是节点值不是Clojure对象，而是例如数字。

在《Clojure Cookbook，2.22.保留键的多个值》中，Luke Vanderhart使用元数据解决类似的问题：将需要解释为集合而不是单个值的条目标记出来。

另一种方法可能是使用拉链遍历/修改节点树。拉链是基于元数据实现的。

我分享您对元数据的疑虑：将任何东西附加到数据上感觉很不舒服，就像感染了寄生虫一样。但是，它与任何其他对象一样是不可变的一部分。

建议使用拉链是幼稚的：标准的Clojure zipper 是为顺序容器层次结构设计的，而不是关联容器。