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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-06.ps.gz