Recent results illustrate the surprising power of pure functionality.
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.