問題2-59〜60

集合に関する問題です。問題2-59のunion-setは以下のように実装しました。intersection-setにおけるelement-of-set?の使い方をちょっと変えるだけで表現することができます。

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else (cons (car set1)
                    (union-set (cdr set1) set2)))))

(union-set (list 1 2 3) (list 4 5 6))  ;=>(1 2 3 4 5 6)
(union-set (list 1 2 3) (list 2 3 4))  ;=> (1 2 3 4)
(union-set '(a b c) '(d e f))  ;=>(a b c d e f)
(union-set '(a d b) '(b c d))  ;=>(a b c d)

次の問題2-60ですが、集合の和や積を求める前に、それぞれの集合の重複を省いてやることで実現できそうです。

(define (remove-duplication set)
  (define (iter result tgt)
    (if (null? tgt)
        result
        (iter (union-set result tgt)
              (cdr tgt))))
  (iter '() set))

(remove-duplication (list 1 2 3 4 5 5 6))  ;=>(1 2 3 4 5 6)

集合のそれぞれの要素と結果リストでunion-setしているので、恐ろしく効率が悪くなってしまいそうです。また、上記の実装をunion-setに組み込んだところ、無限ループに陥ってしまいました。もっと良いやり方があるはずですが、この二つの問題で時間がかかりすぎてしまい埒があかなくなってきたので、次へ進んでしまいたいと思います。