リスト処理を用いた述語の作成


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

今回は、リスト処理を学習する際に、よく出現する述語の
  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述語は2つ定義します。
 まず一つ目の述語は、第一アリティと、第二アリティのリストの頭部が一致した場合、trueとし
 終了します。

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

  ※注: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述語は2つ定義します。
 まず一つ目の述語は、第一アリティが空リストであれば、第二アリティを第三アリティとユニフィケーションします。

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

  ※注: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へ渡し、再帰させ、そこでユニフィケーション
 された第二アリティに1を足した値を、(自分自身の)第二アリティへユニフィケーションします。

  ※注: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)オーダーで済むとのこと。
 N要素のリストを反転する述語のCall回数は、それぞれ次のようになる。
N 1 2 10 30 100
revese 3 6 66 496 5151
revese2 3 4 12 32 102

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