More than with any other part of Standard ML programming with abstypes requires a certain discipline. We have in the abstype concept a means of localising the creation of values of a particular type and the reason for wishing to do this is that we can validate the creation of these values, rejecting certain undesirable ones, perhaps by raising exceptions. Moreover, we can exploit the validation within the abstype definition itself. Here we implement sets as ordered lists without repetitions.

abstype'a ordered_set = Setof(('a * 'a) -> bool) * 'a listwithfunemptyset (op<=) = Set (op<=, [])funaddset (x, Set (op<=, s)) =letfunins [] = [x] | ins (sash::t) =ifx = hthenselseifx <= hthenx :: selseh :: ins tinSet (op<=, ins s)endfunmemberset (x, Set (_, [])) = false | memberset (x, Set (op<=, h::t)) = h <= xandalso(x = hormemberset (x, Set (elseop<=, t)))end;

The abstype mechanism ensures that sets have been created either by
the function emptyset or by the function addset.
Both of these functions construct sorted lists and thus it is safe to
exploit this ordering in memberset. By this time, because we
are imposing a particular order on the values in the list it is
crucially important we do not provide access to the
Set constructor (say via **val** mk_
set = Set) because otherwise a user of this
ordered_set abstype could create an unordered
set thus.

val myset =
mk_set (op <=, [1, 5, 3, 2, 8]) |

memberset (1, myset) | = | true |

memberset (5, myset) | = | true |

memberset (3, myset) | = | false |

memberset (2, myset) | = | false |

memberset (8, myset) | = | true |

**Exercise**

Would it be prudent to add the following definition of equal within the definition of ordered set? What are the circumstances in which its use might give a misleading result?funequal (Set (_, s1), Set (_, s2)) = s1 = s2;

Having seen a simple implementation of sets as ordered lists we could improve this to an implementation which used binary trees and improve that to an implementation which used balanced trees. Fortunately this has already been done for us by Stephen Adams [Ada93] whose paper describes his implementation.