]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex2_60.rkt
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / 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