Your task is to implement a set data structure in Scheme . A set is an unordered
ID: 3859792 • Letter: Y
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
SETS.RKT CODE:
(define (empty? s)-> boolean?
s: generic-set?
)// Returns #t if s is empty else #f
(define (set s)->generic-set?
s: generic-set?
)// Lists sets elements
(define (in? e s)->boolean?
s:generic-set?
e:any/c
)// Returns #t if e is in s else #f
(define (add e s)-generic-set?
s:generic-set?
e: any/c
). //Produces set s with e
(define (discard e s)->generic-set?
s: generic-set?
e: any/c
) //Produces all elements in s except e
(define (union s1 s2)->generic-set?
s1: generic-set?
s2:generic-set?
)// Returns a set s1 which contains elements of both s1and s2
(define (intersection s1 s2)->generic-set?
s1: generic-set?
s2: generic-set?
)// Returns elements of s1 which are also present in s2
(define (difference s1 s2)->generic-set?
s1: generic-set?
s2: generic-set?
)// Returns elements of s1 that are not contained in s2
(define (symmetric-difference s1 s2)->generic-set?
s1: generic-set?
s2: generic-set?
)// Produces set of same type of s1 that contains all of the elements contained an odd never of times in s2
(define (subset? s1 s2)->boolean?
s1: generic-set?
s2: generic-set?
)// Returns #t if each element of s2 also present in s1 else #f
(define (superset? s1 s2)->boolean?
s1: generic-set?
s2: generic-set?
)//Returns #t if s1 is superset of all the other sets otherwise#f
(define (disjoint? s1 s2)->boolean?
s1: generic-set?
s2: generic-set?
)// Returns #t if s1 and s2 contains all the mismatch elements otherwise #f
(define (sameset? s1 s2)->boolean?
s1: generic-set?
s2: generic-set?
)// Returns #t if s1 and s2 are same otherwise #f
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.