; A set is a collection of objects which are separate and distinct 
; from other objects.

; One of the ways to express a set is by listing all its elems 
; e.g. A = {a,b,c,d,e,f}

; This type of set can be represented easily as a list

(define empty-set '())
(define empty-set? (lambda (S) (eq? S empty-set)))

(define get-element-from car)
(define rest-of-set cdr)

(define join cons)

; Thus given some object x we know whether it belons to the set 
; or not

(define true (= 0 0))
(define false (= 0 1))

(define member?
  (lambda (x S) 
    (cond
     ((empty-set? S) false)
     ((eq? x (get-element-from S)) true)
     (else (member? x (rest-of-set S))))))

; Because the collection represents separate and distinct objects 
; a set can not contain duplicates

; So we can define a lambda for adding an element x to a set S 
; as follows:

(define insert
  (lambda (x S) (if (not (member? x S)) (cons x S))))

; Therefore, insert will only add an element to a set if the 
; element is distinct from elements already in the set

; Removing an element from a set S

(define remove
  (lambda (x S)
    (cond
     ((empty-set? S) S)
     ((eq? x (get-element-from S)) (rest-of-set S))
     (else (join (get-element-from S) (remove x (rest-of-set S)))))))

; So we can build a set as follows

(define A (insert 9 (insert 1 empty-set)))
(define B (insert 0 (insert 3 (insert 9 (insert 1 empty-set)))))

; Some operations on sets

; set A is a subset of set B iff every element of A is in B

(define subset?
  (lambda (A B)
    (if (null? A)
	true
	(and (member? (get-element-from A) B) 
	     (subset? (rest-of-set A) B)))))

; set A is equal to set B iff 
; A is a subset of B  AND B is a subset of A

(define seteq? 
  (lambda (A B)
    (and (subset? A B) (subset? B A))))

(seteq? A B)
(seteq? A A)

; Homework:
; Certify all of the lambdas presented above