1 665c255d 2023-08-04 jrmu (define (test-case actual expected)
3 665c255d 2023-08-04 jrmu (display "Actual: ")
4 665c255d 2023-08-04 jrmu (display actual)
6 665c255d 2023-08-04 jrmu (display "Expected: ")
7 665c255d 2023-08-04 jrmu (display expected)
11 665c255d 2023-08-04 jrmu (define (element-of-set? x set)
12 665c255d 2023-08-04 jrmu (cond ((null? set) false)
13 665c255d 2023-08-04 jrmu ((equal? x (car set)) true)
14 665c255d 2023-08-04 jrmu (else (element-of-set? x (cdr set)))))
15 665c255d 2023-08-04 jrmu (define (adjoin-set x set)
16 665c255d 2023-08-04 jrmu (if (element-of-set? x set)
18 665c255d 2023-08-04 jrmu (cons x set)))
19 665c255d 2023-08-04 jrmu (define (intersection-set set1 set2)
20 665c255d 2023-08-04 jrmu (cond ((or (null? set1) (null? set2)) '())
21 665c255d 2023-08-04 jrmu ((element-of-set? (car set1) set2)
22 665c255d 2023-08-04 jrmu (cons (car set1)
23 665c255d 2023-08-04 jrmu (intersection-set (cdr set1) set2)))
24 665c255d 2023-08-04 jrmu (else (intersection-set (cdr set1) set2))))
25 665c255d 2023-08-04 jrmu (define (union-set set1 set2)
26 665c255d 2023-08-04 jrmu (cond ((null? set1) set2)
27 665c255d 2023-08-04 jrmu ((null? set2) set1)
28 665c255d 2023-08-04 jrmu ((element-of-set? (car set1) set2) (union-set (cdr set1) set2))
29 665c255d 2023-08-04 jrmu (else (cons (car set1) (union-set (cdr set1) set2)))))
31 665c255d 2023-08-04 jrmu (test-case (union-set '(1 2 3 4 5) '(1 3 4)) '(2 5 1 3 4))
33 665c255d 2023-08-04 jrmu ;; Exercise 2.60. We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?
35 665c255d 2023-08-04 jrmu (define (element-of-set? x set)
36 665c255d 2023-08-04 jrmu (cond ((null? set) #f)
37 665c255d 2023-08-04 jrmu ((equal? x (car set)) #t)
38 665c255d 2023-08-04 jrmu (else (element-of-set? x (cdr set)))))
39 665c255d 2023-08-04 jrmu (test-case (element-of-set? 4 '(1 3 5 2 3 5 5)) #f)
40 665c255d 2023-08-04 jrmu (test-case (element-of-set? 3 '(1 3 5 2 3 5 5)) #t)
42 665c255d 2023-08-04 jrmu (define (adjoin-set x set)
43 665c255d 2023-08-04 jrmu (cons x set))
45 665c255d 2023-08-04 jrmu (test-case (adjoin-set 5 '()) '(5))
46 665c255d 2023-08-04 jrmu (test-case (adjoin-set 5 '(1 3)) '(5 1 3))
47 665c255d 2023-08-04 jrmu (test-case (adjoin-set 5 '(5 5 1 3)) '(5 5 5 1 3))
49 665c255d 2023-08-04 jrmu (define (union-set set1 set2)
50 665c255d 2023-08-04 jrmu (append set1 set2))
52 665c255d 2023-08-04 jrmu (test-case (union-set '(1 5 2 3 5) '(4 2 8 1 5)) '(1 5 2 3 5 4 2 8 1 5))
54 665c255d 2023-08-04 jrmu (define (intersection-set set1 set2)
55 665c255d 2023-08-04 jrmu (cond ((null? set1) set2)
56 665c255d 2023-08-04 jrmu ((null? set2) set1)
57 665c255d 2023-08-04 jrmu ((element-of-set? (car set1) set2)
58 665c255d 2023-08-04 jrmu (cons (car set1) (intersection-set (cdr set1) set2)))
59 665c255d 2023-08-04 jrmu (else (intersection-set (cdr set1) set2))))
61 665c255d 2023-08-04 jrmu (test-case (intersection-set '(1 5 2 3 5) '(4 2 8 1 5)) '(1 5 2 5 4 2 8 1 5))
63 665c255d 2023-08-04 jrmu ;; the new set has a lot of duplicated entries so that element-of-set? and
64 665c255d 2023-08-04 jrmu ;; intersection-set are much slower. The more duplicate entries, the slower
65 665c255d 2023-08-04 jrmu ;; they become. However, adjoin-set and union-set become extremely easy and
66 665c255d 2023-08-04 jrmu ;; fast to implement. You might use this representation when it is more
67 665c255d 2023-08-04 jrmu ;; important to be able to join two sets or add new elements to a set
68 665c255d 2023-08-04 jrmu ;; than it is to see if an element belongs to a set or is part of an
69 665c255d 2023-08-04 jrmu ;; intersection of two sets.
