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

A shorter, but cleaner version of this work appeared in:
Stephen Adams. Functional pearls: Efficient sets -- a balancing act. Journal of Functional Programming, 3(4):553-561, October 1993. [BibTeX entry]
Source code, written for Standard ML of New Jersey.
An expanded version was incorporated into MIT Scheme version 7.3 onwards. An R4RS and IEEE compliant copy of the Scheme source code and its documentation is available from the Scheme Repository at Indiana University.

[ Project MAC | Stephen Adams ]

Last updated on 27 June 1996

adams@ai.mit.edu.