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 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 set set set oper-ations union, difference and intersection. Finally, program transformatio