为什么 Clojure 拉链实现使用与 Huet 拉链不同的类型和数据结构？
Why does the Clojure zipper implementation use different types and data structures from Huet's zipper?
我正在比较 Huet's original paper with Clojure's implementation 并试图找出进行更改的原因。我是Clojure新手，所以如果我对Clojure代码的理解有误，请指正。
在 Huet 的论文中，路径的类型是（在 Ocaml 中）Top | Node of tree list * path * tree list;;。在 Clojure 中，有两个附加字段，pnodes 和 changed?。这些字段的目的是什么？我是否认为 l 和 r 对应于 Huet 类型中的第一个和第三个条目，而 ppath 是第二个？
Huet 的 zipper 始终使用链表（注意我说的是 Loc 类型本身，而不是 zipper 正在运行的数据结构），而在某些地方，例如 l，Clojure 实现使用载体。为什么要更改，对 Clojure 实现的时间复杂度有何影响？
首先，您对l、r和ppath的理解是正确的。
pnodes 和 changed? 作为优化一起工作：当你去 up 如果 changed? 是 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 将被延迟分配，因为结果序列将被进一步计算消耗。
我正在比较 Huet's original paper with Clojure's implementation 并试图找出进行更改的原因。我是Clojure新手，所以如果我对Clojure代码的理解有误，请指正。
在 Huet 的论文中，路径的类型是（在 Ocaml 中）Top | Node of tree list * path * tree list;;。在 Clojure 中，有两个附加字段，pnodes 和 changed?。这些字段的目的是什么？我是否认为 l 和 r 对应于 Huet 类型中的第一个和第三个条目，而 ppath 是第二个？
Huet 的 zipper 始终使用链表（注意我说的是 Loc 类型本身，而不是 zipper 正在运行的数据结构），而在某些地方，例如 l，Clojure 实现使用载体。为什么要更改，对 Clojure 实现的时间复杂度有何影响？
首先，您对l、r和ppath的理解是正确的。
pnodes 和 changed? 作为优化一起工作：当你去 up 如果 changed? 是 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 将被延迟分配，因为结果序列将被进一步计算消耗。