2006-04-29

順序づけられないリストとしての集合

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

ちなみに intersection = 「論理積」です。

(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 (list 1 2 3 5) (list 4 3 6))

問題2.59

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

結果

(use slib)
(require 'trace)
(trace union-set)
(trace element-of-set?)
(element-of-set? 1 (list 4 3 2 1))
(union-set (list 1 2 3 5) (list 4 6))
gosh>(1 2 3 5 4 6)

なんだかunion-set に1時間くらいかけてしまった。調子悪げ。

※「SICPを読もう」の目次はこちら