# CSC 270

## Homework 4

assigned 3 Dec, due 12 Dec

Write a collection of Scheme functions to do set manipulation. Assume a
set is represented as a list of elements (some or all of which may
themselves be sets), with no element appearing more than once. Write
the following functions:
- element?

A predicate that tells whether a given object is an element of a given
set.

Example: `(element? 'c '(a b c e))` would return `#t`,
while `(element? 'c '(d e f))` would return `#f`.

(For extra credit, write this so that it correctly recognizes a set as
an element of a set of sets, e.g.
`(element? '(a b) '((a) (b c d) (b a) (c)))` would return
`#t` because the first argument, `(a b)`, is the same set as
`(b a)`, one of the elements of the second argument.
Hint: do this extra credit after writing
`equal-sets?`.)
- subset?

A predicate that tells whether one set is completely contained in
another.

Example: `(subset? '(a b c e) '(b f g c a e))` would return
`#t`, while
`(subset? '(a b c e) '(b f g c e))` would return `#f`
because `a` is an element of the first set but not of the second.
(If you do this right and do the extra-credit version of
`element?`, you'll get `subset?` to work correctly on
sets for free. Ditto all the rest of the functions.)
- equal-sets?

A predicate that tells whether two sets are equal.

Example: `(equal-sets? '(a b c e) '(c e a b))` would return
`#t`, while `(equal-sets? '(a b c d) '(c e a b))` would
return `#f`.
- union

The union of two sets is the set of things that appear in one, the
other, or both sets.

Example: `(union '(a b c d) '(c e f))` would return
`(a b c d e f)`.
- intersection

The intersection of two sets is the set of things that appear in both
sets.

Example: `(union '(a b c d) '(c e f))` would return
`(c)`.
- difference

The difference of two sets is the set of things that appear in the first
but not the second.

Example: `(difference '(a b c d) '(c e f))` would return
`(a b d)`.
- empty?

A predicate that tells whether something is the empty set.

Example: `(empty? '(a b c d))` would return `#f`, while
`(empty? (intersection '(a b c) '(d e f)))` would return
`#t`.
- set?

A predicate that tells whether something is a legal set,
i.e. whether each element of it appears at most once.

Example: `(set? '(a b c e))` would return `#t`, while
`(set? '(a b c b))` would return `#f` because the element
`b` appears more than once.
- make-set

A function which, given a list (not necessarily a set), returns the set
of its elements. In other words, `make-set` removes
duplications.

Example: `(make-set '(a b c b e c b))` would return
`(a b c e)` (or the same elements in some other order).

Please name the functions exactly as specified above, so I
can load your file and immediately start using and testing the functions.

Last modified:
Thu Dec 5 14:52:42 EST 1996
Stephen Bloch / sbloch@boethius.adelphi.edu