(*sets*)

datatype 'a set = Set of 'a list;

     val empty_set = Set [];

     fun member e (Set []) = false
        |member e (Set (a::x)) = e=a orelse member e (Set x);

     fun add e S = if member e S 
                   then S 
                   else let val Set(x) = S in Set(e::x) end;

     fun subset (Set []) s2 = true
        |subset (Set (e::x)) s2 = member e s2 andalso subset (Set x) s2;

     fun superset s1 s2 = subset s2 s1;

     fun equal_sets s1 s2 = subset s1 s2 andalso subset s2 s1;

     fun union (Set []) s2 = s2
        |union (Set (e::x)) s2 = if not(member e s2)
                                 then union (Set x) (add e s2)
                                 else union (Set x) s2;

     fun intersection (Set []) s2 = empty_set
        |intersection (Set (e::x)) s2 = if member e s2
                                        then add e (intersection (Set x) s2)
                                        else intersection (Set x) s2;

     fun difference (Set []) s2 = empty_set
        |difference (Set (e::x)) s2 = if not(member e s2)
                                      then add e (difference (Set x) s2)
                                      else difference (Set x) s2;

     fun remove e (Set []) = empty_set
        |remove e (Set (a::x)) = if e=a 
                                 then (Set x)
                                 else add a (remove e (Set x));

     fun show (Set []) = []
        |show (Set (e::x)) = e::show (Set x);

     fun make_set [] = empty_set
        |make_set (e::x) = add e (make_set x); 

     fun map_set f (Set s) = make_set (map f s);

(*
NOTES:
(1) User has access to constructor "Set"
(2) User can redefine things (such as "add") and
    violate the principle of Sets
(3) User is made aware of implementation details
    (ie. sets are finite lists)
(4) Polymorphic or not Polymorphic?
     Reading from LC Paulson pp 86->, and from Reade pp 244 ->

     The function "member" is of type: ''a -> ''a set -> bool
     and function "union" is of type: ''a set -> ''a set -> ''a set

     That is, although these functions are in some way polymorphic, they depend
     on the ability to perform "equality testing" (thus the ''a).
     Therefore, the definitions of sets above is in some ways restrictive. For
     example, can we have a set of sets (the power set of S would be an example)?
     The answer is NO, since we cannot arbitrarly check if S1 = S2 without some
     knowledge of the type of S1 and S2 (imagine a set of functions).
*)

Script started on Wed Nov  6 12:34:46 1991
hunter-01% sml
Standard ML of New Jersey, Version 0.66, 15 September 1990
val it = () : unit
- use "sets";
[opening sets]
datatype 'a  set
con Set : 'a list -> 'a set
val empty_set = Set [] : 'a set
val member = fn : ''a -> ''a set -> bool
val add = fn : ''a -> ''a set -> ''a set
val subset = fn : ''a set -> ''a set -> bool
val superset = fn : ''a set -> ''a set -> bool
val equal_sets = fn : ''a set -> ''a set -> bool
val union = fn : ''a set -> ''a set -> ''a set
val intersection = fn : ''a set -> ''a set -> ''a set
val difference = fn : ''a set -> ''a set -> ''a set
val remove = fn : ''a -> ''a set -> ''a set
val show = fn : 'a set -> 'a list
val make_set = fn : ''a list -> ''a set
val map_set = fn : ('a -> ''b) -> 'a set -> ''b set
[closing sets]
val it = () : unit
- empty_set;
val it = Set [] : 'a set
- val s  1 = make_set [~2,~1,0,1,2,3,4];
val s1 = Set [~2,~1,0,1,2,3,4] : int set
- member 3 s1;
val it = true : bool
- val s2 = add 3 s1;
val s2 = Set [~2,~1,0,1,2,3,4] : int set
- s1 = s2;
val it = true : bool
- val s3 = make_set [1,2,3,4,0,~1,~2];
val s3 = Set [1,2,3,4,0,~1,~2] : int set
- s1 = s3;
val it = false : bool
- (* ????? *)
- subset s1 s2;
val it = true : bool
- superset s1 s2;
val it = true : bool
- equal_sets s1 s2;
val it = true : bool
- equal_sets s1 s3;
val it = true : bool
- union s1 s2;
val it = Set [~2,~1,0,1,2,3,4] : int set
- val s4 = make_set [1,2,5,8,10];
val s4 = Set [1,2,5,8,10] : int set
- intersection s1 s4;
val it = Set [1,2] : int set
- difference s1 s4;
val it = Set [~2,~1,0,3,4] : int set
- difference s4 s1;
val it = Set [5,8,10] : int set
- s4;
val it = Set [1,2,5,8,10] : int set
- union s1 s4;
val it = Set [4,3,0,~1,~2,1,2,5,8,10] : int set
- val s5 = map_set (fn n => n*n) s1;
val s5 = Set [0,1,4,9,16] : int set
- s1;
val it = Set [~2,~1,0,1,2,3,4] : int set
- map_set (fn n => (n mod 2) = 0) s1;
val it = Set [false,true] : bool set
- s1;
val it = Set [~2,~1,0,1,2,3,4] : int set
- val bad = Set [1,2,3,1,2,3];
val bad = Set [1,2,3,1,2,3] : int set
- bad;
val it = Set [1,2,3,1,2,3] : int set
- remove 1 bad;
val it = Set [2,3,1,2,3] : int set
- val okay = union bad empty_set;
val okay = Set [3,2,1] : int set
hunter-01% 
script done on Wed Nov  6 13:01:58 1991