;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; 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 (define-struct pr (fst snd)) ;; 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 [X -> Boolean] ;; represent set using characteristic function: ;; is a given elt in the set? ;; Examples ;; Now we can represent infinite sets, e.g., all even numbers (define evens (lambda (x) (and (number? x) (integer? x) (even? x)))) (define naturals (lambda (x) (and (number? x) (integer? x) (>= x 0)))) (define num0-10 (lambda (x) (and (number? x) (<= 0 x 10)))) (define odds1-9 (lambda (x) (and (number? x) (integer? x) (odd? x) (<= 1 x 9)))) ;; lst->set : [Listof X] -> [Set X] ;; create a set from the given list of objects (define (lst->set lox) (lambda (elt) (ormap (lambda (x) (equal? x elt)) lox))) (define sprimes (lst->set '(2 3 5 7 11 13))) (check-expect (sprimes 6) false) (check-expect (sprimes 13) true) ;; contains? : [Set X] X -> Boolean ;; is elt a member of set? (define (contains? s elt) (s elt)) (check-expect (contains? evens 5) false) (check-expect (contains? evens 40) true) (check-expect (contains? num0-10 4) true) (check-expect (contains? num0-10 40) false) (check-expect (contains? sprimes 17) false) (check-expect (contains? sprimes 9) false) (check-expect (contains? sprimes 3) true) ;; add-elt : [Set X] X -> [Set X] ;; create a set from the given set and object (define (add-elt s elt) (lambda (x) (or (equal? x elt) (s x)))) (check-expect (contains? (add-elt sprimes 17) 6) false) (check-expect (contains? (add-elt sprimes 17) 17) true) ;; union : [Set X] [Set X] -> [Set X] ;; create the set that contains the elements of both (define (union s1 s2) (lambda (x) (or (s1 x) (s2 x)))) (check-expect (contains? (union evens odds1-9) 11) false) (check-expect (contains? (union evens odds1-9) 9) true) (check-expect (contains? (union evens odds1-9) 20) true) ;; intersect : [Set X] [Set X] -> [Set X] ;; create the set that contains the elements ;; that the two sets share (define (intersect s1 s2) (lambda (x) (and (s1 x) (s2 x)))) (check-expect (contains? (intersect evens num0-10) 4) true) (check-expect (contains? (intersect evens num0-10) 7) false) (check-expect (contains? (intersect evens odds1-9) (random 10000)) false) ;; check if set contains a randomly generated even number: (check-expect (local ((define n (random 1000000))) (contains? (intersect evens naturals) (+ n (modulo n 2)))) true) ;; 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) (lambda (x) (and (pr? x) (s1 (pr-fst x)) (s2 (pr-snd x))))) (define s1 (cartesian (lst->set '(2 3 5 7 11 13)) (lst->set '(8 4 2)))) (check-expect (contains? s1 (make-pr 11 2)) true) (check-expect (contains? s1 (make-pr 8 2)) false) (check-expect (contains? s1 (make-pr 2 2)) true)