src/sicp/ex2_60.rkt

   1 #lang racket
   2
   3 (define (element-of-set? x set)
   4   (cond ((null? set) #f)
   5         ((equal? x (car set)) #t)
   6         (else (element-of-set? x (cdr set)))))
   7
   8 (define (adjoin-set x set)
   9   (cons x set))
  10
  11 (define (union-set set1 set2)
  12   (append set1 set2))
  13
  14 (define (intersection-set set1 set2)
  15   (cond ((or (null? set1) (null set2)) '())
  16         ((element-of-set? (car set1) set2) (cons (car set1) (intersection-set (cdr set1) set2)))
  17         (else (intersection-set (cdr set1) set2))))
  18
  19 #|
  20  union-set and adjoin-set has changed. Rest remain unchanged.
  21
  22  Performance while adding a new element is O(1). Same with union.
  23  intersection-set remains the same - O(m * n).
  24  element-of-set? also remains the same - O (n).
  25
  26 If duplicates are allowed, then Intersection and element-of-set? performance will degrade.
  27
  28 |#
  29
  30