今回は、リスト処理を学習する際に、よく出現する述語の
- 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述語は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([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述語で結合し、そのリストを(自分自身の)第二アリティへ
ユニフィケーションします。
上記の定義以外に、以下の書き方も可能です。
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 |
※詳しくは上述のファイルを参照してください。
最終更新:2014年05月07日 12:43