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 | ins of 'a * 'a set
with
val emptyset = null
val addset = ins
fun memberset (x, null) = false
| memberset (x, ins (v, s)) = x = v orelse memberset (x, s)
end;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.
local
datatype 'a set = null | ins of 'a * 'a set
in
type 'a set = 'a set
val emptyset = null
val addset = ins
fun memberset (x, null) = false
| memberset (x, ins (v, s)) = x = v orelse memberset (x, s)
end;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 | ins of 'a * 'a set
with
val emptyset = null
val addset = ins
fun memberset (x, null) = false
| memberset (x, ins (v, s)) = x = v orelse memberset (x, s)
local
fun subset (null, _) = true
| subset (ins (x, s1), s2) =
memberset (x, s1) andalso subset (s1, s2)
in
fun equalset (s1, s2) = subset (s1, s2) andalso subset (s2, s1)
end
end;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.
fun allmembers ([], _) = true | allmembers (h::t, s) = memberset (h, s) andalso allmembers (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.
fun addmembers ([], s) = s | addmembers (h::t, s) = addset (h, addmembers (t, s));