Thus far our programs have been small and simple and it would have
seemed excessive to have structured them into modular units. When we
come to write larger programs we will want to encapsulate some
functions together with a datatype in order to control the access to
the elements of the datatype. The construction we use for this
purpose is **abstype** .. **with** ..
**end**.

We will implement an abstract data type for sets. These are unordered collections of values. A membership test is provided. Duplications are not significant: there is no way to test how many times a value occurs in a set. The problem is then to provide a way to construct sets and test for membership without giving away other information such as the number of times a value appears in the set.

The following abstract data type introduces a type constructor, set, a value emptyset and two functions, addset and memberset. The constructors null and ins are hidden, they are not visible.

abstype'a set = null | insof'a * 'a setwithvalemptyset = nullvaladdset = insfunmemberset (x, null) = false | memberset (x, ins (v, s)) = x = vormemberset (x, s)elseend;

It might seem somewhat futile to hide the names null and
ins and then provide emptyset and
addset. The point is that in so doing, we take away the *
constructor* status of null and ins and
that means that they cannot be used in pattern matching to destruct
the constructed value and see inside.

But it would seem that nothing we have described could not be achieved with the features of the Standard ML language which we knew already, albeit in a slightly more complicated definition.

localdatatype'a set = null | insof'a * 'a setintype'a set = 'a setvalemptyset = nullvaladdset = insfunmemberset (x, null) = false | memberset (x, ins (v, s)) = x = vormemberset (x, s)elseend;

So in what sense is the abstract data type more abstract than the type which is defined here?

The problem is that *equality* is available on the sets which
are defined using the second form of the definition and the equality
which is provided is not the one we want. No equality test is
permitted if we use an **abstype** definition. If we want to allow
equality we must implement it ourselves.

abstype'a set = null | insof'a * 'a setwithvalemptyset = nullvaladdset = insfunmemberset (x, null) = false | memberset (x, ins (v, s)) = x = vormemberset (x, s)elselocalfunsubset (null, _) = true | subset (ins (x, s1), s2) = memberset (x, s1)andalsosubset (s1, s2)infunequalset (s1, s2) = subset (s1, s2)andalsosubset (s2, s1)endend;

We have made the equal function available but not the subset function which we used in its implementation.

Abstract data types are *first-class* values in Standard ML
because they may be passed to functions as arguments, as shown below.

funallmembers ([], _) = true | allmembers (h::t, s) = memberset (h, s)andalsoallmembers (t, s);

This function has type (''a list * ''a set) -> bool. They may also be returned from functions as results. The following function has type ('a list * 'a set) -> 'a set.

funaddmembers ([], s) = s | addmembers (h::t, s) = addset (h, addmembers (t, s));