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

集合演算の続きです。

ノート：

intersect?

「積集合が存在している」と言う述語。

1. set1が空なら偽
2. set1の先頭要素がset2に含まれれば真
3. そうでなければ、set1の残りリストとset2に積終業が存在しているかに依存する。

set1が空の時の関数値が、最初の定義ではnil、２番目が#f、３番目がまたnil。述語なので#fが正しい。nilの部分は改訂漏れと思われる。

> (let ((set1 '(stewed tomatoes and macarino))
        (set2 '(macaroni and cheese)))
    (intersect? set1 set2))
#t
> 

「条件が成り立てば#t、成り立たなければelse節の関数の結果に依存」の状況ではorで纏める事が出来ると言う例。
orで条件を纏めた定義でも確認する。

> (let ((set1 '(stewed tomatoes and macarino))
        (set2 '(macaroni and cheese)))
    (intersect? set1 set2))
#t
> 

#fになるケースが

> (intersect? '(1 2 3) '(a b c))
#f
> (intersect? '() '(a b c))
#f
> (intersect? '(1 2 3) '())
#f
> 

subset?と比較すると

1. set1が空の時の結果が逆
2. subse?ではset1のcarが常にset2に含まれている間再帰し続けるが、intersect?では全く逆でset1のcarがset2に含まれていない間再帰を続ける。

intersect

これは積集合を意味する。

1. set1が空であれば（交わりは無いので）空リスト
2. set1の先頭がset2に含まれる場合、set1の先頭をset1の残りとset2の積集合に加えた集合
3. set1の先頭がset2に含まれていない場合、set1の残りとset2の積集合

示されている例と、積集合が空となるケースを試す。

> (let ((set1 '(stewed tomato and macaroni))
        (set2 '(macaroni and cheese)))
    (intersect set1 set2))
(and macaroni)
> (intersect '(1 2 3) '(a b c))
()
> (intersect '() '(a b c))
()
> (intersect '(1 2 3) '())
()
> 

union

和集合を意味する。

1. set1が空であればset2そのもの
2. set1の先頭がset2に含まれている場合、（それを結果に足す必要は無いので）set1の残りとset2の和集合
3. set1の先頭がset2に含まれていない場合、set1の先頭をset1の残りとset2の和集合に加えた集合

示されている例と空集合のケースを試す。

> (let ((set1 '(stewed tomatoes and macaroni casserole))
        (set2 '(macaroni and cheese)))
    (union set1 set2))
(stewed tomatoes casserole macaroni and cheese)
> (union '(1 2 3) '())
(1 2 3)
> (union '() '(a b c))
(a b c)
> (union '() '())
()
> 

xxx

定義は

1. set1が空の場合、空集合
2. set1の先頭要素がset2に含まれる場合、set1の残り集合とset2にxxxを適用した集合
3. set1の先頭要素がset2に含まれない場合、set1の先頭要素をset1の残り集合とset2にxxxを適用した集合に加えた集合

再帰の最後にset1が空になった時にset2ではなく空リストが返るので、set2は結果には含まれない。結果に含めるのはset2に含まれないset1の要素。set1-set2の差集合を意味する。
適当な例で評価してみる。

> (let ((set1 '(a 1 b 2 c 3 d 4))
        (set2 '(1 2 3 4 5 6)))
    (xxx set1 set2))
(a b c d)
> 

intersectall

二つ以上の集合の積集合を意味する。

1. 集合が一つしかなければ、その集合と定義する
2. 集合が複数ある場合は、最初の集合と残り全ての積集合との積集合

> (let ((l-set '((a b c) (c a d e) (e f g h a b))))
    (intersectall l-set))
(a)
> (let ((l-set '((6 pears and) (3 peaches and 6 peppers) (8 pears and 6 plums) (and 6 prunes with lots of apples))))
    (intersectall l-set))
(6 and)
>