Solution to Abstraction and Structure Definitions

WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.

1. A mathematical set will be implemented by using a defstruct structure.  The elements of the set will be stored in a list within a slot, and the cardinality will be stored in another slot.

   (defstruct <set> (elts <list>) (card <integer>))

2. (define empty-set (make-set empty 0))

3. (define (cardinality s) (get-set-card s))

4. (define (set-member? i s)
     (member i (get-set-elts s)))

5. (define (set-insert i s)
     (if (member i s) 
         s 
         (make-set (cons i (get-set-elts s))
                   (1+ (get-set-card s)))))

6. (define (set-union s1 s2)
     (if (= 0 (cardinality s1)
         s2
         (set-union (make-set (tail (get-set-elts s1))
                              (1- (cardinality s1)))
                    (set-insert (head (get-set-elts s1)) s2))))

Question

Return to CS 212 Prelim 1 - Spring 1999