(*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" ?
*)