Huet の元の論文とClojure の実装を比較し、なぜ変更が加えられたのかを解明しようとしています。私は Clojure の初心者なので、Clojure コードの解釈が間違っている場合は、訂正してください。
Huet の論文では、パスのタイプは (in Ocaml)Top | Node of tree list * path * tree list;;です。Clojure には、2 つの追加フィールドpnodesとchanged?. これらのフィールドの目的は何ですか? Huet のタイプの 1 番目と 3 番目のエントリに対応し、それが 2 番目であるlと信じるのは正しいですか?rppath
Huet のジッパーは全体でリンクされたリストを使用します (ジッパーが操作するデータ構造ではなく、Loc 型自体について話していることに注意してください) 一方でl、Clojure の実装ではベクトルを使用する場所もあります。変更の理由と、Clojure 実装の時間の複雑さへの影響は何ですか?
まず、 と の理解lはr正しいppathです。
pnodeschanged?最適化として連携します。if upis changed?false の場合、現在のノードと左右の兄弟リストからノードを再構築するのではなく、pnodes からノードをポップします。
のベクトルlと のリストの使用についてr。繰り返しますが、ノードを再構築するコストについてです。Huet の論文に(rev left) @ (t::right)は、nleft が left のサイズである O(nleft) があります。Clojure では、(concat l (cons node r))これは O(1) [1] です。これlは、ベクトルであることを反転する必要がないためです (Clojure のベクトルは、効率的に任意の方向にトラバースできますが、右側にのみ追加できます)。
[1] わかりました、作成時のみ O(1) です: 結果のシーケンスがさらなる計算によって消費されるため、nleft conses は遅延して割り当てられます。