第７章：友達と親類

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 の２つのバリエーション。 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 は単射の意味（だと思う）。

感想

集合の操作がメイン。難しいところはそんなになかったかな。

最近、進捗があまりよくないなぁ。

次章からが本番な気がする。

The King's Museum

ソフトウェアエンジニアのブログ。

Scheme 手習い（６）