理系学生日記

おまえはいつまで学生気分なのか

問題2-59 (2.3.3 Example: Representing Sets)

抽象化はとても大事、という例がどんどん出てくるんですけど、2.3.3は集合をどう抽象化するか、という話みたいです。まずは単にリストで表現すればいいんじゃね?というところなんですけど、クソ効率が悪いという旨も書いてある。
とりあえずリスト表現で頑張ると、unionはこんな感じだとおもいます。

(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 '(e d c b a z) '(a b c f g)) ; (f g e d c b a z)
(union-set '(a b c f g) '(e d c b a z)) ; (f g e d c b a z)