; Functions that implement the set-of-integers type ; using an unordered list as the underlying representation. ; Each set thus represented has the symbol "list" ; as its first element and the set members as the ; remaining elements. ; Type name (define list-set-type 'list) ; Return the result of forming a set out of the given elements. (define (new-list-set elements) (tagged-datum list-set-type elements) ) ; Return true if x is in the set, false otherwise. (define (list-member? x set) (member x (contents set)) ) ; Return the result of adding x to the set. (define (list-with-element x set) (if (list-member? x set) set (tagged-datum list-set-type (cons x (contents set))) ) ) ; Return a list of the elements of the set. (define (list-elements set) (contents set) ) ; ***** ; Functions that implement the set-of-integers type using a ; sorted list of intervals as the underlying representation. ; Each set thus represented has the symbol "intvls" ; as its first element, with each remaining element being a ; two-element list representing all the integers between ; the car of the list and the cadr, inclusive. ; The intervals of integers are sorted, e.g. ; ((5 8) (10 10) (14 14) (100 104)) ; represent the set {5, 6, 7, 8, 10, 14, 100, 101, 102, 103, 104}. ; Moreover, consecutive intervals don't overlap. ; Type name. (define intvls-set-type 'intvls) ; Return the result of forming a set out of the given elements. (define (new-intvls-set elements) ... ) ; Return true if x is in the set, false otherwise. (define (intvls-member? x set) ... ) ; Return the result of adding x to the set. (define (intvls-with-element x set) ... ) ; Return a list of the elements of the set. (define (intvls-elements set) ... ) ; ***** ; Functions to implement tagged data. (define (tagged-datum type value) (cons type value) ) (define type car) (define contents cdr) ; ***** (define (new-set elements type) (cond ((equal? type list-set-type) (new-list-set elements)) ((equal? type intvls-set-type) (new-intvls-set elements)) (else (error "unknown initialization type: " type)) ) ) (define (member? x set) (cond ((list-set? set) (list-member? x set)) ((intvls-set? set) (intvls-member? x set)) (else (error "unknown type in member?: " (type set))) ) ) (define (with-element x set) (cond ((list-set? set) (list-with-element x set)) ((intvls-set? set) (intvls-with-element x set)) (else (error "unknown type in with-element: " (type set))) ) ) (define (elements set) (cond ((list-set? set) (list-elements x set)) ((intvls-set? set) (intvls-elements x set)) (else (error "unknown type in elements: " (type set))) ) ) (define (list-set? set) (equal? (type set) list-set-type) ) (define (intvls-set? set) (equal? (type set) intvls-set-type) ) ; ***** ; Utility functions. (define (find-if p L) (cond ((null? L) #f) ((p (car L)) (car L)) (else (find-if p (cdr L))) ) )