;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-reader.ss" "lang")((modname oct-6) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
;; A Set is one of:
;; - empty
;; - (cons Number Set)
;; Interp: repititions allowed, order doesn't matter
#;
(define (set-temp s)
  (cond [(empty? s) ...]
        [(cons? s) (first s) ... (set-temp (rest s))]))

;; contains? : Set Number -> Boolean
;; Is the number in the set?
(check-expect (contains? empty 5) false)
(check-expect (contains? (cons 5 empty) 5) true)
(check-expect (contains? (cons 7 empty) 5) false)
(define (contains? s n)
  (cond [(empty? s) false]
        [(cons? s)
         (or (= (first s) n)
             (contains? (rest s) n))]))

;; subset? : Set Set -> Number
;; Is the first set a subset of the second?
(check-expect (subset? empty empty) true)
(check-expect (subset? empty (cons 5 empty)) true)
(check-expect (subset? (cons 1 empty) (cons 5 (cons 1 empty))) true)
(check-expect (subset? (cons 1 empty) (cons 5 empty)) false)
(check-expect (subset? (cons 1 empty) (cons 1 empty)) true)
(define (subset? s t)
  (cond [(empty? s) true]
        [(cons? s) 
         (and (contains? t (first s))
              (subset? (rest s) t))]))

;; set=? : Set Set -> Boolean
;; Are the two sets equal?
(check-expect (set=? empty empty) true)
(check-expect (set=? empty (cons 5 empty)) false)
(check-expect (set=? (cons 1 empty) (cons 5 (cons 1 empty))) false)
(check-expect (set=? (cons 1 empty) (cons 5 empty)) false)
(check-expect (set=? (cons 1 empty) (cons 1 empty)) true)
(check-expect (set=? (cons 1 (cons 5 empty)) (cons 5 (cons 1 empty))) true)
(define (set=? s t)
  (and (subset? s t)
       (subset? t s)))

;; union : Set Set -> Set
;; Union the two sets together.
(check-expect (set=? (union empty empty) empty) true)
(check-expect (set=? (union empty (cons 5 empty)) (cons 5 empty)) true)
(check-expect (set=? (union (cons 1 empty) (cons 5 (cons 1 empty)))
                     (cons 1 (cons 5 empty)))
              true)
(check-expect (set=? (union (cons 1 empty) (cons 5 empty)) 
                     (cons 1 (cons 5 empty))) 
              true)
(check-expect (set=? (union (cons 1 empty) (cons 1 empty)) (cons 1 empty)) true)
(check-expect (set=? (union (cons 1 (cons 5 empty)) (cons 5 (cons 1 empty)))
                     (cons 1 (cons 5 empty)))
              true)
(define (union s t)
  (cond [(empty? s) t]
        [(cons? s) 
         (cons (first s)
               (union (rest s) t))]))

;; A SetP is one of:
;; - empty
;; - (cons Posn SetP)

;; x : Set Set -> SetP
;; Cross each element the two sets.
(define (x s t)
  (cond [(empty? s) empty]
        [(cons? s) 
         (union (x1 (first s) t)
                (x (rest s) t))]))

;; x1 : Number Set -> SetP
;; Cross the number with each element of the set.
(define (x1 n s)
  (cond [(empty? s) empty]
        [(cons? s)
         (cons (make-posn n (first s))
               (x1 n (rest s)))]))

;; Examples (not tests) because we'd need setp=? to write tests.
(x1 1 (cons 3 (cons 4 empty)))
(cons (make-posn 1 3)
      (cons (make-posn 1 4)
            empty))

(x (cons 1 (cons 2 empty))
   (cons 3 (cons 4 empty)))
(cons (make-posn 1 3)
      (cons (make-posn 1 4)
            (cons (make-posn 2 3)
                  (cons (make-posn 2 4)
                        empty))))