導入
最近、論理プログラミングの勉強を始めました。理解をより深めるために、自分の言葉でまとめたメモを投稿していこうと思います。今回はリスト編です。初めて学ぶ方は、ぜひ前回の「論理型言語(Prolog)入門～再帰編～」や前々回の「論理型言語(Prolog)入門」もご覧ください。
1. リストとは
リストとは、構造（0個以上の定数、変数を持ったオブジェクト）である。リストは一般的に[a,b|c]のように角括弧、カンマ、縦棒用いて表す。リストと再帰は密接に関係している。
2. リストの基本構造
リストは要素をカンマ、縦棒で分ける。それぞれには以下のような意味がある。
- カンマ：要素と要素を区切る
[a, b, c]：a,b,cの３つの要素を持つ - 縦棒：先頭要素（Head）と残りのリスト（Tail）を区切る
[a|[b,c]]：aがHead、[b,c]がTailとなる
[a,b,c]と[a|[b,c]]は等価となる
※空リスト[]はTailの終端になる。
[a,b,c]と[a|[b|[c|[]]]]は等価となる
3. リストの練習問題
問題
XとYをa,b,c,[]を用いて具体化してください。
[X,Y] = [a,b][X|Y] = [a,b,c][X|Y] = [a][a,X,Y] = [a,b|[c]][X|[Y]] = [a,c]
解答
-
X = a, Y = b
左辺と右辺はカンマ区切りで一対一対応できる -
X = a, Y = [b,c]
Xは先頭要素、Yは残りのリストである
Xはアトム、Yはリストとなる -
X = a, Y = []
Xは先頭要素、Yは残りのリストである
要素が1つの場合も空リストが残るので、Yは空リスト -
X = b, Y = c
Xは２番目の要素、Yは３番目の要素のリストである
cはすでにリストなので、要素のみが答えである -
X = a, Y = c
Xは先頭要素、Yは残りの要素のリストであるがすでにリストなので要素のみとなる
4. リストプログラムの基本構造
リストはHeadとTailの再帰的な構造を持つため、リストを操作するプログラムも再帰を用いることが多い。基本構造は以下のような形式となる。
- 単純解
自明な解を設定する - 条件
自明な解が存在しない場合の条件 - 簡単化
複雑度xの問題を複雑度x-1の問題にする - 再帰
複雑度x-1の問題に同じ処理を適用する - 合成
複雑度xの問題の解を複雑度x-1までの解と合わせる
5. リストプログラムの例
リストの長さを求めるプログラム
listsize([],0).
listsize([_|T],N) :-
listsize(T,N1),
N is N1 + 1.
listsize.plはリストの長さを求めるプログラムであり、2つの引数を用意した。1個目の引数が求める対象となるリストであり、2個目がその解である。リストの基本構造とは以下のように対応している。
- 単純解
空リストの長さを0とする - 条件
リストが1個以上の要素を持つリストである - 簡単化
リストを先頭要素_と残りの要素Tの２つに分ける
この時、先頭要素はどのアトムでもよいため、無記名変数とする - 再帰
残りの要素Tに対して同じ処理を行い、その解をN1とする - 合成
解NはN1+1で表されるとする
リストの最後の要素を求めるプログラム
last([X],X).
last([_|T],A) :-
last(T,A).
last.plはリストの最後の要素を求めるプログラムであり、2つの引数を用意した。1個目の引数が求める対象となるリストであり、2個目がそのリストの最後の要素である。リストの基本構造とは以下のように対応している。
- 単純解
リストの要素が１つの時はその要素を最後の要素とする - 条件
リストが２個以上の要素を持つリストであるとする - 簡単化
リストを先頭要素_と残りの要素Tの２つに分ける
この時、先頭要素はどのアトムでもよいため、無記名変数とする - 再帰
残りの要素Tに対して同じ処理を行い、その解をAとする - 合成
合成するものがないため省略する
6. リストプログラムの練習問題
問題1
以下のプログラムはリストとリストを連結したリストを出力するプログラムの一部である。例えば、combi([a,b],[c,d],[a,b,c,d])などである。プログラムの〇と△を埋めよ。
combi([],Y,Y).
combi([H|T],Y,Z) :-
combi(〇, △,Z1),
Z = [H|Z1].
解答1
プログラムをリストの基本構造に当てはめると以下のようになる。
- 単純解
１個目のリストが空リストの時、２個目のリストと結合したリストが等しくなる - 条件
リストが1個以上の要素を持つリストである - 簡単化
リストを先頭要素Hと残りの要素Tの２つに分ける - 再帰
〇と△に対して同じ処理を行い、その解をZ1とする - 合成
ZはZ1にHを追加したものとする
この時、要素Hを１つずつ見ているので、再帰はTに対して行う。
また、２つ目のリストYは変化しないためYのままである。
そのため、答えは以下のようになる
〇=T``△=Y
問題2
要素Aをリストが含んでいるかを確認する、プログラムを作成せよ。ただし、ファンクターはincludeのみを用い、引数は2とする。例えば、include(a,[a,b,c])がyesとなる。
解答2
まず、リストの基本構造を作成する。リストの基本構造は以下のようになる。
- 単純解
リストの先頭要素がAである - 条件
リストが1個以上の要素を持つリストである
また、Aとリストの先頭要素が等しくないとする - 簡単化
リストを先頭要素Hと残りの要素Tの２つに分ける - 再帰
AとTに対して同じ処理を実行する - 合成
合成するものがないため省略する
このような基本構造をプログラムにすると以下のような答えになる。
include(A,[A|_]).
include(A,[H|T]) :-
A \= H,
include(A,T).
問題3
リストの要素を逆順にしたリストを出力する、プログラムを作成せよ。例えば、reverse([c,b,a],[a,b,c])がyesとなる。
解答3
まず、リストの基本構造を作成する。リストの基本構造は以下のようになる。
- 単純解
空リストの逆順は空リストである - 条件
リストが1個以上の要素を持つリストである - 簡単化
リストを先頭要素Hと残りの要素Tの２つに分ける - 再帰
Tに対して同じ処理を行い、その解をA1とする - 合成
AはHとA1を合成させたものである
※A=[A1|H] とするとリストの中にリストが入ってしまうため、合成には 問１のcombi を用いる
このような基本構造をプログラムにすると以下のような答えになる。
reverse([],[]).
reverse([H|T],A) :-
reverse(T,A1),
combi(A1,[H],A).
7. リストを扱う時の注意点
-
yes/noを返すプログラムには合成のステップは不要である -
appendなど既存の組み込み述語と同じ名前を使うとエラーになるため、ファンクター名を変える - 縦棒
|の右側（Tail）は必ずリストとする - 再帰の終了条件（単純解）を忘れると無限ループになる
- 変数がプログラム中に1度しか登場しない場合は、無記名変数
_を使用する
まとめ
- リストとは、0個以上の定数、変数を持ったオブジェクトである
- リストは角括弧、カンマ、縦棒用いて表す
- リストは Head と Tail から構成され、再帰と密接に関係している
- リストプログラムは単純解・条件・簡単化・再帰・合成の5つの基本構造で作成する
- リストを用いる際にはいくつかの注意点が存在する
参考
以下のサイト・参考書が分かりやすく、参考にさせていただきました。
『Prologへの入門』(I.Bratko 著)
https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0