理系学生日記

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

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

要素数nに対して、\theta (n)でunionをとる。

 (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 (union-set (cdr set1) 
				      set2)))
		 ((= x1 x2)
		  (cons x1 (union-set (cdr set1)
				      (cdr set2))))
		 (else
		  (cons x2 (union-set set1
				      (cdr set2)))))))))
(union-set '(1 2 3 4 5 6) '(0 2 3 4 5)) ;(0 1 2 3 4 5 6)