We will implement sets as boolean-valued functions which return true if applied to an element in the set and false otherwise.
structure Set :> Set = struct type ''a set = ''a -> bool fun emptyset _ = false fun addset (x, s) = fn e => e = x orelse s e fun memberset (x, s) = s x end;
This structure declaration has collected the type and the three functions under the umbrella name, Set. They are given long identifiers which are formed by prefixing the identifier with the name of the structure and a dot.
|Set.addset||:||''a * ''a Set.set -> ''a Set.set|
|Set.memberset||:||''a * ''a Set.set -> bool|
|Set.emptyset||:||'a -> bool|
|Set.addset||:||''a * (''a -> bool) -> ''a -> bool|
|Set.memberset||:||'a * ('a -> 'b) -> 'b|
There are other candidate signatures for the Set structure which lie `between' the principal signature and the Set signature. One of these is given below.
signature Set = sig type 'a set val emptyset : 'a set val addset : ''a * ''a set -> ''a set val memberset : 'a * 'a set -> bool end;
This does not seem to be better than the previous Set signature because it fails to require equality types throughout. In so doing it rules out implementations of the Set structure which are allowed by the previous signature and all but forces the use of functions to represent sets.
Exercise (Addicts only.)
Provide a Set structure which matches the signature given above but stores the set elements in a list.