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

今日の課題

■リスト構造

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

[a,b,c,d]

次の記述は，リストの先頭要素は変数Xであり，残りの要素列（リスト）が変数Yであることを表す． 

[X|Y]

また，先頭X，第２番目Y，残りの要素列Zを表す記述は，次のとおりである． 

[X,Y|Z]

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

規則 winner_in は，開催国と優勝者の関係を表す規則である．アンダーバーは，バインド値が返されない特別な変数である． 

gpx(america,  [msc,mas,fis,tru,alo,bar,cou,liu]).
gpx(canada,   [alo,msc,rai,fis,mas,tru,hei,cou]).
gpx(england,  [alo,msc,rai,fis,mas,mon,hei,vil]).
gpx(monaco,   [alo,mon,cou,bar,msc,fis,hei,rsc]).
gpx(spain,    [alo,msc,fis,mas,rai,but,bar,hei]).
gpx(europe,   [msc,alo,mas,rai,bar,fis,ros,vil]).
gpx(sanmarino,[msc,alo,mon,mas,rai,web,but,fis]).
gpx(australia,[alo,rai,rsc,hei,fis,vil,bar,cou]).
gpx(malaysia, [fis,alo,but,mon,mas,msc,vil,rsc]).
gpx(bahrain,  [alo,msc,rai,but,mon,web,ros,kli]).

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(spain,[alo,msc,fis]) という関係である． 答え ⇒

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

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

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

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

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

再帰の終了条件のところで得た結果を返すには

memberの定義で，_の所に何が入っているのか確認してみよう．そのために，memberの定義を書き換えてみよう． 

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

1行目で，R にバインドされた結果が，第３引数を通じて返される．

そして，次の質問をしてみよう． 

?- member(c,[a,b,c,d,e,f],R).

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

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

R に何が入ったのか，観察しよう．

例題５

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

■ 小レポート

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

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

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

(c) 2006.7.4 by tokuhisa