Fully persistent lists with catenation
- 1 September 1994
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 41 (5) , 943-959
- https://doi.org/10.1145/185675.185791
Abstract
This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O(log logk) time and space. Herekis the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.Keywords
This publication has 7 references indexed in Scilit:
- Making data structures persistentJournal of Computer and System Sciences, 1989
- Abstract continuations: a mathematical semantics for handling full jumpsPublished by Association for Computing Machinery (ACM) ,1988
- Searching and storing similar listsJournal of Algorithms, 1986
- How to search in historyInformation and Control, 1985
- An applicative random-access stackInformation Processing Letters, 1983
- Incremental Context-Dependent Analysis for Language-Based EditorsACM Transactions on Programming Languages and Systems, 1983
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978