(*sets*)
                      (* Use of abstract data types *)

abstype 'a set = Set of 'a list
with 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); 
end;

(* NOTE
 (1) The constructor "Set" is disallowed.
 (2) The details of sets are "hidden" from the user
 (3) But how do we implement "map_set" ?
*)



Script started on Wed Nov  6 12:55:26 1991
hunter-01% sml
Standard ML of New Jersey, Version 0.66, 15 September 1990
val it = () : unit
- use "sets-abstype";
[opening sets-abstype]
type'a  set
val empty_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
[closing sets-abstype]
val it = () : unit
- val s1 = empty_set;
val s1 = - : 'a set
- val s2 = (Set [1,2,3]);
std_in:4.11-4.13 Error: unbound variable Set
std_in:4.10-4.22 Error: operator is not a function
  operator: undef
  in expression:
    Set 1 :: 2 :: 3 :: nil
- val s1 = make_set [1,2,3,4];
val s1 = - : int set
- (* ??? why can't I see it ???? *)
- show s1;
val it = [1,2,3,4] : int list
- val s2 = make_set (map (fn n => n*n) (show s1));
val s2 = - : int set
- show s2;
val it = [1,4,9,16] : int list
hunter-01% 
script done on Wed Nov  6 12:57:57 1991