cer*_*wen 7 algorithm clojure zipper
我正在将Huet的原始论文与Clojure的实现进行比较,并试图找出改变的原因.我是Clojure的新手,所以如果我对Clojure代码的解释错了,请纠正我.
在Huet的论文中,路径的类型是(在Ocaml中)Top | Node of tree list * path * tree list;;.在Clojure中,还有两个字段,pnodes和changed?.这些领域的目的是什么？我是否正确地认为l并且r对应于Huet类型中的第一个和第三个条目,那ppath是第二个？
Huet的拉链始终使用链接列表(注意我说的是Loc类型本身,而不是拉链操作的数据结构),而在某些地方,例如l,Clojure实现使用向量.为什么要改变,以及Clojure实现的时间复杂性有何影响？
首先,您的理解l,r并且ppath是正确的.
pnodes并changed?作为优化一起工作:当你去的时候,up如果changed?是假,那么你从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将被懒惰分配,因为结果序列被进一步计算消耗.