Zipper on Prolog

Zipper (Wikipedia)
非破壊な構成を取る場合に、単方向リストだけで全てを賄う事は難しい。リスト中の任意な部分に着目したいし、またその部分を入れ替えたリストが必要になる場合も多い。Zipperはそういったニーズに応えるデータ構造である。或いは非常に資源の限られたハードウェアで巨大なデータを取り扱う場合、オンメモリなページとその前後への参照に対して編集操作をログとして処理する手段は、古くからある一種のZipperだと云えよう。後者は過去の記憶サイズによって非破壊な情報量に限度が伴うことになる。

PrologもLisp同様にList操作に優れている。パターンマッチの自由度が高い分、より強力だと云える。しかしListだけでは流石に不自由があるのでZipper（やそれの亜種）を用意することは多い。この時に差分リストを使っておくと、割と効率の良い実装となるだろう。

% zipper/2
zipper([[PreHead | Pre], PreTail]:Cursor:[[Next | Rest], RestTail],
       [[Cursor, PreHead | Pre], PreTail]:Next:[Rest, RestTail]).
% create_zipper/2
create_zipper([Head | Rest],
              [[ZPreTail], ZPreTail]:Head:[ZRest, ZRestTail]) :-
    append(Rest, ZRestTail, ZRest).

?- create_zipper([1,2,3,4,5], Z0), zipper(Z0, Z1), zipper(Z1, Z2), zipper(ZX, Z2).
Z0 = [[_G700], _G700]:1:[[2, 3, 4|_G712], _G712],
Z1 = [[1, _G700], _G700]:2:[[3, 4|_G712], _G712],
Z2 = [[2, 1, _G700], _G700]:3:[[4|_G712], _G712],
ZX = [[1, _G700], _G700]:2:[[3, 4|_G712], _G712].

?- create_zipper([1,2,3,4,5], Z0), zipper(Z0, Z1), zipper(Z1, P:C:R), zipper(Z, P:1:R).
..
Z = [[1, _G808], _G808]:2:[[1, 4, 5|_G820], _G820].

ちなみにこの実装だとZipper以上の機能が利用出来る。というのは、先行する差分リストの末尾である本来のリストの先頭に要素を加える事も、後続する差分リストの末尾である本来のリストの末尾に要素を加える事も可能だからである。つまり実を言えばこれは、Prologでの可変長リングバッファーの実装である。