Warum verwendet die Clojure-Reißverschluss-Implementierung verschiedene Typen und Datenstrukturen von Huets Reißverschluss?

Question

Ich vergleiche Huet's original paper mit Clojure's implementation und versuchen herauszufinden, warum die Änderungen vorgenommen wurden. Ich bin ein Clojure-Neuling, also wenn ich falsch liege bei meiner Interpretation des Clojure-Codes, korrigiere mich bitte.

In Huets Papier ist der Typ eines Pfades (in Ocaml) Top | Node of tree list * path * tree list;;. In Clojure gibt es zwei zusätzliche Felder, pnodes und changed?. Was ist der Zweck dieser Felder? Habe ich Recht zu glauben, dass l und r dem ersten und dritten Eintrag in Huets Typ entsprechen, und dass ppath der zweite ist?

Huets Reißverschluß verwendet verknüpfte Listen überall (ich spreche über den Loc-Typ selbst, nicht die Datenstruktur des Reißverschlusses), während an einigen Stellen, zum Beispiel l, die Clojure-Implementierung Vektoren verwendet. Warum die Veränderung und was bedeutet die zeitliche Komplexität der Clojure-Implementierung?

Answer 1

Zuerst ist Ihr Verständnis von l, r und ppath korrekt.

pnodes und changed? arbeiten zusammen als Optimierung: wenn Sie gehen up wenn changed? falsch ist dann knallen Sie den Knoten aus pnodes anstatt es aus dem aktuellen Knoten und dem linken und rechten Geschwister Listen wieder aufzubauen.

Wie für die Verwendung eines Vektors für l und eine Liste für r. Auch hier geht es um die Kosten für den Wiederaufbau eines Knotens. In Huets Papier gibt es (rev left) @ (t::right), das ist O (nleft), wo links die Größe von links ist. In Clojure haben wir (concat l (cons node r)), was O (1) [1] ist, weil l ein Vektor ist, der nicht umgekehrt werden muss (Vektoren in Clojure können effizient in jeder Richtung durchlaufen werden, sind aber nur an der rechten Seite anhängig).

[1] ok es ist O (1) nur zur Erstellungszeit: nleft conses wird träge zugewiesen, da die resultierende Sequenz durch weitere Berechnungen verbraucht wird.