Partial Persistent Linked Data Structure

個人的メモ

(注) このアルゴリズムは pointer machine based model の枠組みで解釈され、 本来的にはそれに沿った形で 純Lisp や ML 系の言語を用いて実装されるべきである. ちなみに pointer machine based model は同じ名のもとで複数の定義が存在するらしく、 なかでも Knuth's "linking automaton" model と呼ばれるものが一番制限がゆるくかつ他のモデルを用いて定数 factor の overhead で再現できるので理解には良いと思う. ただ界隈では SMM(Schönhage's storage modification machine) と呼ばれるものが主流らしい.
雑に言うと管理されるデータ(メモリ) の構造はノードとそれをつなぐ異なる label を持ったエッジからなり、 できる操作がノードを新しく作る, エッジを付け替える, エッジをたどる, 入力を受け取る, 出力を返すなどに制限されたモデルである(算術演算やランダムアクセスなどはできない).
モデルによってエッジが無向 / 有向の違いがあったり、出次数が制限されていたり,各ノードが定数個の value を持っていたりなどする(参考 "What is a "Pointer Machine"" [Ben-Amram 1995]).