理系学生日記

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

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

あんまし変わってないけど、重複を許す集合上の演算。

(define (element-of-set? x set)
  (cond ((null? set) #f)
	((equal? x (car set)) #t)
	(else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
	((element-of-set? (car set1) set2)
	 (cons (cdr set1)
	       (intersection-set (cdr set1) set2)))
	(else (intersection-set (cdr set1) set2))))

efficiencyつっても、adjoin-setとかunion-setとかは集合上を走査する必要はなくなったぽい。書くのは楽になったw
もちろん空間的な効率は下がってるかんじ