Purely Functional Representations of Catenable Sorted Lists

Abstract:

The power of purely functional programming in the construction
of data structures has received much attention, not only
because functional languages have many desirable properties,
but because structures built purely functionally are automatically
fully persistent: any and all versions of a structure
can coexist indefinitely. Recent results illustrate the
surprising power of pure functionality. One such result
was the development of a representation of double-ended queues
with catenation that supports all operations, including
catenation, in worst-case constant time [21].
This paper is a continuation of our study of pure functionality,
especially as it relates to persistence. For one purposes,
a purely functional data structure is one built only with
the LISP functions car, cons, cdr. We explore purely
functional representations of sorted lists, implemented as
finger search trees. We describe three implementations.
The most efficient of these achieves logarithmic access, insertion,
and deletion time, and double-logarithmic catenation time. It
uses one level of structural bootstrapping to obtain
its efficiency.
The bounds for find,insert, and delete are
the same as the best known bounds for an ephemeral
implementation of these operations using finger search trees.
The representations we present are the first that address
the issues of persistence and pure functionality, and the
first for which fast implementations of catenation and split
are presented.
They are simple to implement and could be efficient in practice,
especially for applications that require worst-case time bounds
or persistence.