TY - GEN

T1 - Purely functional representations of catenable sorted lists

AU - Kaplan, Haim

AU - Tarjan, Robert Endre

PY - 1996/7/1

Y1 - 1996/7/1

N2 - 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 [19]. This paper is a continuation of our study of pure functionality, especially as it relates to persistence. For our 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 access, 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 appbcations that require worst-case time bounds or persistence.

AB - 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 [19]. This paper is a continuation of our study of pure functionality, especially as it relates to persistence. For our 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 access, 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 appbcations that require worst-case time bounds or persistence.

UR - http://www.scopus.com/inward/record.url?scp=0029703216&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029703216&partnerID=8YFLogxK

U2 - 10.1145/237814.237865

DO - 10.1145/237814.237865

M3 - Conference contribution

AN - SCOPUS:0029703216

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 202

EP - 211

BT - Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996

PB - Association for Computing Machinery

T2 - 28th Annual ACM Symposium on Theory of Computing, STOC 1996

Y2 - 22 May 1996 through 24 May 1996

ER -