(*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). *)