差分リスト

Prologの基本的なデータ構造としてリストが利用出来る、という話は間違ってはいないけれども美味しいところを取りこぼしているような気がしてしまう。何故ならPrologの強みは、自由な表記がそのままデータ構造（Structure）として利用可能な点にあるからである。そしてこのStructureは単一化の対象となる。だからマクロのような事も、インタプリタのような事も簡単に出来るわけである。という事を考えていると、リストを世間一般的な形だけで考えているそのこと自体がもったいないのではないかと思えてくる。

Prologのリストは標準的な書き方以外でも扱える。それが差分リストである。一般的な書き方をしたリストは、先頭の要素から順序的に要素を取り出す必要がある、と同時にそれがリストというStructureの定義であった。ところでリスト同士であればその前後を接続したとしてもリストである事は想像に難くあるまい。逆に言えば、リストを途中で切断して分かれたものはどちらもリストであるということだ。この観点から定義したリストが差分リストである。

% List A = X - Y, List B = Y - Z
% => List A+B = X - Y + Y - Z = X - Z

% diff_append/3
diff_append([Xs, Ys], [Ys, Zs], [Xs, Zs]).

?- diff_append([[1, 2 | X], X], [[3 | Y], Y], Z ).
X = [3 | Y],
Z = [[1, 2, 3 | Y], Y].

あえて手続き的な解釈をすると、リスト末尾に未初期化領域への参照を確保しておくことで、リストの連結を参照先の初期化として意味づける、という事である。こうすることでリストの連結は非常に高速になる、と同時にリストの表示が自由変数混じりとなるデメリット（と考えるかどうかは状況次第だが）もある。

差分リストを用いてクイックソートを実装してみるとこんな具合になる。クイックソートの処理の大部分が分類した大小要素の連結であることを想像すれば、差分リストの意義は推察されよう。

% diff_qsort/2
diff_qsort(X, Y) :- diff_qsort(X, Y, []).
% diff_qsort/3
diff_qsort([], S, S).
diff_qsort([H | T], S1, S2) :-
    partition(H, T, Low, High),
    diff_qsort(Low, Low1, Low2),
    diff_qsort(High, High0, High2),
    High1 = [H | High0],
    diff_append([Low1, Low2], [High1 | High2], [S1, S2]).

% partition/4
partition(_H, [], [], []).
partition(H, [E | T], [E | Low], High) :-
    E < H, !, partition(H, T, Low, High).
partition(H, [E | T], Low, [E | High]) :-
    partition(H, T, Low, High).

?- diff_qsort([8, 4, 1, 5, 6, 9, 0, 3, 2], Sorted).
Sorted = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].