「リスト処理を用いた述語の作成」の編集履歴（バックアップ）一覧に戻る
リスト処理を用いた述語の作成 - (2014/05/07 (水) 12:43:02) のソース
今回は、リスト処理を学習する際に、よく出現する述語の
+member
+append
+length
+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とし
終了します。
一致しなかった場合、２つ目の述語が実行され、第二アリティを頭部、尾部へ分解し
第一アリティと、尾部を再度、自分自身へ渡します。
&bold(){※注：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述語は２つ定義します。
まず一つ目の述語は、第一アリティが空リストであれば、第二アリティを第三アリティとユニフィケーションします。
空リストではなければ、第一アリティのリストの頭部を、第三アリティのリストの頭部へ追加
その後、尾部を自分自身へ渡し、再帰処理を行います。
&bold(){※注：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へ渡し、再帰させ、そこでユニフィケーション
された第二アリティに１を足した値を、（自分自身の）第二アリティへユニフィケーションします。
&bold(){※注：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|
※詳しくは上述のファイルを参照してください。
