第12回リスト構造と再帰プログラミング

今日の課題

■リスト構造

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 にマッチ

では、次のプログラムを入力（コピー）してみよう。 事実は、今年のF1グランプリについて、開催国とその結果を表している。 リストは、レース結果で、入賞者（第１位から第８位まで）の人物の略称である。 たとえば、アメリカグランプリのデータは gpx(america, ...) の部分が表している。 優勝者は、ham (ルイス・ハミルトン）である。 また、第２位はalo（フェルナンド・アロンソ）、 第３位はmas（フェリペ・マッサ）である。

規則 winner_in は、開催国と優勝者の関係を表す規則である。なお、アンダーバーは、特別な変数で、バインド値が返されず、１行の中で複数回使われても、互いに関係を持たない。 

gpx(australia,[rai,alo,ham,hei,fis,mas,ros,rsh]).
gpx(malaysia, [alo,ham,rai,hei,mas,fis,tru,kov]).
gpx(bahrain,  [mas,ham,rai,hei,alo,kub,tru,fis]).
gpx(spain,    [mas,ham,alo,kub,cou,ros,kov,sat]).
gpx(monaco,   [alo,ham,mas,fis,kub,hei,wur,rai]).
gpx(canada,   [ham,hei,wur,kov,rai,sat,alo,rsh]).
gpx(america,  [ham,alo,mas,rai,kov,tru,web,vet]).
gpx(france,   [rai,mas,ham,kub,hei,fis,alo,but]).

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

例題１

次の質問をしてみよう。この質問の意味は、アメリカグランプリの優勝者Wは誰であるかを求めることである。 

?- winner_in(W,america).

例題２

aloが優勝した国を求める質問はどのようにすれば良いか？ 答え ⇒

例題３

開催国と第２位の関係を表す規則 second_winner_in(W,C) を作ろう。 答え ⇒

例題４

優勝者、第２位、第３位の３名が表彰台に立つことができる。 開催国と表彰台に立った人の関係を表す規則 gpx_top3(C,L) を作ろう。 ここで、L はその３者の名前のリストとする。たとえば、 gpx_top3(france,[rai,mas,ham]) という関係である。 答え ⇒

■ 簡単な再帰プログラミング

再帰的にリストの要素をチェックする

member(X,L) は、リストLの中にXが存在することを表す。メンバーは次のとおり定義される。 

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

再帰的な定義になっている。最初の行は、X がリストの先頭に存在することを表わす。２行目は、X がリストの２番目以降に存在することを表す。

リストに指定要素を見付けたとき、それ以降の要素から成るリストを得る

scheme の member では、リストの中に指定要素を見つけると、それ以降の要素から成るリストを返り値としていた。リスト操作において、この返り値の得られることのほうが便利なことがある。

そこで、指定要素の次の要素から成るリストを返す member を作ろう。なお、Prolog では引数の数の異なる規則や事実は別ものとして扱われる。 

member(X,[X|R],R).
member(X,[_|L],R):-member(X,L,R).

次のとおり動作する。 

?- member(c,[a,b,c,d,e],X).
X = [d,e]

また、トレースモードで実行してみよう。具体的には次の手順をとる。

  1. プログラムをロードする。
  2. ?- trace.
  3. ?- member(c,[a,b,c,d,e,f],R).
  4. Call のときは、表示された質問を実行しているところを表し、Exit のときは、 質問の結果を表している。リターンキーを押して、トレースを進めよう(creapという)。

R に何が入ったのか、観察しよう。

例題５

開催国 C と入賞者 P （第１位から第８位の人）の関係を表す規則 got_point_in(P,C)を、member を使って作ろう。 答え ⇒

■ 小レポート

上記の例題のプログラムが利用可能であるとする。

  1. 人物 X と人物 Y が、同時に表彰台に上ったグランプリの開催国を質問する方法を示せ。
    ※ たとえば、alo と mas が同時に表彰台（1位から3位までの入賞者）に上ったのは、spain, monaco, america である（セミコロンを押して、複数の解を表示する）。
  2. 人物 X が入賞し、かつ、それよりも下位に人物 Y が入賞したグランプリの開催国を表す規則 greater_than_in(X,Y,C) を定義せよ。マッサ（mas）がアロンソ(alo)よりも勝っていた開催国を質問し、その結果を示せ。

小レポートには、プログラム、質問方法、結果を記載せよ。

(c) 2007.7.2 by tokuhisa