In Scheme sets can be represented as lists. However, unlike lists, the order of values in a set is not significant. Thus both (1 2 3) and (3 2 1) represent the same set.
(a) Write a Scheme function (set-equal? S1 S2) that tests whether S1 and S2 (represented as lists) are equal. Two sets are equal if they contain exactly the same members, ignoring ordering. You may assume that sets contain only atomic values (numbers, string, symbols, etc.) For example
(set-equal? '(1 2 3) '(3 2 1)) ---> #t (set-equal? '(1 2) '(3 2 1)) ---> #f (set-equal? '(susan john lyta) '(lyta john susan)) ---> #t
You may assume that no sets contain duplicate members.
(b) Two common operations on sets are union and intersection. The union of two sets is the set of all elements that appear in either set (with no repetitions). The intersection of two sets is the set of elements that appear in both sets.
Write Scheme functions (union S1 S2) and (intersect S1 S2) that implement set union and set intersection. You may again assume that set elements are always atomic, and that there are no duplicates. For example
(union '(1 2 3) '(3 2 1)) ---> (1 2 3) (union '(1 2 3) '(3 4 5)) ---> (1 2 3 4 5) (union '(a b c) '(3 2 1)) ---> (a b c 1 2 3) (intersect '(1 2 3) '(3 2 1)) ---> (1 2 3) (intersect '(1 2 3) '(4 5 6)) ---> () (intersect '(1 2 3) '(2 3 4 5 6)) ---> (2 3)
The ordering of the elements in your answer may differ from the above.
(c) In general sets can contain other sets. Extend your solution to parts (a) and (b) to allow sets to contain other sets. For example:
(set-equal? '(1 (2 3)) '((3 2) 1)) ---> #t (set-equal? '(1 2 3) '((3 2) 1)) ---> #f (set-equal? '(1 2 3) '((1 2 3))) ---> #f (union '(1 (2) 3) '(3 2 1)) ---> (1 2 3 (2)) (union '((1 2 3)) '((3 4 5))) ---> ((1 2 3) (3 4 5)) (union '((1 2 3)) '((3 2 1))) ---> ((1 2 3)) (intersect '((1 2 3)) '((3 2 1))) ---> ((1 2 3)) (intersect '((1 2 3)) '((4 5 6))) ---> () (intersect '((1) (2) (3)) '((2) (3) (4))) ---> ((2) (3))
Make sure to test additional cases of sets containing sets containing sets, etc.
You should only turn in the code you write for part (c) if you succeed. Otherwise, turn in your code for parts (a) and (b) for functions that you were unable to make work in part (c). Indicate in program comments what level of functionality you were able to achieve.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called sets.rkt.