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

Question

I am comparing the original Huet paper with Clojure and trying to find out why the changes were made. I am new to Clojure, so if I am mistaken in my interpretation of Clojure code, please correct me.

In Huet paper type of path (in Ocaml) Top | Node of tree list * path * tree list;; Top | Node of tree list * path * tree list;; . Clojure has two additional fields: pnodes and changed? . What is the purpose of these fields? Do I correctly assume that l and r correspond to the first and third records of type Huet and that ppath is the second?

Huet zipper uses linked lists (note that I'm talking about the Loc type itself, not about the data structure that the zipper works), and in some places, like l , the Clojure implementation uses vectors. Why change and what is meant for the complexity of running Clojure?

Answer 1

Firstly, your understanding of l , r and ppath correct.

pnodes and changed? work together as optimization: when you go up , if changed? is false, you are pushing the node out of pnodes, and not rebuilding it from the current node and to the left and the lists of right siblings.

Regarding the use of the vector for l and the list for r . Once again about the cost of recovering a node. Uete's paper has (rev left) @ (t::right) , which is O (nleft), where nleft is the size on the left. In Clojure we have (concat l (cons node r)) , which is O (1) [1], because l , which is a vector, does not need the opposite (vectors in Clojure can be efficiently traversed in any direction, but can be added only on the right).

[1] ok this is O (1) only at the time of creation: nleft conses will be lazily allocated as the resulting sequence is consumed by further calculation.