algorithm - 为什么 Clojure 拉链实现使用与 Huet 的拉链不同的类型和数据结构？

Question

我正在将Huet 的原始论文与Clojure 的实现进行比较，并试图找出做出这些更改的原因。我是 Clojure 新手，所以如果我对 Clojure 代码的解释有误，请纠正我。

在 Huet 的论文中，路径的类型是 (in Ocaml) Top | Node of tree list * path * tree list;;。在 Clojure 中，有两个附加字段，pnodes和changed?. 这些领域的目的是什么？我是否相信l并r对应于 Huet 类型中的第一个和第三个条目，那ppath是第二个？

Huet 的 zipper 始终使用链表（注意我说的是 Loc 类型本身，而不是 zipper 操作的数据结构），而在某些地方，例如l，Clojure 实现使用向量。为什么要进行更改，以及对 Clojure 实现的时间复杂度有何影响？

Answer 1

首先，您对 , 的理解l是r正确ppath的。

pnodes并changed?作为优化一起工作：当你 go upifchanged?为 false 时，你从 pnodes 中弹出节点，而不是从当前节点和左右兄弟列表中重建它。

至于向量的使用l和列表的使用r。同样是关于重建节点的成本。在 Huet 的论文中，(rev left) @ (t::right)这是 O(nleft)，其中 nleft 是左侧的大小。在 Clojure 中，我们有(concat l (cons node r))O(1) [1]，因为l作为向量不需要反转（Clojure 中的向量可以在任何方向上有效地遍历，但只能在右侧追加）。

[1] 好的，仅在创建时为 O(1)：nleft conses 将被延迟分配，因为结果序列被进一步计算消耗。