リスト処理を用いた述語の作成 - az-prolog @ ウィキ

今回は、リスト処理を学習する際に、よく出現する述語の

1. member
2. append
3. length
4. reverse

について学習します。

---

member/2

• 第一アリティの値が、第二アリティのリスト内に存在するか調べる

member(X,[X|_]).
member(X,[_|T]):- member(X,T).

?-member(a,[a,b,c]).
yes

?-member(d,[a,b,c]).
no

• 解説

　member述語は２つ定義します。
　まず一つ目の述語は、第一アリティと、第二アリティのリストの頭部が一致した場合、trueとし
　終了します。

　一致しなかった場合、２つ目の述語が実行され、第二アリティを頭部、尾部へ分解し
　第一アリティと、尾部を再度、自分自身へ渡します。

　※注：memberはAz-Prologには組み込み述語として定義されているので、実際に作成してみる際は、述語名を適宜変えてください。

---

append/3

• 第一アリティのリストと、第二アリティのリストを結合する

append([],Y,Y).
append([H|T],Y,[H|R]):- append(T,Y,R).

?-append([a,b,c],[d,e,f],R).
R	= [a,b,c,d,e,f]
yes

• 解説

　append述語は２つ定義します。
　まず一つ目の述語は、第一アリティが空リストであれば、第二アリティを第三アリティとユニフィケーションします。

　空リストではなければ、第一アリティのリストの頭部を、第三アリティのリストの頭部へ追加
　その後、尾部を自分自身へ渡し、再帰処理を行います。

　※注：appendはAz-Prologには組み込み述語として定義されているので、実際に作成してみる際は、述語名を適宜変えてください。

• appendの使い方（応用例）

リストの分解
?-append([1,2,3],B,[1,2,3,4,5,6])
B=[4,5,6]

2つのリストに分解できるすべての組み合わせを求める
?-append(X,Y,[1,2,3,4,5,6])
X	= [],
Y	= [1,2,3,4,5,6];
X	= [1],
Y	= [2,3,4,5,6];
X	= [1,2],
Y	= [3,4,5,6];
X	= [1,2,3],
Y	= [4,5,6];
X	= [1,2,3,4],
Y	= [5,6];
X	= [1,2,3,4,5],
Y	= [6];
X	= [1,2,3,4,5,6],
Y	= [];

上記の例のように、ひとつの述語で複数の使い方ができるのがPrologの特徴です。

---

length/2

• 第一アリティのリストの要素数をカウントする

length([],0):- !.
length([_|T],N1):-
	length(T,N2),
	N1 is N2 + 1.

?-length([a,b,c],N).
N	= 3

?-length([],N).
N	= 0

• 解説

　一つ目の述語は、第一アリティが空リストの場合、0を第二アリティへユニフィケーションします。

　第一アリティが空リストでは無い場合、尾部をlengthへ渡し、再帰させ、そこでユニフィケーション
　された第二アリティに１を足した値を、（自分自身の）第二アリティへユニフィケーションします。

　※注：lengthはAz-Prologには組み込み述語として定義されているので、実際に作成してみる際は、述語名を適宜変えてください。　　

---

reverse/2

• 第一アリティのリストの要素を逆順にする

reverse([],[]):- !.

reverse([H|T],R1):-
	reverse(T,R2),
	append(R2,[H],R1).

?-reverse([1,2,3],R).
R	= [3,2,1]

• 解説

　一つ目の述語は、例によって終了条件です。

　第一アリティが空リストでは無い場合、尾部をreverseへ渡し、再帰させ、そこでユニフィケーション
　された第二アリティと、頭部をappend述語で結合し、そのリストを（自分自身の）第二アリティへ
　ユニフィケーションします。

• reverseの最適化

　上記の定義以外に、以下の書き方も可能です。

reverse2(Ls,R):-
	reverse2(Ls,[],R).
reverse2([],R,R):- !.	
reverse2([H|T],Y,R):-
	reverse2(T,[H|Y],R).

reverse2では、reverse2/2にてreverse2/3を定義し、計算の途中結果を格納する為に
第二アリティを使用します。
このように、処理の途中経過と単一化されるものを「累算器」と呼びます。

累算器を使うことによって、二つのリストを連結するという処理が必要ではなくな
りますので、効率がかなり改善されます

※AZ-Prologに同封されている、[DEL_APP.PL]によると
　reverseの定義では、計算量はO(n^2)オーダーとなり、reverse2ではO(n)オーダーで済むとのこと。
　Ｎ要素のリストを反転する述語のCall回数は、それぞれ次のようになる。

N	1	2	10	30	100
revese	3	6	66	496	5151
revese2	3	4	12	32	102

※詳しくは上述のファイルを参照してください。