第12回 リスト構造と再帰プログラミング（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 にマッチ

例題１

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

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

gpx(australia,[ham,hei,ros,alo,kov,nak,bou,rai]).
gpx(malaysia, [rai,kub,kov,tru,ham,hei,web,alo,cou,but,piq,fis,bar,ros,dav,sat,nak]).
gpx(bahrain,  [mas,rai,kub,hei,kov,tru,web,ros,glo,alo,bar,fis,ham,nak,bou,dav,sat,cou,sut]).
gpx(spain,    [rai,mas,ham,kub,web,but,nak,tru,hei,fis,glo,cou,sat]).
gpx(turkey,   [mas,ham,rai,kub,hei,alo,web,ros,cou,tru,but,kov,glo,bar,piq,sut,vet]).
gpx(monaco,   [ham,kub,mas,web,vet,bar,nak,kov,rai,alo,but,glo,tru,hei]).
gpx(canada,   [kub,hei,cou,glo,mas,tru,bar,vet,kov,ros,but,web,bou]).
gpx(france,   [mas,rai,tru,kov,kub,web,piq,alo,cou,ham,glo,vet,hei,bar,nak,ros,bou,fis,sut]).

winner_in(W,C) :- gpx(C,[W|_]).

次の質問をしよう。

  1. カナダ・グランプリの優勝者は？
  2. マッサ(mas)が優勝したグランプリの開催国は？

解答はここ

例題２

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

解答はここ

■ 再帰プログラミング

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

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

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

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





例題３

完走したこと(完走扱いを含む)を表す規則 gpx_on_course_in(D,C) を作成せよ。D はドライバー名、C はグランプリの開催国である。たとえば、フランスグランプリでは、中嶋(nak)は、完走したので、?- gpx_on_course_in(nak,france).は Yes となり、バトン(but)は、完走していないので、?- gpx_on_course_in(but,france).は No となる。

解答はここ

例題４

完走者のうちビリだった選手と開催国を表す規則 gpx_buttom_on_course_in(D,C) を作成せよ。D はドライバー名、C は国名である。たとえば、フランスグランプリでは、スーティル(sut)がビリだったのでgpx_buttom_on_course_in(sut,france)は Yes となる。

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

解答はここ

□ 小レポート

「ひとり尻取り」のプログラムを作ろう。ルールは次のとおりである：

実行の様子を以下に示す。 
?- L=[_,_,_,_], shiritori(L), print_list(L).
クマ
マントヒヒ
ヒトコブラクダ
ダックスフント

L = [[165, 175, 165, 222], [165, 222, 165, 23, 165, 200, 165|...], [165, 210, 165, 200, 165, 179|...], [165, 192, 165, 195, 165|...]] ;

クマ
マングース
スズメ
メダカ

L = [[165, 175, 165, 222], [165, 222, 165, 243, 165, 176, 161|...], [165, 185, 165, 186, 165, 225], [165, 225, 165, 192, 165|...]]

Yes
?-

shiritori(L) にて、リストの各単語が尻取りの関係であることが定められる。print_list(L) は、文字コード列 [165, 175, ...] をアトムに変換して画面に出力する。

shiritori(L) は次の知識である。

  1. もし、リスト L が空 [] ならば、尻取りの関係である。
  2. もし、リスト L が１つの単語であり、それが登録されているならば、尻取りの関係である。
  3. もし、リスト L が２つ以上の単語であり、２つの単語が登録されており、１つめの単語の末尾の文字と、２つめの単語の先頭の文字が一致し、２つめの単語とリストの残り(リスト L の３つめ以降の単語によるリスト)とを合せることで構成されるリストにおいて尻取りの関係があるならば、リスト L は尻取りの関係である。

print_list(L) は次のとおりである。 
print_list([]).
print_list([X|L]):-
        name(S,X),
        write(S), nl,
        print_list(L).

なお、単語の登録例を以下に示す。実行例を作るために、単語を追加すること。 
word("マントヒヒ").
word("ヒトコブラクダ").
word("ダックスフント").
word("クマ").
word("アライグマ").
word("マングース").
word("スズメ").
word("メダカ").

カタカナの文字列、つまり、ダブルコーテーションで囲まれた文字列であることに注意せよ。全角のカタカナは、２バイトコードである。たとえば、"マ" は、[165,222] という２バイトで表わされる。

"クマ" = [165, 175, 165, 222] である。W = "クマ" とは、W = [165, 175, 165, 222] なので、先頭の１文字を W から抽出する方法は、W = [X,Y|_] とすれば良い。その結果、X = 165, Y = 175 となる。最後の１文字を W から抽出する方法は、再帰呼出しを使う。もし W が１文字で構成されるならば、W = [A,B] なので、すぐに最後の１文字が得られる。もし、２文字上の場合は、最初の１文字を捨てて、残りの文字における最後の１文字であるならば、全体でも最後の１文字である。

レポートには次のことを記載せよ。

  1. プログラムリスト。主たる規則にコメントを書く。
  2. 実行例１。尻取りをする単語数が４つの場合。
  3. 実行例２。尻取りをする単語数が３つの場合で、最後の単語が「ダックスフント」である場合。
(c) 2008.6.27 by tokuhisa