Purely functional representations of catenable sorted lists

Haim Kaplan, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

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 [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.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996
PublisherAssociation for Computing Machinery
Pages202-211
Number of pages10
ISBN (Electronic)0897917855
DOIs
StatePublished - Jul 1 1996
Event28th Annual ACM Symposium on Theory of Computing, STOC 1996 - Philadelphia, United States
Duration: May 22 1996May 24 1996

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129452
ISSN (Print)0737-8017

Other

Other28th Annual ACM Symposium on Theory of Computing, STOC 1996
CountryUnited States
CityPhiladelphia
Period5/22/965/24/96

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Purely functional representations of catenable sorted lists'. Together they form a unique fingerprint.

  • Cite this

    Kaplan, H., & Tarjan, R. E. (1996). Purely functional representations of catenable sorted lists. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996 (pp. 202-211). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129452). Association for Computing Machinery. https://doi.org/10.1145/237814.237865