Scheme手習い 第５章 *すごい* 星がいっぱいだ（その２）
木構造のデータの扱いの続き。リストの比較を習います。
ノート：
and
最初のandの議論。
> (let ((x 'pizza) (l '(mozzarella pizza))) (and (atom? (car l)) (eq? (car l) x))) #f > (let ((x 'pizza) (l '((mozzarella mushroom) pizza))) (and (atom? (car l)) (eq? (car l) x))) #f >
xとlの例を与えましょう。ここで、
(and (atom? (car l)) (eq? (car l) x))
は真です。
原文は"Give an example for x and l where (and (atom? (car l)) (eq? (car l) x)) is true."なので、「(and (atom? (car l)) (eq? (car l) x))が真となる様なxとlの例を挙げなさい。」と解釈。
> (let ((x 'pizza) (l '(pizza (tastes good)))) (and (atom? (car l)) (eq? (car l) x))) #t >
脚注
(cond …)も、すべての引数が考慮されない事があると言う性質を持っています。この性質のため(and …)も(or …)も、(cond …)を使って関数として定義(define)することはできません。
Schemeでは関数の場合は全ての引数を評価してから関数が適用されるので。
eqlist?
最初の定義はあまりパッと見で分かりにくいが、それぞれの引数は３つの状態
- 空リスト
- アトムで始まるリスト
- リストで始まるリスト
を持つ可能性があるため、その組み合わせで９つの質問をすると言う事になり、下記の順番で条件分岐されている事が分かる。
| 第１引数 | 第２引数 | 判定または処理 | |
|---|---|---|---|
| 1 | 空リスト | 空リスト | 真 |
| 2 | 空リスト | アトムがリストにconsされたもの | 偽 |
| 3 | 空リスト | （リストが別のリストにconsされたもの） | 偽 |
| 4 | アトムがリストにconsされたもの | 空リスト | 偽 |
| 5 | アトムがリストにconsされたもの | アトムがリストにconsされたもの | (car l1)と(car l2)が等しく、残りのリスト同士が等しければ真 |
| 6 | アトムがリストにconsされたもの | （リストが別のリストにconsされたもの） | 偽 |
| 7 | （リストが別のリストにconsされたもの） | 空リスト | 偽 |
| 8 | （リストが別のリストにconsされたもの） | アトムがリストにconsされたもの | 偽 |
| 9 | （リストが別のリストにconsされたもの） | リストが別のリストにconsされたもの | (car l1)と(car l2)が等しく、残りのリスト同士が等しければ真 |
暗黙の前提としてl1、l2にはアトムは渡されない。最初にeqlist?を呼ぶ時には呼ぶ側の責任だが、再帰する時にアトムを渡さない様にする必要がある。
１番目、２番目の条件はそのままだが、３番目の引数はl2に関してはelseと同様なので特に条件式に「l2がリストが別のリストにconsされたもの」と言う様な記述は現れない。同じ考え方で７番目以降の条件にはl1が出て来ない。
５番目の条件と９番目の条件は判定または処理が同じ記述になっているが、car側の比較の仕方が異なる。５番目の条件はアトム同士の比較なのでeqan?で比較するが、９番目の条件ではeqlist?で比較する。
最初の定義で評価する。
> (let ((l1 '(strawberry ice cream)) (l2 '(strawberry ice cream))) (eqlist? l1 l2)) #t > (let ((l1 '(strawberry ice cream)) (l2 '(strawberry cream ice))) (eqlist? l1 l2)) #f > (let ((l1 '(beef ((sawsage)) (and (soda)))) (l2 '(beef ((salami)) (and (soda))))) (eqlist? l1 l2)) #f > (let ((l1 '(beef ((sausage)) (and (soda)))) (l2 '(beef ((sausage)) (and (soda))))) (eqlist? l1 l2)) #t >
次に９つの条件を纏める。
| 元の条件分岐 | 条件の内容 | 判定または処理 |
|---|---|---|
| １番目 | l1、l2とも空リスト | 真 |
| ２番目、３番目、４番目、７番目 | l1、l2の片方だけが空リスト | 偽 |
| ５番目 | carは両方ともアトム | (car l1)と(car l2)が等しく、残りのリスト同士が等しければ真 |
| ６番目、８番目 | l1、l2の片方だけのcarがアトム | 偽 |
| ９番目 | l1、l2両方ともリストのリスト | (car l1)と(car l2)が等しく、残りのリスト同士が等しければ真 |
条件式をまとめた定義で評価してみる。
> (let ((l1 '(strawberry ice cream)) (l2 '(strawberry ice cream))) (eqlist? l1 l2)) #t > (let ((l1 '(strawberry ice cream)) (l2 '(strawberry cream ice))) (eqlist? l1 l2)) #f > (let ((l1 '(beef ((sawsage)) (and (soda)))) (l2 '(beef ((salami)) (and (soda))))) (eqlist? l1 l2)) #f > (let ((l1 '(beef ((sausage)) (and (soda)))) (l2 '(beef ((sausage)) (and (soda))))) (eqlist? l1 l2)) #t >
equal?
eqlist?の時と同じく引数の状態の組み合わせで４つの質問をする。
| 第１引数 | 第２引数 | 判定または処理 | |
|---|---|---|---|
| 1 | アトム | アトム | eqan?で比較 |
| 2 | アトム | （S式のリスト） | 偽 |
| 3 | （S式のリスト） | アトム | 偽 |
| 4 | （S式のリスト） | S式のリスト | eqlist?で比較 |
eqlist?の時と同じく上から評価して行くので（）の条件は省略可能。
equal?は再帰していない。比較対象の種類に寄ってeqan?とeqlist?を使い分けているだけ。
逆にeqlist?の５番目と９番目の条件に当てはまった場合の比較処理（アトム同士あるいはリスト同士）はequal?でまとめる事が出来る。ただし、(cdr l1)と(cdr l2)はアトムにはなり得ないので、比較にはequal?を適用せずに直接eqlist?を適用している。equal?を適用しても（atom?を適用する分無駄だが）結果は同じ筈。
６番目と８番目の条件はequal?の２番目の条件に相当するので、これもまとめる事が出来る。
equal?はDrRacketでは組み込み関数なので、別な適当な名前で定義してそれを使ってeqlist?を書き直し、評価してみる。
> (let ((l1 '(strawberry ice cream)) (l2 '(strawberry ice cream))) (eqlist? l1 l2)) #t > (let ((l1 '(strawberry ice cream)) (l2 '(strawberry cream ice))) (eqlist? l1 l2)) #f > (let ((l1 '(beef ((sawsage)) (and (soda)))) (l2 '(beef ((salami)) (and (soda))))) (eqlist? l1 l2)) #f > (let ((l1 '(beef ((sausage)) (and (soda)))) (l2 '(beef ((sausage)) (and (soda))))) (eqlist? l1 l2)) #t >
rember
最初の定義は(car l)がアトムの場合とリストの場合に分けてある。でも条件式もその後の式も全く同じなので纏める事が出来る。
実行例がないが最後の簡略化された定義を評価してみる。
> (rember 'a '(c d f e a c d)) (c d f e c d) > (rember '(1 2 3) '(3 4 (5 6) (1 2 3) 2 5)) (3 4 (5 6) 2 5) > (rember '(1 2 3) '(((1 2 3) 2 3) 2 3)) (((1 2 3) 2 3) 2 3) >
中に含まれているリストも取り除かれているが、１段目の要素としてのリスト以外は取り除かないので名前にスター＊は付かない。
