リスト処理

前章でも少しリスト処理について考えてみました。リスト処理はPrologプログラミングにおいて頻繁に用いられます。データを何らかのまとまった単位で処理したい場合に、便利だからです。構造を用いても良いのですが、構造では、引数の数が異なるとユニファイしませんでした。ひとまとめにしたいデータの数が不定な場合は[ ]で括って、要素をカンマで区切った列の形のリストが便利なのです。

定数や文字定数、変数などの他に、構造やリスト自体もリストの要素となります。したがって、
          [f(x,y),g(x)]
もリストですし、
          [[a,b],[h(c)]]
もリストです。 リストは縦棒を用いてリストの先頭の要素と残りのリストとに分けることができましたね。
          [Head|Tail]
これは[a]とは、どのようにユニファイするのでしょうか。また、[ ]とは、どうでしょうか。[a]の場合は、
          Head = a, Tail = [ ]
となります。[ ]の場合は先頭の要素がないので、ユニファイしません。

では、先ず次の例題について考えてみましょう。

member

第1パラメータのデータが第2パラメータのリストに含まれているかどうか調べる。

上の機能を持つ関数memberを作成しましょう。具体的には、以下のように実行します。
          ?- member(a,[a,b,c]).                  .....(1)
          yes

          ?- member(b,[a,b,c]).                  .....(2)
          yes

          ?- member(d,[a,b,c]).                  .....(3)
          no

          ?- member([a,b],[[a,c],[a,b],[a,d]]).  .....(4)
          yes
第1パラメータのデータが第2パラメータのリストに含まれていればyesと答えます(上の(1),(2)参照)。含まれていなければnoと答えます(上の(3))。第1パラメータのデータはリストでもいいのです(上の(4))。いま、memberを「第1パラメータのデータが第2パラメータのリストに含まれているかどうか調べる」関数と考えていましたので、上のような使い方がノーマルですね。でも、次のように使うこともできます。
          ?- member(X,[a,b,c]).
このように使うと「リストの中の要素を取り出す」ことになります。この質問を入力するとPrologは下のように動作します。
          X=a;
          X=b;
          X=c;
          no
セミコロンで別解を求めると、Prologは順次リストの要素を出力します。つまり、「リストの中の要素を先頭から順に取り出す」ことになりますね。Prologの場合、引数を定数にも変数にもできますから(勿論、プログラムによっては正常に動作しなくなるものもあるでしょうが)いろいろな使い方ができて便利です。

さて、このような関数をどのようにして作成したらいいのでしょう。

第1パラメータをTarget、第2パラメータをListとすると、TagetがListに含まれているのは、以下の場合です。 先頭の要素を除いた残りのリストにTargetが含まれているかどうかは、残りのリストに関して再帰呼び出しをすればいいのです。Listの中にTargetが含まれていれば、いずれリストの先頭の要素として現れてくるでしょう。リストの先頭の要素がTargetでなければ、それを除いた残りのリストに関して再帰呼び出しをして、調べ続けるのです。これをプログラムにすると次のようになります。
          member(Target,[Target|_]).
          member(Target,[_|Tail]):-member(Target,Tail).
どうでしょう。再帰を用いたプログラムは慣れないと戸惑いがちです。しかし、決して難しいことをしているのではありません。再帰に慣れれば、こんな簡単なことはないのです。

前章の演習で偶数かどうかを判断するのに、剰余ではなくて「どんどん2を引いていく」という方法を採りましたね。あれと同じです。皆さんには一発で答えの出る剰余の方が判りやすいでしょう。しかし、剰余の関数も自分で作らなければならないとしたらどうですか。「2を引く」という操作を繰り返すことによって解を求めるのは決して難しいことではないのが判ると思います。さあ、演習です。頑張ってください。

last

第1パラメータのリスト(以下、Listとします)の最後の要素を第2パラメータとして取り出すlastという関数を作りなさい。

