SWI-Prolog 備忘録的虎の巻

アイデアとして、リストを [リスト]ー[リスト] のように差で表現する方法があります。

♪ 例えば、

次は、同じ[a,b,c]を表しています。そうです決めたのです。
[a,b,c,d,e]-[d,e]              => [a,b,c]
[a,b,c,d,e,f,g,h]-[d,e,f,g,h]  => [a,b,c]
[a,b,c,m]-[m]                  => [a,b,c]
[a,b,c]-[]                     => [a,b,c]

上の４行を一般化して表現すると

[a,b,c|E]-E

となります。

上の４行が、一般化式とパターンマッチングするか試してみます。

?- [a,b,c,d,e]-[d,e]               = [a,b,c|E]-E.
E = [d, e].

?- [a,b,c,d,e,f,g,h]-[d,e,f,g,h]   = [a,b,c|E]-E.
E = [d, e, f, g, h].

?- [a,b,c,m]-[m]                   = [a,b,c|E]-E.
E = [m].

?- [a,b,c]-[]                      = [a,b,c|E]-E.
E = [].

?-

パターンマッチングすることがわかりました。

上の差分リストは、リストの結合に使うと効率的に働くようです。

普通リストの結合は、次のように定義されますが、
続けて差分リストでの方法を示します。

♪ プログラムコード code

% dl_append.pl

% 通常

a_append( [], A, A ).
a_append( [X|A], B, [X|C] ) :- a_append( A, B, C ).


% 差分リスト

d_append(I-M, M-O, I-O).

実行してみましょう。

love:uema% swipl -q -s dl_append.pl
?- a_append( [a,b,c], [x,y,z], A ).
A = [a, b, c, x, y, z].

?- d_append([a,b,c|E]-E,  [x,y,z|W]-W,  A).
E = [x, y, z|W],
A = [a, b, c, x, y, z|W]-W.

?-

一般形から読み解くと、[a,b,c]+[x,y,z]=>[a,b,c,x,y,z]となり結合を表しています。

M.Hiroiさんにならって take_integer.pl code
（同一ではありません。差分リストの表現が違う）

% take_integer.pl

take_integer(X, Y) :- take_int_sub(X, Y-[]).
take_int_sub([X | Xs], Ys-Zs) :-
		take_int_sub(X, Ys-Ys1), take_int_sub(Xs, Ys1-Zs), !.
take_int_sub(X, [X | Xs]-Xs) :- integer(X), !.
take_int_sub(_, Ys-Ys).

実行してみます。

$ swipl -qs take_integer.pl
?- take_integer([a, 1, [b, 2]], Z).
Z = [1, 2].

?- q.
$

♪クイックソート code

love:uema% cat quick.pl
% quick.pl
% 通常版
quick1(Xs, Ys) :- quick_sub(Xs, [Ys, []]).
quick_sub([X | Xs], [Ys, Zs]) :-
	partition(Xs, X, Littles, Bigs),
	quick_sub(Littles, [Ys, [X | Ys1]]),
	quick_sub(Bigs, [Ys1, Zs]).
quick_sub([], [Xs, Xs]).

% 差分リスト版
quick2(Xs, Ys) :- quick_sub2(Xs, Ys - []).
quick_sub2([X | Xs], Ys - Zs) :-
	partition(Xs, X, Littles, Bigs),
	quick_sub2(Littles, Ys - [X | Ys1]),
	quick_sub2(Bigs, Ys1 - Zs).
quick_sub2([], Xs - Xs).

% quick1, quick2, 共通
partition([X | Xs], Y, [X | Ls], Bs) :-
	X =< Y, partition(Xs, Y, Ls, Bs).
partition([X | Xs], Y, Ls, [X | Bs]) :-
	X > Y, partition(Xs, Y, Ls, Bs).
partition([], _, [], []).
love:uema%

♪ 実行してみます。

love:uema% swipl -q -s  quick.pl
?- quick1([5, 3, 7, 6, 9, 8, 1, 2, 4], X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ;
false.

?- quick2([5, 3, 7, 6, 9, 8, 1, 2, 4], X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ;
false.

?-

♪ 図解します（ append ）。

                      (A2)                    
A1                     Z1                      Z2
|-----------L1---------|----------L2-----------|-------------------

|----------------------L3----------------------|

結合
       L1 = A1 - Z1    ＋    L2 = A2 - Z2   ==>   L3 = A1 - Z2,    (Z1==A2:でなければならない)