差分リスト(difference list)の解説をします。
まず初めにPrologの通常のリストの構造の解説から。
Prologでは例えば[a,b,c,d]で表されるリストは、内部的には以下の形の木構造で表されています。
左の要素に値が入っていて、右の要素には続く要素が入るリストが入っています。黄色のところ見るとわかるように、最後の要素が[]の空リストになっています。
ここで、このリストそのものの後ろに何か新しい要素やリストを追加する方法を考えてみます。
結論から言うと、Prologでは自由変数に値を設定すると固定化されバックトラック以外の方法では変更できないため、図の黄色の空リストが入っている変数の値を変更することが出来ず、「できない」 のです。
appendという術語を用いて、append([a,b],[c,d],NewList). のように記述するとNewListには[a,b,c,d]というリストが入りますが、前の方のリスト[a,b]はそのまま使用できず全要素コピーされています。
述語appendの定義：
append([], L, L).
append([H|T], L, [H|R]) :-
append(T, L, R).
長いリストの後ろにリストを追加するときなどは、元のリストは全要素コピーされ、結構な無駄（リスト終わりまでたどり着く時間とコピーで使用されるメモリ資源）となります。
ここで登場するのが差分リストです。
差分リストは、上記で述べた通常のリストの黄色い部分を「空リストではなく、値を決定しない自由変数のままにした」リストのことを言います。
当たり前ですが、黄色の変数に空リストを設定すると、通常のPrologのリストと全く同じになります（→差分リストを通常のリストに変換するのは簡単）
青い部分を差分リストの頭部(Head)、黄色の部分を差分リストの尾部(Tail)と言います。
差分リストの表現方法はいくつかあるようですが、自分は[Head,Tail]という表記を使用しています。
最終要素の自由変数をTailとして表に引っ張り出してきます。
無理やり図で表すとこんな感じです（便宜的に矢印つけました）
ちょっとわかりずらいので、ドット演算子をはしょって以下のように図示してみます。
この表現にすると、リストの後ろに新たなリストを追加するという操作が、「尾部の自由変数に追加したいリストを代入してやる」操作で行えることがわかります。これはappendによる1つ目のリストの全要素コピーが行われないため、高速です。
注意点としては、「新しく追加するリストの最終要素も自由変数である必要がある」「その自由変数が結合後のリストの新たな尾部となる」ということです。以下で説明します。
差分リストの結合は以下のような述語を用いて行います。
append_difference_list([List1Head, List1Tail], [List2Head, List2Tail], [List1Head, List2Tail]):-
List1Tail=List2Head.
仮に
List1:[a,b,c,d,自由変数1]
List2:[e,f,g,h,自由変数2]
とします（ちょっと表現変ですがニュアンスで）
①一番目と二番目の引数として以下のようにマッチングされます。
②List1Tail=List2Head. の記述により List1の尾部(自由変数1)にList2が設定され、List1が以下のようなリストになります。
③3番目の引数として結合した差分リストを返します。
実際は
List1Tail=List2Head.の記述は述語を以下のような記述にすることにより省略できます。説明のためわざとこのような記述にしました。
append_difference_list([List1Head, List2Head], [List2Head, List2Tail], [List1Head, List2Tail]).
差分リストの具体的な使われ方なのですが、例えばSWI-Prologのfindall/4があります。
これは通常のfindall/3で返ってくるリストを差分リストとして返すもので、リストの尾部が4番目の引数として返ってきます。
私は以前スライドパズルのラッシュアワー(RUSH HOUR)のソルバーを作成したときにこのfindall/4を使用しました。
ソースコード
ドキュメントおよび実行結果
詳細の解説は行いませんが、このソースコードでは幅優先探索というアルゴリズムを用いていて、ある局面から発生しうるすべての局面を生成するのにfindall/4を使用しています。結果を差分リストで取得することにより、幅優先探索キューの尾部にfindall/4で返された差分リストをそのまま追加することにより処理を効率化しています。
差分リストが使用されている他の例は構文解析などで使用される DCG(Definite clause grammar)などがあります。SWI-PrologでDCGで何らかの述語（トークン？）を記述したのちlistingなどで定義を見ると、すべて差分リストの引数が追加された同名のprolog述語に変換されているのがわかります。