SICP 問題2.59（union-setを定義）

問題

集合の順序づけられないリスト表現で union-set 演算を実装せよ。

解答

性能はさておき。

set1とset2をひとつのリストにまとめて考えた方がわかりやすいのでそうしちゃう。
まとめたリストを src、解答となる和集合を ans とすると、こんな感じ。

(define (union-set set1 set2)
  (let loop ((ans '())
	     (src (append set1 set2))) ;set1とset2をまとめちゃう。
    (cond ((null? src)
	   (reverse ans))
	  ((element-of-set? (car src) ans)
	   (loop ans (cdr src)))
	  (else
	   (loop (cons (car src) ans)
		 (cdr src))))))
		  

では今までの手続きも含めて実験を。

gosh> (define set1 '(1 2 3 4 5 6 7 8 9))

set1

gosh> (define set2 '(2 4 6 7 8 9 10 12))

set2

gosh> (element-of-set? 4 set1)

#t

gosh> (element-of-set? 0 set1)

#f

gosh> (element-of-set? 10 set1)

#f

gosh> (element-of-set? 9 set1)

#t

gosh> (intersection-set set1 set2)

(2 4 6 7 8 9)

gosh> (union-set set1 set2)

(1 2 3 4 5 6 7 8 9 10 12)

gosh> 

反復でやってみたけど再帰でもやってみよう。

(define (union-set set1 set2)
  (cond ((null? set1) set2)
	((element-of-set? (car set1) set2)
	 ;set2にあるなら最後にこの要素を含んでいるset2が返るんだからconsしない。
	 (union-set (cdr set1) set2))
	(else
	 ;set1にしかないなら cons しておかないとね。
	 (cons (car set1)
	       (union-set (cdr set1) set2)))))

実験。

gosh> (union-set set1 set2)

(1 2 3 4 5 6 7 8 9 10 12)

gosh> 

おけ。
なんとなく、和集合についてはこっちの方が効率がいいような気が。。
う〜ん、ここら辺の疑問を解消するための１章だと思うんだけどよくわかってねぇっす。