実行時には以下のようになります。
          ?- last([a,b,c],X).
          X=c

          ?- last([a,b,[c]],X).
          X=[c]

          ?- last([ ],X).
          no
縦棒を使えば、リストの先頭の要素を取り出すのは簡単でした。では、最後の要素はどうでしょう。どのようにしたら、スムーズに取り出せるでしょうか。

考え方としては、与えられたリストListの最後の要素Targetを求めるにあたって、 となります。

delete

第1パラメータのデータ(以下、Targetとします)を第2パラメータのリスト(List)から消去するdeleteという関数を作りなさい。

実行時には以下のようになります。
          ?- delete(a,[a,b,c],X).
          X=[b,c]

          ?- delete(b,[a,b,c],X).
          X=[a,c]

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

          ?- delete([a,b],[[a,b],[a,c],[a,d]],X).
          X=[[a,c],[a,d]]
TargetがListの中にあれば、これを消去して第3パラメータのリストとします。なければ、第3パラメータのリストはListそのものとなります。Targetはリストでも可とします。但し、TargetがListの中に重複して含まれている場合は、全て消去するのは少し難しいので、最初に出現するもののみ消去することにしてください。
          ?- delete(a,[a,b,a,b],X).
          X=[b,a,b]
考え方としては、ListからTargetを除いたリストXを求めるにあたって、 となります。どうでしょう。考えてみてください。

add

第1パラメータのリスト(List1)と第2パラメータのリスト(List2)を結合して第3パラメータのリストとするaddという関数を作りなさい。

実行時には以下のようになります。
          ?- add([ ],[a,b,c],X).
          X=[a,b,c]

          ?- add([g],[a,b,c],X).
          X=[g,a,b,c]

          ?- add([a,b,c],[ ],X).
          X=[a,b,c]

          ?- add([ ],[ ],X).
          X=[ ]
考え方としては、List1とList2を結合したリストXを求めるにあたって、 となります。 addは使いでのある関数です。
          add(L,[b,c],[a,b,c]).
とか、
          add([1,2,3],M,[1,2,3,4,5,6]).
などとすることによって、リストの一部を取り出すことができます。addができあがったら、上のような質問を入力してみてどのように動作するのか確認しておきましょう。

reverse

第1パラメータのリスト(List)の要素を逆順にして第2パラメータのリストとするreverseという関数を作りなさい。

実行時には以下のようになります。
          ?- reverse([a,b,c],X).
          X=[c,b,a]

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

          ?- reverse([ ],X).
          X=[ ]
考え方としては、リストListを逆順にして得られたリストをXとすると、 となります。

addを利用すると比較的簡単にできます。

cap

リストを1つの集合と考えます。第1パラメータと第2パラメータにリストを指定し、これら2つの集合の共通部分を求めるcapという関数を作りなさい。

実行時には以下のようになります。
          ?- cap([ ],[a,b,c],X).
          X=[ ]

          ?- cap([a,b,c],[ ],X).
          X=[ ]

          ?- cap([a,d],[a,b,c],X).
          X=[a]
第1パラメータ、第2パラメータそれぞれのリストの中に重複して含まれている要素があった場合はどうなるのでしょう。各パラメータのリストの要素をチェックしてから共通部分を求めればいいのですが、これは少し難しいので今回は考えなくていいです。
          ?- cap([a,a],[a,b,a,b],X).
          X=[a,a]
考え方としては、2つのリストList1,List2の共通部分Xを求めるにあたって、 となります。

cup

では、同じように2つの集合の和集合を求めるcupという関数を作りなさい。

実行時には以下のようになります。
          ?- cup([a,b,c],[b,c,d],X).
          X=[a,b,c,d]

          ?- cup([ ],[a,b,c],X).
          X=[a,b,c]
これまでの問題はヒントとしてプログラミングの考え方を示してきました。このcupはリスト処理の最後の問題なので、ヒントはなしです。自力でやってください。基本的にはいままでの問題で用いた戦略と同じです。では、頑張ってね。健闘を祈る。
目次に戻る目次に戻る