Examples of ML implementations of ADTs
ADTs specified with Algebraic semantics, Guttag's hueristic,
can be directly implemented in ML... almost a syntactic
The canonical methods of your specs are expressed in an ML "datatype"
Each non-canonical method is defined as a "fun" definition using the
pattern matching facilities of ML. Create one alternative per
basic stuff... holds integers only
A more polymorphic set... can build a set to contain elements
of any equality type (not just int).
double ended queue... illustrates an ADT where you have several
choices of canonical constructors
A stack (of int) where elements in the stack are unique... like
a set... if you push an element on the stack that is already in
the stack, the element "bubbles" to the top
A more complicated stack of int defined to have a max size;
push is defined to do nothing is it is applied to a full stack