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) ...)
add-element	Set Anything -> Set
	create a set that contains x and all the elements in s and
	(define (add-element 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:

1. Let Set = [Listof Anything] without repetition. Design all of the above functions. Make up your own favorite representation of pairs.
2. Let Set = [Anything -> Boolean]. Design all of the above functions. Use the same test suite for both implementations.
3. Add test cases that show how the function-based representation can deal with larger sets than the list-based one.
4. Add test cases that show how the list-based representation can deal with lists that do contain the same element more than once.
5. 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 cross-product 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 (build-list N xxx)))
             (define the-set (list-ref lst* (random N))))
       (time (contains the-set element))))
   
   (test some-set another-set some-element X)
   
   

   A report consists of the following items: computer (Dell Pentium II, Mac OS 9 PPC, etc); memory; version of drscheme; times reported.