Scheme手習い　第７章　友達と親類（その１）

リストを使った集合演算を習います。

ノート：

set?

「（与えられたリストが）集合である（重複が無い）」と言う述語

latが空リストであれば真（確かに重複は無い）
latの先頭要素がlatの残りリストに含まれていれば偽
そうでなければlatの残りリストが集合であるかに依存する

はい、member?はeq?ではなくequal?を使って書かれていますから。

95ページでequal?が登場して以来member?は登場していない。ここでは「eq?ではなくequal?を使ったmember?を使っているので」と解釈する。DrRacketでは数字もシンボルもeq?が使えるので特に問題無し。リストを要素とする集合では問題あり。

23ページのeq?を使ったmember?を使ったset?を評価する。

> (set? '(apple paeches apple plum))
#f
> (let ((lat '(apple peaches pears plums)))
    (set? lat))
#t
> (set? '(apple 3 pear 4 9 apple 3 4))
#f
> (set? '(apple 3 pear 4 9))
#t
> (set? '((1 2 3) (a b c) (1 2 3)))
#t
>

eq?を使っている為、リストを要素とする集合には対応出来ていない。

equal?を使ったmember?に切り替えて評価してみる。

> (set? '(apple paeches apple plum))
#f
> (let ((lat '(apple peaches pears plums)))
    (set? lat))
#t
> (set? '(apple 3 pear 4 9 apple 3 4))
#f
> (set? '(apple 3 pear 4 9))
#t
> (set? '((1 2 3) (a b c) (1 2 3)))
#f
>

リストが要素になっていても対応出来る。

makeset

makeと言う極めて手続き的な名前だが、「与えられたリストの全ての要素を重複無く含む集合」を意味する。その集合は

リストが空であれば、空集合
リストの先頭要素が残りのリストに含まれていれば、残りのリストの全ての要素を含む集合
そうでなければ、リストの先頭要素を残りのリストの全ての要素を含む集合に加えた集合

示されているmakesetの定義は(car lat)が(cdr lat)に含まれる場合それを結果の集合には含めない事になるので、結果的には重複がある場合最後の要素が残る事になり、最初に示された例とは結果の順番が違って来る。

> (let ((lat '(apple peach pear peach plum apple lemon peach)))
    (makeset lat))
(pear plum apple lemon peach)
>

multiremberを使う場合、最初に出現した要素が結果に加えられ、以降の重複を全て無視するので結果は以下の通りとなる。

> (let ((lat '(apple peach pear peach plum apple lemon peach)))
    (makeset lat))
(apple peach pear plum lemon)
>

本では最初の定義の時の結果と変わっていないのでタイポと思われる。

> (makeset '(apple 3 pear 4 9 apple 3 4))
(apple 3 pear 4 9)
>

multiremberはeq?を使っているが正しい結果となる。引数のリストがリストを含んでいない限りeq?でも結果は変わらない。

> (makeset '(1 2 (a b) 3 4 (c d) 2 4 (a b) 4 5))
(1 2 (a b) 3 4 (c d) (a b) 5)
>

eq?を使っているため(a b)が重複したまま。equal?を使ったmultiremberに変えると以下の結果となる。

> (makeset '(1 2 (a b) 3 4 (c d) 2 4 (a b) 4 5))
(1 2 (a b) 3 4 (c d) 5)
>

正しく(a b)の重複がなくなる。

subset?

「ある集合が別の集合に含まれている」と言う述語。

set1が空リストであれば真（全てのリストは空リストを含んでいると解釈）
set1の先頭要素がset2に含まれていれば、set1の残り要素がset2に含まれているかに依存
そうでなければ偽

> (let ((set1 '(5 chicken wings))
        (set2 '(5 hambergers 2 pieces fried chicken and light duckling wings)))
    (subset? set1 set2))
#t
> (let ((set1 '(4 pounds of horseradish))
        (set2 '(four pounds chicken and 5 onces horseradish)))
    (subset? set1 set2))
#f
>

本では(four pounds chicken and5 ...)と5の前にスペースがないが、恐らくタイポだと判断した。

elseに抜けた時には#fと言うケースでは、その前の条件部と条件が成り立った時の式をandで繋いで元のelse節を省略可能である事が示されている。条件部が#fであればandの結果は#f（元のelse節に相当）だし、条件部が#tの場合は式部の結果がそのままその関数での結果となります。つまり

set1が空リストであれば真
命題「set1の先頭がset2に含まれている」かつ命題「set1の残りがset2に含まれている」の真偽値

> (let ((set1 '(5 chicken wings))
        (set2 '(5 hambergers 2 pieces fried chicken and light duckling wings)))
    (subset? set1 set2))
#t
>  (let ((set1 '(4 pounds of horseradish))
        (set2 '(four pounds chicken and 5 onces horseradish)))
    (subset? set1 set2))
#f
>

eqset?

「二つの集合は同じ要素から構成される」と言う述語

set1がset2に含まれていれば、set2がset1に含まれているかに依存
そうでなければ偽

> (let ((set1 '(6 large chickens with wings))
        (set2 '(6 chickens with large wings)))
    (eqset? set1 set2))
#t
>

再びandを使って最後のelseを省略する。つまり

set1がset2に含まれていて、かつset2もset1に含まれている

だけの条件となる。

最後の定義でもう一度評価してみる。

> (let ((set1 '(6 large chickens with wings))
        (set2 '(6 chickens with large wings)))
    (eqset? set1 set2))
#t
>

プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート