Implementing sets efficiently in a functional language
Most texts describing data structures give imperative implementations.
These are either difficult or tedious to convert to a functional (non
This technical report describes the implementation of sets in the
functional subset of Standard ML.
The implementation is based on balanced binary trees.
Tree balacing algorithms are usually complex.
We show that this need not be the case---the trick is to abstract away
from the rebalancing scheme to achieve a simple and efficient implementation.
A complete implementation of sets is given, including the
operations union, difference and
Finally, program transformation techniques are used to derive a more efficient
Full document is available in Postscript, either
compressed (67k), or
[ Project MAC
| Stephen Adams
Last updated on 27 June 1996