Why does the Clojure zipper implementation use different types and data structures from Huet's zipper?

Question

I'm comparing Huet's original paper with Clojure's implementation and trying to figure out why the changes were made. I'm a Clojure novice, so if I'm wrong on my interpretation of the Clojure code, please correct me.

In Huet's paper, the type of a path is (in Ocaml) Top | Node of tree list * path * tree list;;. In Clojure, there are two additional fields, pnodes and changed?. What's the purpose of these fields? Am I right in believing that l and r correspond to the first and third entries in Huet's type, and that ppath is the second?

Huet's zipper uses linked lists throughout (note I'm talking about the Loc type itself, not the data structure the zipper is operating), while in some places, for instance l, the Clojure implementation uses vectors. Why the change, and what's the implication for the Clojure implementation's time complexity?

Impearl

Answer 1

First, your understanding of l, r and ppath is correct.

pnodes and changed? work together as an optimization: when you go up if changed? is false then you pop the node from pnodes rather than rebuilding it from the current node and the left and right siblings lists.

As for the use of a vector for l and a list for r. Again it's about the cost of rebuilding a node. In Huet's paper there's (rev left) @ (t::right) which is O(nleft) where nleft is the size of left. In Clojure we have (concat l (cons node r)) which is O(1) [1] because l being a vector does not need to be reversed (vectors in Clojure can be efficiently traversed in any direction but are appendable only at the right).

[1] ok it's O(1) only at creation time: nleft conses will be lazily allocated as the resulting sequence is consumed by further computation.

Subconscious