;<pre>

;; First, a few lines to make this file usable as a teachpack
;;    (For details, see htus.org ("how to use scheme"), or
;;     http://www.owlnet.rice.edu/~comp210/02fall/Handouts/teachpack-demo.shtml ) 
;;
(module set (lib "plt-pretty-big.ss" "lang")
  (provide element-of?   ; any, Set --> boolean
           intersect     ; Set, Set --> Set
           union         ; Set, Set --> Set

           cars          ; Set                    (test case)
           reals<10      ; Set                    (test case)
           reals>=4      ; Set                    (test case)    
           )




;; We base our data-def'n of a set on the ways
;; mathematicians write sets.
;; We call it "inft-Set" since it can represent infinite sets.
;      <a name="data-defn" />

;; A inft-Set of alpha is either:
;; - a list of alpha, or
;; - alpha --> boolean  (the set's "indicator" function)


; Some examples of the data:
;
(define cars (list 'vw 'bmw 'audi 'saab 'geo))
(define (reals<10 x) (and (real? x) (<  x 10)))
(define (reals>=4 x) (and (real? x) (>= x  4)))

; Observation:
; The list representation can only be used for finite sets.
; The indicator-function representation can accomodate finite or infinite sets.





;; element-of?: ANY, inft-Set --> boolean
;; Is x in S?
;;
;; (Implementation note:
;;  compares via 'equal?' (not 'eq?') 
;;  if given a list-representation of a Set/infinite.)
;;
;  <a name="element-of?" />
;;
(define (element-of? x S)
  (cond [(list? S)      (not (boolean? (member x S)))]
        [(procedure? S) (S x)]))
  ;
  ; Not an issue unless reference-values are used:
  ; If we wanted to use eq? rather than equal?, 
  ; we'd use "memq" instead of "member".
  ; Either way, the indicator function implementation doesn't 
  ; have this ambiguity -- the function itself is given the
  ; input (possibly a reference), and decides the answer for itself.

; Tests:
;
(element-of? 'vw cars)   = true
(element-of? 'yugo cars) = false

(element-of?  4  reals<10)  = true
(element-of? 13  reals<10)  = false
(element-of? 'vw reals<10)  = false





;; intersect: Set, Set --> Set
;; union:     Set, Set --> Set
;;
;; Implementation note: the returned Set happens to
;; be represented as an indicator function, regardless of the input
;; representation.
;; (Not that the user of the abstract type "Set" cares.)
;;
;  <a name="union" />
;;
(define (intersect A B)
   (lambda (elt) (and (element-of? elt A) (element-of? elt B))))

(define (union A B)
   (lambda (elt) (or  (element-of? elt A) (element-of? elt B))))


; Tests:
;
(element-of? 'vw   (union cars     reals<10)) = true
(element-of?  9    (union cars     reals<10)) = true
(element-of? 11    (union cars     reals<10)) = false
(element-of? 11    (union reals>=4 reals<10)) = true
(element-of?  3    (union reals>=4 reals<10)) = true
(element-of?  6    (union reals>=4 reals<10)) = true

(element-of? 'yugo (intersect cars     reals<10)) = false
(element-of? 'vw   (intersect cars     reals<10)) = false
(element-of?   6   (intersect reals>=4 reals<10)) = true
(element-of?  11   (intersect reals>=4 reals<10)) = false
(element-of?   3   (intersect reals>=4 reals<10)) = false







;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Doomed ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; An attempt, which will be scotched by not being
;; able to implement subset? for inft-sets.
;; (This turns out to be a fundamental limit on computation -- not
;;  an artifact of our language, representation, etc.)
;; However, for finite sets, this code works like a charm.
;  <a name="set=?" />
;; 

;; inft-set=?: set, set --> boolean
;;
(define (inft-set=? A B)  (and (subset? A B) (subset? B A)))
  ;
  ; This code directly parallels our (alternate) def'n of equal sets 
  ; -- happiness!

;; empty-set?: set --> boolean
;;
(define (empty-set? A)  (inft-set=? empty A)) 
  ;
  ; Pointed out: Could also write (subset? A empty).
  ; Empty is one possible representation of the empty set; what is another?



;; subset?: set, set --> boolean
;;
(define (subset? A B)
  (error 'subset? "Fundamentally can't implement subset? for infinite sets."))
;
; If we restrict ourselves to finite sets, then we could write subset?.
; We still would not want to change the code for set=? or empty-set? --
; The compiler can do any optimization; we'll keep our code clearly
; reflecting our definitions.
;
; See the reading (Rosen 1.7) for implementations of finite sets.




#|
;;;;;;;;;;;;;;;;; Aside: An object hierarchy for finite & infinite sets.
In a class system, how should classes inft-set and finite-set be arranged?
;  <a name="set-class-hier" />

(define-class Inft-set (extends Object)
   (public* element-of?)
   (static* union intersect))
   ; Make these 2-arg functions static, not methods,
   ; since neither of the two args have more importance than the other.

(define-class Finite-set (extends Inft-set)
   (inherit*  element-of? union intersect)
   (public*   subset? empty-set?)
   (static*   set=?)
   ; Make this 2-arg functions static, not methods,
   ; since neither of the two args have more importance than the other.
   )

(N.B. This isn't exactly drscheme's object syntax;
      see help-desk for the official details.)

It's a bit weird english, to say "Finite-set extends Inft-set";
clearly finite sets are a >restriction< of infinite sets.
However, in terms of behavior, we are extending the number of methods.

Indeed, the is-a relation certainly holds between these classes:
every Finite-set is-a Inft-set.
(Okay, maybe a better name would have been "Possibly-infinite-set", oh well.)
This is analagous to "class Cat extends Animal" -- Cats are a restricted 
type of Animal, but they have more behaviors than generic Animals,
such as shredOwnersOttoman! (a function with side-effects).

One annoying thing:
if we wanted, for Finite-sets, versions of union and
intersect that returned *finite* sets (rather than just Sets),
we'd just override those methods.
HOWEVER, <a href="lect01-aside.java">most languages</a> don't allow 
modifying the signature of the inherited function.
This is true even though:
- we want to express that Finite-set.union() *must* always return a 
  Finite-set, and 
- we are still meeting the original contract, 
  since every Finite-set is-a Inft-set.
This weakness of the type-system keeps us from properly expressing
the typing that we really want to enforce
(and, may force us to add type-casts to our code later -- ugly!).

|#



)  ; End module.
;</pre>