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. In this part 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.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called sets.scm.