An important idea in program design is programming to interfaces. Someone will tell you that there is a
class of data, e.g., Set
, and then list the functions that are available for this class, e.g.,
contains  Set Anything > Boolean 
 does s contain x ? 
 (define (contains s x) ...) 

addelement  Set Anything > Set 
 create a set that contains
x and all the elements in s and 
 (define (addelement s x) ...) 

lst>set  [Listof Anything] > Set 
 create a set from the elements of l 
 (define (lst>set l) ...) 

union  Set Set > Set 
 create a set from all the elements
that are in s or t 
 (define (unions s t) ...) 

intersection  Set Set > Set 
 create a set from all the elements
that are in s and t 
 (define (intersection s t) ...) 

minus  Set Set > Set 
 create a set from all the elements
that are in s but not in t 
 (define (minus s t) ...) 

X  Set Set > Set 
 create the set that pairs all
elements from s with all elements from t 
 (define (X s t) ...) 
where Anything
is the class of all Scheme objects.
When someone else wants to program with sets, you tell them to use
the above conventions. You can implement (design) the data
representation and the interface functions in many different ways.
In class, we have discussed two distinct representations of sets:
lists and functions. The former are simple, the latter can represent
infinite sets. Your tasks are:

Let
Set = [Listof Anything] without repetition
. Design
all of the above functions. Make up your own favorite representation
of pairs.

Let
Set = [Anything > Boolean]
. Design all of the above
functions. Use the same test suite for both implementations.

Add test cases that show how the functionbased representation can
deal with larger sets than the listbased one.

Add test cases that show how the listbased representation can deal
with lists that do contain the same element more than once.
 Run the following stress tests on your two implementation of the
X
function and report your
results:
;; Set Set Anything [Set Set > Set] > Boolean
;; create the crossproduct X of set1 and set2,
;; then check whether element is in the result
(define (test set1 set2 element X)
(local ((define N 10000)
(define (xxx i) (X set1 set2))
(define lst* (time (buildlist N xxx)))
(define theset (listref lst* (random N))))
(time (contains theset element))))
(test someset anotherset someelement X)
A report consists of the following items: computer (Dell Pentium II, Mac OS 9 PPC, etc); memory; version of
drscheme; times reported.