Numerical Representations as Higher−Order Nested Datatypes
Ralf Thomas Walter Hinze · 1998
Number systems serve admirably as templates for container types: a container object of size n is modelled after the representation of the number n and operations on container objects are modelled after their number-theoretic counterparts. Binomial queues are probably the first data structure that was designed with this analogy in mind. In this paper we show how to express these so-called numerical representations as higher-order nested datatypes. A nested datatype allows to capture the structural invariants of a numerical representation, so that the violation of an invariant can be detected at compile-time. We develop a programming method which allows to adapt algorithms to the new representation in a mostly straightforward manner. The framework is employed to implement three different container types: binary random-access lists, binomial queues, and 2-3 finger search trees. The latter data structure, which is treated in some depth, can be seen as the main innovation from a data-structural point of view. It appears that 2-3 finger search trees are the best known purely functional implementation of ordered sequences. In detail, 2-3 finger search trees support the operations findMin, findMax, deleteMin, and deleteMax in #THETA#(1) amortized time and member, insert, and delete in #THETA#(log(min#left brace#d, n-d#right brace#)) amortized time where d is the distance from the smallest element. In addition, concatenation is supported in #THETA#(log(min#left brace#n_1, n_2#right brace#)), splitting in #THETA#(log(min#left brace#d, n-d#right brace#)), and merge in #THETA#(n_s log(n_l/n_s)) amortized time where n_s is the size of the shorter and n_l the size of the longer sequence. These bounds remain valid even if the data structure is used in a persistent setting. (orig.)