;; NSet = [Listof Number]
;; order does not matter, no repetitions allowed

;; contains? : NSet Number -> Boolean
;; Does set s contain number n?
(define (contains? s n)
  (ormap (lambda (x) (= x n)) s))

(check-expect (contains? '() 1) false)
(check-expect (contains? '(1 3 4) 3) true)
(check-expect (contains? '(1 5 4) 3) false)
(check-expect (contains? '(1 4 3) 3) true)

;; subset? : NSet NSet -> Boolean
;; Is s1 a subset of ss?
(define (subset? s1 s2) 
  (andmap (lambda (x1) (contains? s2 x1)) s1))

(check-expect (subset? '() '(1)) true)
(check-expect (subset? '(1) '()) false)
(check-expect (subset? '(10 4 5) '(4 5 10)) true)
(check-expect (subset? '(10 4 5) '(5 10)) false)

;; set=? : NSet NSet -> Boolean
;; Is s1 equal to s2?
(define (set=? s1 s2)
  (and (subset? s1 s2) 
       (subset? s2 s1))) 

#;(define (set=? s1 s2)
  (and (subset? s1 s2) 
       (= (length s1) (length s2))))

(check-expect (set=? '() '(1)) false)
(check-expect (set=? '() '()) true)
(check-expect (set=? '(1) '()) false)
(check-expect (set=? '(10 4 5) '(5 10)) false)
(check-expect (set=? '(10 4 5) '(4 5 10)) true)


;; intersect : NSet NSet -> NSet
;; compute intersection of s1 and s2
(define (intersect s1 s2)
  (filter (lambda (x2) (contains? s1 x2)) s2))

(check-expect (set=? (intersect '(10 4 5) '(5 10)) '(5 10)) true)
(check-expect (set=? (intersect '() '(4 5 10)) '()) true)
(check-expect (set=? (intersect '(6 5) '(4 5 10)) '(5)) true)

;; union : NSet NSet -> NSet
;; compute the union of s1 and s2
(define (union s1 s2)
  (append s1 (filter (lambda (x2) (not (contains? s1 x2))) s2)))

(check-expect (set=? (union '(10 4 5) '(5 10)) '(10 4 5)) true)
(check-expect (set=? (union '() '(4 5 10)) '(10 5 4)) true)
(check-expect (set=? (union '(6 5) '(4 5 10)) '(5 6 4 10)) true)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Representing infinite sets

;; NSet = [Number -> Boolean]
;; represent set using a characteristic function

(define evens (lambda (n) (and (integer? n) (even? n))))
(evens 2)