Abstraction and Structure Definitions

Sets are an extremely useful abstraction to provide in any programming environment. In what follows, you will design and implement an integer set abstraction. You may use any implementation you like as long as it meets the specification provided below. You need not worry about bulletproofing your code nor the efficiency of your implementation except that the operation cardinality (described below) should run in O(1). (Hint: no definition requires more than 4-5 lines of code if you think about the implementation.)

The set abstraction should provide the following definitions:

• a new type <set>.
• a value empty-set of type <set> representing {} (the empty set of integers).
• a function (set-member? i S) which takes an <integer> i and a <set> S and returns #f if and only if iS (i.e., i is not in the set S.) If i is in S, then set-member? may return any value but #f.
• a function (set-insert i S) which takes any <integer> i and <set> S and returns a new <set> representing {i}S.
• a function (set-union S₁ S₂) which returns a <set> representing S₁S₂.
• a function (cardinality S) which returns the number i of unique integers appearing in the <set> S. That is, i = |S|.

1. Give a Scheme definition for the <set> type and explain in English how you will represent a mathematical set using your new type.
   
   
2. Give a Scheme definition for the empty-set.
   
   
3. Give a Scheme definition for cardinality such that (cardinality S) runs in time O(1) for any set S.
   
   
4. Give a Scheme definition for set-member?.
   
   
5. Give a Scheme definition for set-insert.
   
   
6. Give a Scheme definition for set-union.
   
   

Solution

Return to CS 212 Prelim 1 - Spring 1999