Implementing sets efficiently in a functional language

Abstract

Most texts describing data structures give imperative implementations. These are either difficult or tedious to convert to a functional (non side-effecting) form. 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 intersection. Finally, program transformation techniques are used to derive a more efficient union operation.

Full document is available in Postscript, either compressed (67k), or uncompressed (200k).

Further information


[ Project MAC | Stephen Adams ]

Last updated on 27 June 1996

adams@ai.mit.edu.