差分リストその 1

番外編です♪
Prolog のイディオム．．．なのかなぁ？
まぁ，そんなようなものに差分リストというものがあります．
これはなんだろ？ C でいうところのポインタみたいな存在なのかな？分かってる人には普通というか当たり前のものかもしれないけれど，分からない人にはさっぱり，みたいな雰囲気．
その差分リストが写経本以外に教科書として読んでいる「Prolog への入門 (isbn:476490165X)」に，ついに出てきました．わくわく．
が，しかし．．．
説明少なすぎ！！ 2 ページくらいしかないよ？原書第三版もあまり違いはない感じ．
そんなに簡単なのか？

たしかに差分リスト自体はとても簡単．
差分リストというのは，リストを二つのリストの差分で表現しようというものです．
たとえば

[a, b, c]

というリストは，次のような差分リストと等価です．

[a, b, c] - []
[a, b, c, d] - [d]
[a, b, c, d, e] - [d, e]

どれも左のリストから右のリスト (の要素) を除くと [a, b, c] になります．
このように，あるリストを表現するのに二つのリストのペアを使うのが差分リスト．
ただし，右のリストは左のリストの末尾と一致しなければなりません．[a, b, c] - [b] みたいなのは差分リストではないということです．

この差分リスト，変数を使うと次のように書くことが出来るそうな．

[a, b, c | Z] - Z

これにより，Z が空リストだろうが [d] だろうが [d, e] だろうが，差分リスト全体としては [a, b, c] を表現することになります．
まぁ，いわれてみれば当たり前な感じ．

差分リスト自体の説明はこんな程度．簡単♪
・・・
なのですが，これだけだと「だからどうした」という気がしないでもありません．
なんで差分リストが必要なの？回りくどいだけじゃん？？
と，しばし思っちゃいましたよ．
どうやらですね，差分リストだなんて奇天烈なものがある理由は「効率」のためらしいですぜ，だんな．

例えば N を与えられると，1 から N までの整数を要素とするリストを返す seq/2 という述語を考えてみませう．

2 ?- seq(10, L).

L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

Yes

みたいな．

まずは普通に考えてみます．
1 から N までのリストって事は，1 から N - 1 までのリストの最後に N をくっつければいいって考えるのが Prolog 流な気のせいが．
そんなわけで (どんなわけで？)，

seq1(0, []) :-
	!.
seq1(N, L) :-
	M is N - 1,
	seq1(M, L2),
	conc(L2, [N], L).

という感じになります．最後は conc/3 の代わりにこの前写経した insert_last/3 を使ってもいいのですが，結局は同じなのでこちらで．
これはこれで分かりやすくていいのですが，N が大きくなってくると極端に効率が悪くなります．
というのも，conc/3 は第一引数で渡したリストの要素数分だけ再帰するため，リストの連結は O(N) なんですよね．
なので，N がでかくなってくるととってもいや〜んな気分．
実際，N を 1000 程度にすると目に見えてもっさりと答えを返すようになります．10000 だと 20 秒くらい返ってきません．．．

そこで効率を改善するために，リストの末尾ではなく先頭に要素を追加するように変更します．

seq2(N, L) :-
	seq2(N, 1, L).
seq2(N, N, [N]) :-
	!.
seq2(N, M, [M|L]) :-
	M2 is M + 1,
	seq2(N, M2, L).

下請けの述語 seq2/3 を用意して，N からカウントダウンする代わりに 1 から N までカウントアップしていきます．
この場合，リストの連結は [M|L] なのでそれ自体は O(1) のはず (述語全体での連結の回数は O(N) ですが，それは気にしない気にしない) なので，十分に効率的．N が 10000 でも 100000 でも全然平気，一瞬で返ってきます♪

しかし．
問題によってはこんな風に置き換えるとか出来ない場合もあるかもしれません．
そこで差分リストの登場です．たぶん．
さっそく，seq1/2 を差分リストを使うように書き換えてみます．
こうなりました．じゃーん．

seq3(N, L) :-
	seq3(N, L, []).
seq3(0, Z, Z) :-
	!.
seq3(N, L, Z) :-
	M is N - 1,
	seq3(M, L, [N|Z]).

下請けの述語 seq3/3 を使っていますが，やり方自体は seq1/2 とほとんど同じです．
まず，

