概要
今回は差分リストを調べたのでまとめてみました。
Prologではリストの要素を直接変更することができないので、差分リストのような手法を利用せずにリスト操作を実装すると、毎回リストがコピーされてメモリや実行速度が遅くなるという問題があります。
差分リスト はPrologの単一化(Unification)が高速に動作するという性質を利用して、この問題を解決しています。
差分リストの挙動に関しては以下の解説が詳しいので参照してください。
コード
とりあえずリストの結合に関して、ChatGPT先生に聞きながらコードが書けたので載せておきます。
% 差分リストに変換します
% list_to_diff_list/2
% [1,2,3] →[1,2,3 | E]-E
% ※ Eはバインドされていない変数
list_to_diff_list([], E-E).
list_to_diff_list([X|Xs], [X|E]-Tail) :-
list_to_diff_list(Xs, E-Tail).
% 元のリストに変換します
% diff_list_to_list/2
% [1,2,3 | E]-E → [1,2,3]
% ※ Eはバインドされていない変数
diff_list_to_list([X, E]-E, [X]).
diff_list_to_list([X|E]-Tail, [X|Xs]) :-
diff_list_to_list(E-Tail, Xs).
% 差分リストをマージします
% merge_diff_list/3
% [1,2,3 | E]-E
% [3,2,2 | F]-F
% → [1,2,3,3,2,2 | F]-F
% ※ Eの部分に[3,2,2]を入れるので結果として連結される
merge_diff_list(X-Y, Y-Z, X-Z).
% リストを結合します
concat_lists(List1, List2, ResultList) :-
list_to_diff_list(List1, Diff1),
list_to_diff_list(List2, Diff2),
merge_diff_list(Diff1, Diff2, Merged),
diff_list_to_list(Merged, ResultList).
test_diff_list :-
concat_lists([1,2,3], [3,2,2], List),
writeln(List)
.
test_diff_list. % 実行
簡単な解説
全体的な流れとしては以下のようになります。
- リストを差分リストに変換
list_to_diff_list
- 差分リストをマージ
merge_diff_list
- 差分リストを元のリストに戻す
diff_list_to_list
最初と最後は単に変換しているだけなので、キモは以下の差分リストをマージする処理になります。
merge_diff_list(X-Y, Y-Z, X-Z).
まず差分リスト化により、元のリストは以下のように変換されています。
これをmerge_diff_listの１、２番目の引数に入れます。
[1, 2, 3 | E]-E
[3, 2, 2 | F]-F
X-Y, Y-Zという制約があるので、X, Y, Zは以下のようになります。
X = [1, 2, 3, 3, 2, 2 | F]
Y = [3, 2, 2 | F]
Z = F
わかりにくいですが、X-Yと[1, 2, 3 | E]-Eを単一化すると以下のようになり
Eの部分にYを展開して上記のXのようになるという感じです。
X = [1, 2, 3 | E]Y = E
最後の結果の部分(X-Z)は上記より [1, 2, 3, 3, 2, 2 | F]-Fとなるので、この値が返されるということになります。
まとめ
今回は差分リストを利用したリストの結合処理を書きましたが、他のリスト操作に於いても差分リストを用いて実装できます。
以下のリンクでは、差分リストによるキュー操作やクイックソートの実装例が載っています。
差分リストを意識してコードを記述するのは難しいですが、動作上のメリットが大きいのでなるべく意識して使うようにしたいですね。