To introduce the notion of type abstraction, and its realisation through the
Miranda abstype mechanism.
To illustrate multiple implementations of abstype signatures.
To compare the effect of modifying the implementation of a
type when it is concretely or abstractly presented.
To present standard data types: stacks, queues, search trees,
sets, relations and graphs,
together with their abstract interfaces.
To discuss principles of abstract data type design, and to illustrate their
use in the simulation case study.
I have tried to give an illustration of the value of type abstraction using
the abstype of search trees. The implementation has a size field
added, and we can then examine the effect on the functions using the search
trees. It would be interesting to illustrate this using abstypes from other
There is plenty of scope for class exercises to
design abstract data types, particularly examples which have been presented
earlier in the course.
Written 18 May 1995.