第12回 リスト構造と再帰プログラミング（7月2日;7月3日）

今日の課題

• リストの操作
• 再帰プログラミング

■ リストの操作

Prolog では、リスト構造を次のように記述する。

[] ... 空のリスト [a] ... １つの要素ａから成るリスト（長さ1のリスト） [a,b] ... ２つの要素ａとｂから成るリスト（長さ2のリスト） [a,b,c] ... ３つの要素ａとｂとｃから成るリスト（長さ3のリスト）

リストの操作は、変数のマッチングによる。

[X] ... １つの要素から成るリストとマッチ [X|Y] ... １つ以上の要素から成るリストとマッチ ◎ 長さ1のリストとマッチしたとき、X は先頭の要素、Y は []。 ◎ 長さ2以上のリストとマッチしたとき、X は先頭の要素、 Y は２番目以降の要素から成るリスト [X,Y|Z] ... ２つ以上の要素から成るリストとマッチ ◎ 先頭要素は X、２番目の要素は Y、 ３番目以降の要素から成るリストは Z にマッチ

練習1

次のプログラムを入力（Webからコピー）して、動作を確認しよう。ここに示している事実は、今年のF1グランプリの開催国と結果を表している。リストの先頭は、優勝者であり、完走者を順位の番号の昇順に並べている。たとえば、オーストラリア・グランプリでの優勝者は、ハミルトン(ham)、２位は、ハイドフェルド(hei)、３位は、ロズベルグ(ros)である。

優秀者を表す規則は winner_in である。リストの先頭要素ならば、優勝者であるという規則である。

gpx(australia,[but,bar,tru,glo,alo,ros,bue,bou,sut,hei,fis,web,vet,kub,rai]). gpx(malaysia, [but,hei,glo,tru,bar,web,ham,ros,mas,bou,alo,nak,piq,rai,vet,bue,sut,fis]). gpx(china, [vet,web,but,bar,kov,ham,glo,bue,alo,rai,bou,hei,kub,fis,ros,piq,sut]). gpx(bahrain, [but,vet,tru,ham,bar,rai,glo,alo,ros,piq,web,kov,bou,mas,fis,sut,bue,kub,hei]). gpx(spain, [but,bar,web,vet,alo,mas,hei,ros,ham,glo,kub,piq,nak,fis]). gpx(monaco, [but,bar,rai,mas,web,ros,alo,bou,fis,glo,hei,ham,tru,sut,nak]). gpx(turkey, [but,web,vet,tru,ros,mas,kub,glo,rai,alo,hei,nak,ham,kov,bue,piq,sut,bou]). gpx(britain, [vet,web,bar,mas,ros,but,tru,rai,glo,fis,nak,piq,kub,alo,hei,ham,sut,bue]). winner_in(W,C) :- gpx(C,[W|_]).

次の質問をしよう。

1. モナコ・グランプリの優勝者は？
2. ベッテル(vet)が優勝したグランプリの開催国は？

解答はここ

練習2

表彰台に立つことのできるのは、３位までである。そこで、表彰台た立った人のリストを表す規則、gpx_top3_in(L,C) を作成せよ。

解答はここ

■ 再帰プログラミング

Prolog は、再帰的な条件を記述することができる。

リストの中に、指定した要素が存在することを表す規則は、再帰的に宣言できる。

よく使う述語に、member(X,L) がある。リストLの中に X が存在するならばtrue なる規則である。それは次のように定義する。

member(X,[X|_]). ← もし、リストの先頭に要素があれば true である。 member(X,[_|L]) :- member(X,L). ← もし、リストの２番目以降のリストに要素があれば true である。

練習3

完走したこと（完走扱いを含む）を表す規則 gpx_on_course_in(D,C) を作成せよ。D はドライバー名、C はグランプリの開催国である。たとえば、モナコグランプリでは、中嶋(nak)は、完走扱いとなったので、?- gpx_on_course_in(nak,monaco).は Yes となり、ピケJr.(piq)は、完走していないので、?- gpx_on_course_in(piq,monaco).は No となる。

解答はここ

練習4

完走者のうちビリだった選手と開催国を表す規則 gpx_bottom_on_course_in(D,C) を作成せよ。D はドライバー名、C は国名である。たとえば、オーストラリアグランプリでは、ライコネン(rai)がビリだったのでgpx_bottom_on_course_in(rai,australia)は Yes となる。

ヒント：リストの最後の要素を表す規則を作れば良い。要素数が１つのリストの場合は、その要素が該当する。要素数が２つ以上のリストの場合、先頭を除くリストにおける最後の要素が該当する。

解答はここ

□ 小レポート

今回の練習で作成した知識の続きを作ろう。次のプログラムを作り、プログラムおよび実行結果にコメントを手書きで記載して提出せよ。

問1

F1で１位と２位になった者が同一のチームである場合、ワンツーフィニッシュと言う。たとえば、オーストラリア、スペイン、モナコでは、チーム「ブラウンＧＰ」のワンツーフィニッシュであった。また、中国、イギリスは「レッドブル」のワンツーフィニッシュであった。

そこで、チームTが国Cでワンツーフィニッシュとなったことを表す規則 one_two_finish(T,C) を作成せよ。

例えば、

 ?- one_two_finish(spain,'ブラウンＧＰ'). 

問2

F1で１位から８位までの者は、入賞者といわれ、ポイントがもらえる。そこで、選手Pが国Cのグランプリで入賞したことを表す規則 praise_in(P,C) を作成せよ。P はニックネームとする。

問3

同一のチームの２人が入賞したことをダブル入賞と言う。そこで、チームTが国Cのグランプリでダブル入賞したことを表す規則 double_praise_in(T,C) を作成せよ。

問4

国Cのグランプリで選手Aと選手Bがともに完走し、かつ A が B の上位であったことを表す規則 gpx_greater_than_in( A, B, C ) を作成せよ。たとえば、ライコネン(rai)とマッサ(mas)が完走し、かつ、ライコネンがマッサより上位であったことは、バーレインとモナコの2回である。