Your task is to implement a set data structure in Scheme . A set is an unordered

Question

Your task is to implement a set data structure in Scheme.

A set is an unordered collection of unique elements. Elements may be numbers, characters or strings. Elements of a set do not need to have the same type.

You will define the following functions:

(empty? s): return #t if s is an empty set and #f otherwise.

(set s): return a list representation of a set where each element appears once. The order is not relevant.

(in? e s): return #t if the element e is in the set s, #f otherwise.

(add e s): return a new set that contains all the elements in s and the element e.

(discard e s): return a new set that contains all the elements in s other than e. If e is not in s, discard returns s.

(union s1 s2): return a new set that contains all the elements in s1 and all the elements of s2. The new set does not contain duplicates.

(intersection s1 s2): return a new set that contains all the elements that appear in both sets.

(difference s1 s2):  return a new set that contains all the elements in s1 that are not in s2.

(symmetric-difference s1 s2): return a new set with elements in either s1 or s2 but not both.

(subset? s1 s2): return #t if every element of s1 is in s2, #f otherwise.

(superset? s1 s2): return #t if every element of s2 is in s1, #f otherwise.

(disjoint? s1 s2): return #t if s1 and s2 have no elements in common, #f otherwise.

(sameset? s1 s2): return #t if s1 and s2 have the same elements, #f otherwise. The order is not relevant.

A racket definition template that includes some test code is available for your convenience: sets.rkt

SETS.RKT CODE:

(define (empty? s)
'enter-your-code-here
)

(define (set s)
'enter-your-code-here
)

(define (in? e s)
'enter-your-code-here
)

(define (add e s)
'enter-your-code-here
)

(define (discard e s)
'enter-your-code-here
)   

(define (union s1 s2)
'enter-your-code-here
)

(define (intersection s1 s2)
'enter-your-code-here
)

(define (difference s1 s2)
'enter-your-code-here
)

(define (symmetric-difference s1 s2)
'enter-your-code-here
)

(define (subset? s1 s2)
'enter-your-code-here
)
  
(define (superset? s1 s2)
'enter-your-code-here
)

(define (disjoint? s1 s2)
'enter-your-code-here
)

(define (sameset? s1 s2)
'enter-your-code-here
)

SOME TESTS:

(define A (set '(1 2 7 9 7 1)))
(define B (set '(2 0 8 0 7 12)))
(define C (set '(9 7)))

(define colors (set '("yellow" "red" "green" "blue" "orange" "purple" "pink")))
(define rgb (set '("red" "green" "blue")))

(define hi (set '(#h #i)))

(isempty? A) ; #f
(isempty? rgb) ;#f
(isempty? (set'())) ;#t

(isin? 0 A) ; #f
(isin? "red" A); #f
(isin? 2 A) ; #t

(isin? "green" rgb) ; #t
(isin? "purple" rgb) ; #f
(isin? "i" hi) ;#f
(isin? #i hi) ;#t

(add 9 A) ; (2 9 7 1)
(add 5 A) ; (5 2 9 7 1)

(discard 1 A) ; (2 9 7)
(discard 5 A) ; (2 9 7 1)
(union A B) ; (9 1 2 8 0 7 12)
(union A rgb) ; (2 9 7 1 "red" "green" "blue")

(intersection A rgb) ; ()
(intersection A B) ; (2 7)
(intersection rgb colors) ; ("red" "green" "blue")

(difference A B) ; (9 1)
(difference rgb colors) ; ()
(difference colors rgb) ; ("yellow" "orange" "purple" "pink")

(symmetric-difference A B) ; (9 1 8 0 12)
(symmetric-difference A C) ; (2 1)
(symmetric-difference colors rgb) ; ("yellow" "orange" "purple" "pink")

(issubset? A B) ;#f
(issubset? C A) ; #t

(issubset? colors rgb) ;#f
(issubset? rgb colors) ; #t

(issuperset? A B) ;#f
(issuperset? A C) ; #t

(issuperset? colors rgb) ;#t
(issuperset? rgb colors) ; #f

(isdisjoint? B C) ;#f
(isdisjoint? colors A) ;#t

(issameset? (set '(9 1 2 7)) A); #t
(issameset? B A) ; #f

Explanation / Answer

(define (empty? s) (if (null? s) #t #f))
(define (in? e s) (if (empty? s) #f (if (equal? e (car s)) #t (in? e (cdr s)))))
(define (set l) (if (empty? s) '() (if (not (in? (car s) (cdr s))) (cons (car s) (set (cdr s))) (set (cdr s)))));;; l is list not set
(define (add e s) (cons e s))
(define (discard e s) (if (empty? s) '() (if (equal? e (car s)) (cdr s) (cons (car s) (discard e (cdr s))))))

(define (union s1 s2) (if (empty? s1) s2 (if (in? (car s1) s2) (union (cdr s1) s2) (cons (car s1) (union (cdr s1) s2)))))

(define (intersection s1 s2) (if (empty? s1) '() (if (in? (car s1) s2) (cons (car s1) (intersection (cdr s1) s2)) (intersection (cdr s1) s2))))

(define (difference s1 s2) (if (empty? s1) '() (if (not (in? (car s1) s2)) (cons (car s1) (difference (cdr s1) s2)) (difference (cdr s1) s2))))

(define (symmetric-difference s1 s2) (difference (union s1 s2) (intersection s1 s2)))
(define (subset? s1 s2) (if (empty? s1) #t (if (not (in? (car s1) s2)) #f (subset? (cdr s1) s2))))
(define (superset? s1 s2) (if (empty? s2) #t (if (not (in? (car s2) s1)) #f (superset? s1 (cdr s2)))))
(define (disjoint? s1 s2) (if (empty? (intersection s1 s2)) #t #f))
(define (sameset? s1 s2) (if (and (empty? (difference s1 s2)) (empty? (difference s2 s1))) #t #f))

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.