(define-struct pr (fst snd)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; INTERFACE Set ;; lst->set : [Listof X] -> [Set X] ;; create a set from the given list of objects ;; contains? : [Set X] X -> Boolean ;; is elt a member of set? ;; add-elt : [Set X] X -> [Set X] ;; create a set from the given set and object ;; union : [Set X] [Set X] -> [Set X] ;; create the set that contains the elements of both ;; intersect : [Set X] [Set X] -> [Set X] ;; create the set that contains the elements ;; that the two sets share ;; cartesian : [Set X] [Set Y] -> [Set (make-pr X Y)] ;; create all possible (make-pr .. ..) of elements from ;; set1 and set2 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; A [Set X] is [List-of X] ;; where order does not matter and duplicates ARE allowed #| Alternate data definition for [Set X]: [Set X] = [List-of X] where order does not matter and duplicates are NOT allowed |# ;; lst->set : [List-of X] -> [Set X] ;; create a set from the given list of objects (define (lst->set lox) lox) ;; contains? : [Set X] X -> Boolean ;; is elt a member of set? (define (contains? s elt) (ormap (lambda (y) (equal? y elt)) s)) ;; add-elt : [Set X] X -> [Set X] ;; create a set from the given set and object (define (add-elt s elt) (cons elt s)) ;; union : [Set X] [Set X] -> [Set X] ;; create the set that contains the elements of both (define (union s1 s2) (append s1 s2)) #| If duplicates were NOT allowed: (define (union s1 s2) (append (filter (lambda (x1) (not (contains? s2 x1))) s1) s2)) |# ;; intersect : [Set X] [Set X] -> [Set X] ;; create the set that contains the elements ;; that the two sets share (define (intersect s1 s2) (filter (lambda (x1) (contains? s2 x1)) s1)) ;; cartesian : [Set X] [Set Y] -> [Set (make-pr X Y)] ;; create all possible (make-pr .. ..) of elements from ;; set1 and set2 (define (cartesian s1 s2) (apply append (map (lambda (x1) (map (lambda (x2) (make-pr x1 x2)) s2)) s1))) (define evens (lst->set '(2 4 6 8 0)))