第4章 リストを処理するルール
１． リストとは
リストとは対象が順に並んだものである。最も単純な形のリストは、定数、変数、またはこの両方を半角 の空白で区切って並べ、全体を丸括弧で囲んだものである。リストの中に含まれる対象を、リストの要素 という。その要素の数をリストの長さという。要素がすべて数であるリストを数リストという。
（1 2 3 4 5 6） (a b c d e f) (*A *B *C *D *E *F) (1 *X 3 4 *Y *Z)
リスト自体もリストの要素になることができる。これは「リストのリスト」と呼ばれる。これを使えば行 列などをリストで表現することも可能である。すなわち行列の１行を数リストで表しそれらを並べたリス トを作れば、行列が「リストのリスト」として表現される。
1 2 3 ((1 2 3)
4 5 6 --> (4 5 6) 7 8 9 (7 8 9))
要素が全く含まれていないものもリストであり、それを空リストと呼ぶ。ETプログラミングでは、空リ ストを（ ）と書く。空リストの長さは０である。
２．頭部と尾部
リストの頭部とは、リストの先頭の要素である。リストの尾部はリストの２番目以降の要素からなるリス トである。例えば、(1 2 3 4 5 6) というリストの頭部は１であり、尾部はリスト (2 3 4 5 6) であ る。逆に、頭部が１、尾部が (2 3 4 5 6) のリストは (1 2 3 4 5 6) である。リストの頭部をＣＡＲ
（カー）と呼び、尾部をＣＤＲ（クダー）と呼ぶこともある。また、ＣＡＲとＣＤＲを縦棒で結びつけた 構造体 (CAR¦CDR) のことを、ＣＯＮＳ(コンス)と呼ぶ。
一般に、頭部と尾部から作られる対象は、（頭部｜尾部）の形に書かれる。記号¦は縦棒と呼ばれる。た とえば、頭部が１、尾部が (2 3 4 5 6) の場合には、それらから作られる対象は、(1¦(2 3 4 5 6)) と なる。実は (1 2 3 4 5 6) は (1¦(2 3 4 5 6)) の略記であり、両者は全く同じリストを表している。つ まり、頭部が１、尾部が (2 3 4 5 6) のリストは (1 2 3 4 5 6) であるといえる。以下の式をETIに入 力し、直接実行して結果を確認しなさい。
① (= *X (1¦(2 3 4 5 6))）
② (= *X (1 2¦(3 4 5 6)))
③ (= *X (1 ¦(2¦(3 4 5 6))))
これらのリストは、計算機の内部では全く同一のデータとして格納される。ETは、その最も簡単な表現方 法である (1 2 3 4 5 6) を用いて答を返す。
縦棒を用いて (*A¦*X) と書かれたリストの頭部と尾部はそれぞれ*Aと*Xになる。尾部を(*X) と表現し がちであるが、これは誤りである。(*X)は、*Xというただ１つの要素を持つ長さが１のリストを意味す る。
リスト処理では(*A¦*X)のように（変数が入った）式がよく使われる。このような式は考察の対象を
「絵」としてわかりやすく表現するのに適しており、パターンと呼ばれる。
ETでよく使われるパターンを列挙しておこう。
( ) 長さが０のリスト (*A) 長さが１のリスト (*A¦*X) 長さが１以上のリスト (*A *B) 長さが２のリスト (*A *B¦*X) 長さが２以上のリスト (*A *B *C) 長さが３のリスト
(*A *B *C¦*X) 長さが３以上のリスト ３． 簡単なリスト処理
リスト処理を行う上で、リストの頭部や尾部を取り出したり、リストの先頭に要素を付け加えて新しいリ ストを作ることは重要な基本操作である。
練習のために次の述語を定義する。
(first *x *y) ･･･ *ｘの頭部は*yである。リストの頭部を求める。
(rest *x *y) ･･･ *ｘの尾部は*yである。リストの尾部を求める。
(cons *a *ｂ *y) ･･･ *aを頭部、*ｂを尾部とする構造体は*yである。
これらの述語を処理するルールは次のように記述できる。
//リストの頭部を求める。
(first (*A¦*B) *Y) ==> {(= *Y *A)}.
//リストの尾部を求める。
(rest (*A¦*B) *Y) ==> {(= *Y *B)}.
//対象とリストから新たなリストを作る。
(cons *A *X *Y) ==> {(= *Y (*A¦*X))}.
これらの述語を組み合わせれば、いろいろな処理が可能になる。しかしETでは、これらの述語を組み合 わせてプログラムを書くよりも、これらの述語の中に出現する(*A¦*B)などのパターンを直接にルールの 中に書いて、プログラムを構成するほうが普通である。パターンの力を十分生かしたプログラムを書くよ うにすると、簡潔で分かりやすいプログラムを書くことができる場合が多いのである。
４． リスト処理のためのルールをつくる ４．１．与えられたリストから値を求める
（1 2 3）というリストなら３、（a b c d e）というリストならeというように、空でないリストの最後 の要素を求めるプログラムを作ることを考える。リストの最後の要素を記述する述語lastを導入する。
(last *X *E)
意味：｛*Xの最後の要素は*Eである｝
例えば、 (1) というリストの最後の要素が*Eであるという問題は、*E＝１という問題に置き換えること ができ、(2) というリストの最後の要素が*Yであるという問題は、*E＝２という問題に置き換えることが できる。
より一般的に言えば、長さが１のリストでは、そのリストの唯一の要素が求める最後の要素になる。こ れをルールで表すと、次のようになる。
(last (*A) *E) ==> {(= *E *A)}.
意味：｛リスト (*A) の最後の要素が*Eであるという問題は、*E＝*Aという問題に置き換えるこ とがで きる。｝
次にリストの長さが２以上の場合を考えてみる。例えば、(1 2)というリストの最後の要素を求めるに は、リストの先頭の要素は必要としない。よって、(1 2)というリストの最後の要素は、先頭の要素を除 いた (2) のリストの最後の要素を求める問題と等しくなる。同様に、(1 2 3)というリストの最後の要素 を求める問題は、(2 3)のリストの最後の要素を求める問題と同じである。
このような簡単化を実現できる一般的なルールを考えよう。（*A *B｜*X）というパターンは、*Aは先頭 の要素、*Bは２番目の要素、*Xは残りの要素全体のなすリストを表す。
(*A *B｜*X)というパターンから、頭部を除いたリストは (*B¦*X)となる。これらのパターンを用いて、
リストの先頭の要素を除くルールを作成する。
(last (*A *B¦*X) *E) ==> (last (*B¦*X) *E).
意味：｛リスト (*A *B¦*X) の最後の要素が *Yであるという問題は、リスト (*B¦*X) の最後の要素が*Y であるという問題に置き換えることができる。
こうして、２つのルールが得られた。与えられたリストの末尾の要素を求める問題を解くには、リストの 長さが１のときに適用できるルールと、長さが２以上のときに適用できるルールの２つがあればよい。
(last (*A) *E) ==> {(= *E *A)}.
(last (*A *B¦*X) *E) ==> (last (*B¦*X) *E).
４．２．リスト処理におけるyes-no判定問題 ４．２．１． １引数の述語に対するルール
例えば、数リスト*Xの要素がすべて偶数であるかどうかを判定するプログラムを考える。この問題を解く のに述語 evenlist を導入する。
(evenlist *X)
意味：｛数リスト*Xは、要素がすべて偶数である。｝
リスト(2)は、唯一の要素である２が偶数なので、リストのすべての要素は偶数であるといえる。すなわ ち、長さ１の数リストのときは、「要素が２で割り切れる」という問題に置き換えることができる。
(evenlist (*A)) ==> {(:= 0 (mod *A 2))}.
意味：｛長さ１の数リストはすべて偶数の要素を持つという問題は、要素が２で割り切れるという問題に 置き換えることができる。｝
(4 2 6)というリストは、頭部の４が偶数なので、「尾部(2 6)のすべて要素が偶数である」という問題に 置き換えることができる。
このことを表現するルールは以下のようになる。
(evenlist (*A¦*X)) ==> {(:= 0 (mod *A 2))}, (evenlist *X).
意味：｛(*A¦*X) の要素がすべてはすべて偶数であるという問題は、*Aが２で割り切れる問題と、リスト
*X の要素がすべて偶数であるという問題に置き換えることができる。｝
これらのルールを記述し、(2 4 6 8) や(4 2 7 8)のリストがすべて偶数の要素で構成されているかど うかを判定しなさい。
２つのルールを比べてみると、適用条件が重複している部分があることがわかる。適用条件が重複してい ても、プログラムとして誤りというわけではないが、重複の必要性を考察すると、プログラムの改善につ ながる場合が少なくない。長さ１のリストは長さ１以上のリストに含まれているので、第一のルールを削 除する方向で検討しよう。そのために、第2のルールだけで (evenlist (2 4 6 8)) を実行して見る。
得られる節は、
(ans (evenlist (2 4 6 8)) ← (evenlist ()).
である。これより、空リストを処理するルールを書く必要があることがわかる。空リストのときの答え は yes になるので、次のルールが書ける。
(evenlist ()) ==> .
意味：｛長さ０の数リストのすべての要素は偶数であるいう条件は、削除できる。｝
４．２．２． ２引数のアトムに対するルール
ある数リストの中に、指定した数が要素として含まれているかどうかを判定するプログラムを考える。例 えば、（3 7 2 6）の中にｂという要素が含まれているかどうかを調べると、2はリストの要素であるので 成功する。
この問題を解くのに述語 member を導入する。
(member *A *X)
意味：｛*Aは、リスト*Xの要素である。｝
１はリスト(1)の要素であり、2はリスト(2)の要素である。これらの例を含む一般的なルールには以下の ものがある。
(member *A (*A)) ==> .
意味：｛*Aが(*A)の要素であるという条件は、削除してよい。｝
memberの第１引数とリストの先頭の要素が一致しないときは、その要素を取り除いて短くしたリストの問 題に置き換えることができる。これを表すルールを示す。
(member *A (*B¦*X)),{(not (== *A *B))} ==> (member *A *X).
意味：｛*Aが(*B¦*X)の要素であるという問題は、*A≠*Bのとき、*Aが*Xの要素であるという問題に置き 換えることができる。｝
この２つのルールを用いて、(member 5 (1 5 3))という質問を与えて（Nモードで）実行して見よう。
すると、
(ans (member 5 (1 5 3))) ← (member 5 (5 3)).
という節が返される。これは、(member 5 (5 3))を簡単化できるルールがないからである。すでに導入し たルール：
(member *A (*A)) ==> .
は長さ１のリストにしか適用できない。これを長さ２以上のリストにも適用できるように拡張するには、
パターン(*A)を(*A¦*X)に直せばよい。
(member *A (*A¦*X)) ==> .
意味：｛*Aが(*A¦*X)の要素であるという問題は、真である。｝
これで３つのルールが得られた。最初のルールは最後のルールでカバーできるので、結局２つのルールか らなるプログラムが得られる。
(member *A (*A¦*X)) ==> .
(member *A (*B¦*X)),{(not (== *A *B))} ==> (member *A *X).
このプログラムは、数と数リストが与えられて、その数がそのリストの要素であるか否かを判定するもの であったことに注意したい。
この場合、ルール
(member *A (*B¦*X)),{(not (== *A *B))} ==> (member *A *X).
が適用されるときには、変数 *A, *B が数になるから、 == で比較することが意味を持つ。しかしもっと 一般的な memberアトムを処理したい時には、このルールは使えない。具体的な数の場合は、それらが等 しいか否かが判定できるが、変数の場合には、まだ変数がどの数になるかわからないので､一致の判定を 保留する必要がある。
例えば、リスト(3 6 9)の要素をすべて求める場合には、member の第１引数が変数となるので、上記とは 異なる次のルールを用いる必要がある。
(member *A (*B¦*X)) ==> {(= *A *B)};
==> (member *A *X).
このように、対象とするアトムの範囲によって、使えるルールの範囲も変わるので、注意が必要である。
