2.3.3 例:集合の表現、問題2.59 – SICP(計算機プログラムの構造と解釈)その71

2.3.3 例:集合の表現 – 順序づけられないリストとしての集合

intersection-set 手続き

  • set1set2 のいずれかが空集合ならば '() を返す。
  • set1 の最初の要素が set2 に含まれていれば、"set1 の最初の要素" と "set1 の残りの要素と set2 との積集合" とから成るリストを返す。
  • それ以外の場合は、set1 の残りの要素と set2 との積集合とから成るリストを返す。
(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)
  (if (element-of-set? x set)
      set
      (cons x set)))

(adjoin-set '1 '(2 3 4))
gosh> (1 2 3 4)
(adjoin-set '2 '(2 3 4))
gosh> (2 3 4)

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

(intersection-set '(1 2 3 4 5) '(2 3 6))
gosh> (2 3)

問題2.59

union-set 手続き

  • set1 が空集合ならば set2 を返す。
  • set2 が空集合ならば set1 を返す。
  • set1 の最初の要素が set2 に含まれていれば、set1 の残りの要素と set2 との和集合から成るリストを返す。
  • それ以外の場合は、"set1 の最初の要素" と "set1 の残りの要素と set2 との和集合" とから成るリストを返す。
(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 '(1 2 3 4 5) '(2 3 6))
gosh> (1 4 5 2 3 6)
(union-set '() '(2 3 6))
gosh> (2 3 6)
(union-set '(1 2 3 4 5) '())
gosh> (1 2 3 4 5)
(union-set '(1 2 3 4 5) '(1 2 3 4 5))
gosh> (1 2 3 4 5)
(union-set '(1 2 3 4 5) '(1 2 3 4 5 6))
gosh> (1 2 3 4 5 6)
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»