We will implement sets as boolean-valued functions which return true if applied to an element in the set and false otherwise.

structureSet :> Set =structtype''a set = ''a -> boolfunemptyset _ = falsefunaddset (x, s) =fne => e = xors eelsefunmemberset (x, s) = s xend;

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.emptyset | : | ''a Set.set |

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.

signatSet =uresigtype'a setvalemptyset : 'a setvaladdset : ''a * ''a set -> ''a setvalmemberset : 'a * 'a set -> boolend;

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.