seq3(0, Z, Z) :-
	!.

は限りなく

seq1(0, []) :-
	!.

と同じ．なんたって，同じリスト二つの差分 (Z - Z) は空リストに決まっているのだ．
そして

seq3(N, L, Z) :-
	M is N - 1,
	seq3(M, L, [N|Z]).

は限りなく

seq1(N, L) :-
	M is N - 1,
	seq1(M, L2),
	conc(L2, [N], L).

と同じ．ただし，再帰呼び出し後にリストの末尾に要素を追加するのではなく，再帰呼び出し前に差分リストの差分の方の先頭に要素を追加しています．
なぜこれが同等になるのか，差分リストに馴染んでいない頭にはとても奇妙な感じがします．

順を追って考えましょう．例えば

3 ?- seq3(3, L).

なんてやった場合．最終的に [1, 2, 3] というリストを求めたいわけですが，まずは

seq3(N, L) :-
	seq3(N, L, []).

が呼ばれます．この時点 (コンテキスト 1) で具体化されている変数は

N = 3

です．
そして seq3/3 を呼び出します．具体的には

	seq3(3, L, []).

です．
呼び出された seq3/3 (コンテキスト 2) では次のように変数が具体化されます．

N' = 3
Z' = []
M' = 2

です．
ここで seq3/3 の再帰呼び出しが行われます．具体的には，

	seq3(2, L, [3|[]]).

となります．
再帰呼び出しされた seq3/3 (コンテキスト 3)では次のように変数が具体化されます．

N'' = 2
Z'' = [3]
M'' = 1

さらに seq3/3 の再帰呼び出しが行われます．具体的には

	seq3(1, L, [2|[3]]).

です．
再帰呼び出しされた seq3/3 (コンテキスト 4) では次のように変数が具体化されます．

N''' = 1
Z''' = [2, 3]
M''' = 0

さらにさらに seq3/3 の再帰呼び出しが行われます．具体的には

	seq3(0, L, [1|[2, 3]]).

です．
ここで第 1 引数が 0 なので，seq3/3 の最初の節が選択されます．

seq3(0, Z, Z) :-
	!.

再帰呼び出しされた seq3/3 (コンテキスト 5) では次のように変数が具体化されます．

Z'''' = [1, 2, 3]

ここで最終的に欲しいリストができあがっていることに注意．差分リスト的には [1, 2, 3] - [1, 2, 3] で空リストなんですが．ここポイントですね．
この呼び出しが戻ると，コンテキスト 4 で次の変数が具体化されます．

L''' = [1, 2, 3]

このコンテキスト 4 では Z''' = [2, 3] なので，差分リスト的には [1] です．
さらに呼び出しが戻ってコンテキスト 3 で次の変数が具体化されます．

L'' = [1, 2, 3]

このコンテキスト 3 では Z'' = [3] なので，差分リスト的には [1, 2] です．
さらに呼び出しが戻ってコンテキスト 2 で次の変数が具体化されます．

L' = [1, 2, 3]

このコンテキスト 1 では Z' = [] なので，差分リスト的には [1, 2, 3] です．
そして最後に seq3/2 に呼び出しが戻ってコンテキスト 1 で次の変数が具体化されます．

L = [1, 2, 3]

これが求めていた解です．
なんか騙されている感じがしないでもないですが，差分リストを見ると seq1/2 と同じ動きをしていることになります．
なのですが，リストの連結そのものは [N|Z] なので O(1) のはず．
おかげで，N が 10000 でも 100000 でも全然平気，これまた一瞬で返ってきます♪

ようするに，

[X|Z] - Z

という差分リストは，[X] というリストと等価なのだけど，リストを辿ることなく後ろにリストを追加するための変数 Z をあらかじめ仕込んであるのがポイントなのではないかと．たぶん．
と，日記にまとめると簡単に見えるけど，ここまでたどり着くのは結構難儀しました．
差分リストを無意識的に使えるようになるには相当地道に素振りを続けないといけない感じ．Prologer への道は遠いぜ．

差分リストはもっと奥が深いようで，二つの差分リストを連結するというのが主な使い方のようです．
でもでも，差分リスト二つ使うのを考えるのが辛かったので，まずは一つで考えられる方へ逃げてしまいました．心より恥じる．
差分リストの連結についてもそれなりに理解できればまた後日．