第7章:友達と親類
set?
(define (set? lat)
(cond [(null? lat) #t]
[(member? (car lat) (cdr lat)) #f]
[else (set? (cdr lat))]))
lat が重複要素を持たない(= セットかどうか)かを調べる関数。
前章までですでに定義した手続き member? を利用する。
makeset
(define (makeset lat)
(cond [(null? lat) '()]
[(member? (car lat) (cdr lat)) (makeset (cdr lat))]
[else (cons (car lat) (makeset (cdr lat)))]))
(define (makeset lat)
(cond [(null? lat) '()]
[else (cons (car lat)
(makeset (multirember (car lat) (cdr lat))))]))
makeset の2つのバリエーション。
member? を使うか multirember を使うかでリスト内の要素の順序が変わる。
機能は同じだけど実装が異なるという話。
subset?
(define (subset? set1 set2)
(cond [(null? set1) #t]
[else (and (member? (car set1) set2)
(subset? (cdr set1) set2))]))
set1 が set2 の部分集合かどうかを調べる関数。
and をうまく使うと短く書ける。
eqset?
(define (eqset? set1 set2)
(and (subset? set1 set2) (subset? set2 set1)))
set1 と set2 が等しい集合かどうかを調べる関数。
subset? を使うとうまく簡潔に書ける。
intersect?
(define (intersect? set1 set2)
(cond [(null? set1) #f]
[else (or (member? (car set1) set2)
(intersect? (cdr set1) set2))]))
二つの集合に共通部分があるかどうかを調べる関数。
set1 の要素が1つでも set2 にあったら true となる。
intersect
(define (intersect set1 set2)
(cond [(null? set1) '()]
[(member? (car set1) set2)
(cons (car set1) (intersect (cdr set1) set2))]
[else (intersect (cdr set1) set2)]))
二つの集合の積集合を得る関数。
union
(define (union set1 set2)
(cond [(null? set1) set2]
[(member? (car set1) set2)
(union (cdr set1) set2)]
[else (cons (car set1) (union (cdr set1) set2))]))
二つの集合の和集合を得る関数。
実装としてはちょうど intersect の反対のような処理を行う。
intersectall
(define (intersectall l-set)
(cond [(null? (cdr l-set)) (car l-set)]
[(intersect (car l-set) (intersectall (cdr l-set)))]))
集合のリストからすべての集合の積集合を得るための関数。
リスト内のそれぞれの集合に intersect を再帰的に適用する。
もし、集合 A、B、C、D があったら、
(intersect A (intersect B (intersect C (intersect D))))
と適用していくイメージ。((intersect D) = D である)
a-pair?
(define (a-pair? x)
(cond [(atom? x) #f]
[(null? x) #f]
[(null? (cdr x)) #f]
[(null? (cdr (cdr x))) #t]
[else #f]))
対象がペアかどうかを調べる関数。
ペアとは Lisp における対ではなくて、要素がふたつのリストという意味。
fun?
(define (fun? rel)
(cond [(null? rel) #t]
[else (set? (firsts rel))]))
対象の関係(rel)が関数であるかどうかを調べる。
関数であるためには、入力(第一要素)が重複してないことが条件。
revrel
(define (revrel rel)
(cond [(null? rel) '()]
[else (cons
(build (second (car rel))
(first (car rel)))
(revrel (cdr rel)))]))
対象の関係(rel)を逆にする関数。
第一要素と第二要素を入れ替えて、リストを構築し直す。
fulfun?
(define (fullfun? rel)
(cond [(null? rel) #t]
[else (set? (seconds rel))]))
第二要素に重複がないかどうかを調べる関数。
one-to-one?
(define (one-to-one? rel)
(fun? (revrel fun)))
full-fun? を fun? と revrel を使って書き直した関数。
one-to-one は単射の意味(だと思う)。
感想
集合の操作がメイン。難しいところはそんなになかったかな。
最近、進捗があまりよくないなぁ。
次章からが本番な気がする。