SICP 問題 2.62（順序づけられた集合に対する union-set を定義）

問題

順序づけられたリストによる集合表現の union-set を、Θ(n) で実装せよ。

解答

intersection-set と同じ感じでやってみよう。

(define (union-set set1 set2)
  (cond ((null? set1)
	 set2)
	((null? set2)
	 set1)
	(else
	 (let ((x1 (car set1))
	       (x2 (car set2)))
	   (cond ((= x1 x2)
		  ;重複を許すつもりで、２つとも挿入しとる。
		  (cons x1 (cons x2 (union-set (cdr set1) (cdr set2)))))
		 ((< x1 x2)
		  ;x1の方が小さいのでそいつを挿入し、set1のみ残りの要素を集合としてで再帰処理。
		  (cons x1 (union-set (cdr set1) set2)))
		 (else ;(< x2 x1)
		  ;x2、set2 の組み合わせで前の条件と同じことをするだけさ。
		  (cons x2 (union-set set1 (cdr set2)))))))))

んでは実験。

gosh> (union-set '() '())

()

gosh> (union-set '(1 2 3) '())

(1 2 3)

gosh> (union-set '() '(1 2 3))

(1 2 3)

gosh> (union-set '(1 2 3) '(5 6 7))

(1 2 3 5 6 7)

gosh> (union-set '(1 2 3 4 5 6) '(2 3 5))

(1 2 2 3 3 4 5 5 6)

gosh> (union-set '(2 4 5) '(1 2 3 4 5 6))

(1 2 2 3 4 4 5 5 6)

gosh> (union-set '(1 2 4 5) '(3 4 5 6))

(1 2 3 4 4 5 5 6)

gosh> (union-set '(1 3 5 7) '(2 4 6 8))

(1 2 3 4 5 6 7 8)

gosh> 

よぉ〜し、これもおっけ〜。