SICP 問題2.60（重複ありの集合について）

問題

集合を重複のないリストで表現しようとしてきた。重複が許されるとしよう。例えば集合 {1, 2, 3} はリスト (2 3 2 1 3 2 2) で表現されるかもしれない。
この表現を操作する手続き、 element-of-set?、adjoin-set、union-set、及び intersection-set を設計せよ。
重複なし表現の対応する手続きと比べて効率はどうなるか。
重複なし表現よりこの表現が使いたくなる応用はあるだろうか。

解答

まずは重複OKの集合に対する4種の手続を再定義してみる。
でも基本的に変更しなくても使えるっぽい。

;変更不要
(define (element-of-set? x set)
  (cond ((null? set)
	 #f)
	((equal? x (car set))
	 #t)
	(else
	 (element-of-set? x (cdr set)))))

;重複チェック不要なので素直に cons。
(define (adjoin-set x set)
  (cons x set))

;変更不要？
(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2))
	 '())
	((element-of-set? (car set1) set2)
	 (cons (car set1)
	       (intersection-set (cdr set1) set2)))
	(else
	 (intersection-set (cdr set1) set2))))

;単なる連結で和集合が求められる。（定義的には合ってるよね？）
(define (union-set set1 set2)
  (append set1 set2))

adjoin-set と union-set は効率よくなってると思うよ？
使いたくなる応用ねぇ〜。意味がいまいちよくわからん。。
だって重複があってもOKな集合を扱う現象なら重複なしの集合を扱うオペレーションは使えないじゃん。
ま、その場合「使いたくなる」じゃなくて「使わざるを得ない」ケースになっちゃうけど。