SICP問題2.60

• 順序づけられない重複ありのリストを操作する手続き

element-of-set?は変更なし

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

adjoin-set も変更なし

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

intersection-set

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

union-set

(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)))))

intersection-set, union-setに関してはset1に重複が存在するか、set2に重複が存在するかで結果が変わって来る気がするけど、どうするのが正しいのかなぁ?

• 重複なしの表現の対応する手続きと比べての効率はどうか?重複なし表現よりこの表現の方が使いたくなる応用はあるか?

重複ありの表現の方が効率は悪い。(メモリーも多く取るし、演算も時間がかかる)
重複有りの表現を使いたい場合は、リストの要素として何をしたのかを全て記録するようなアプリケーションの場合かなぁ。もっと良い方法はありそうな気がしますが。