Почему реализация Clojure zipper использует различные типы и структуры данных из застежки-молнии Huet?

Question

Я сравниваю Huet's original paper с Clojure's implementation и пытаюсь выяснить, почему были сделаны изменения. Я новичок в Clojure, поэтому, если я ошибаюсь в своей интерпретации кода Clojure, пожалуйста, поправьте меня.

В бумаге Уэта тип пути (в Окамле) Top | Node of tree list * path * tree list;;. В Clojure есть два дополнительных поля: pnodes и changed?. Какова цель этих полей? Правильно ли я полагаю, что l и r соответствуют первой и третьей записям типа Huet и что ppath является вторым?

Застежка-молния Huet использует связанные списки во всем (обратите внимание, что речь идет только о типе Loc, а не о структуре данных, на которой работает молния), тогда как в некоторых местах, например l, реализация Clojure использует векторы. Почему изменение, и каково значение для сложности выполнения Clojure?

Answer 1

Во-первых, ваше понимание l, r и ppath Правильно.

pnodes и changed? работают вместе как оптимизация: когда вы идете up если changed? ложно, то вы поп узел из pnodes, а не восстанавливать его из текущего узла и левого и правого списка братьев и сестер.

Что касается использования вектора для l и списка для r. Опять же, речь идет о стоимости восстановления узла. В бумаге Уэта есть (rev left) @ (t::right), который является O (nleft), где nleft - размер слева. В Clojure мы имеем (concat l (cons node r)), который является O (1) [1], потому что l, являющийся вектором, не нуждается в обратном (векторы в Clojure могут быть эффективно пройдены в любом направлении, но могут быть добавлены только справа).

[1] ОК это O (1) только во время создания: nleft conses будет лениво распределено, так как результирующая последовательность будет потребляться дальнейшим вычислением.