article

Simple Confluently Persistent Catenable Lists

Authors:

Haim Kaplan,

Chris Okasaki,

Robert E. TarjanAuthors Info & Claims

SIAM Journal on Computing, Volume 30, Issue 3

Pages 965 - 977

https://doi.org/10.1137/S0097539798339430

Published: 01 May 2000 Publication History

Publisher Site

Abstract

We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive---each operation produces a new list incorporating the change, while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. Our implementation is functional if we allow memoization.

Cited By

View all

Denzumi SYoshinaka RArimura HMinato S(2016)Sequence binary decision diagramDiscrete Applied Mathematics10.1016/j.dam.2014.11.022212:C(61-80)Online publication date: 30-Oct-2016
https://dl.acm.org/doi/10.1016/j.dam.2014.11.022
Danielsson N(2008)Lightweight semiformal time complexity analysis for purely functional data structuresACM SIGPLAN Notices10.1145/1328897.132845743:1(133-144)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328897.1328457
Danielsson NNecula GWadler P(2008)Lightweight semiformal time complexity analysis for purely functional data structuresProceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1328438.1328457(133-144)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328438.1328457
Show More Cited By

Index Terms

Simple Confluently Persistent Catenable Lists
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Linked lists

Recommendations

Fully persistent lists with catenation

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 ...
Discrete-time single-server finite-buffer queues under discrete Markovian arrival process with vacations

This paper treats a discrete-time single-server finite-buffer exhaustive (single- and multiple-) vacation queueing system with discrete-time Markovian arrival process (D-MAP). The service and vacation times are generally distributed random variables and ...
Purely functional, real-time deques with catenation

We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of catenable deques is required to add certain sophisticated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 30, Issue 3

2000

352 pages

ISSN:0097-5397

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 May 2000

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Denzumi SYoshinaka RArimura HMinato S(2016)Sequence binary decision diagramDiscrete Applied Mathematics10.1016/j.dam.2014.11.022212:C(61-80)Online publication date: 30-Oct-2016
https://dl.acm.org/doi/10.1016/j.dam.2014.11.022
Danielsson N(2008)Lightweight semiformal time complexity analysis for purely functional data structuresACM SIGPLAN Notices10.1145/1328897.132845743:1(133-144)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328897.1328457
Danielsson NNecula GWadler P(2008)Lightweight semiformal time complexity analysis for purely functional data structuresProceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1328438.1328457(133-144)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328438.1328457
Lagogiannis GPanagis YSioutas STsakalidis A(2005)A survey of persistent data structuresProceedings of the 9th WSEAS International Conference on Computers10.5555/1369599.1369607(1-6)Online publication date: 14-Jul-2005
https://dl.acm.org/doi/10.5555/1369599.1369607
Gapeyev VLevin MPierce BSchmitt A(2005)XML goes nativeProceedings of the 14th international conference on Compiler Construction10.1007/978-3-540-31985-6_4(43-58)Online publication date: 4-Apr-2005
https://dl.acm.org/doi/10.1007/978-3-540-31985-6_4
Eker S(2003)Associative-commutative rewriting on large termsProceedings of the 14th international conference on Rewriting techniques and applications10.5555/1759148.1759152(14-29)Online publication date: 9-Jun-2003
https://dl.acm.org/doi/10.5555/1759148.1759152
Fiat AKaplan H(2003)Making data structures confluently persistentJournal of Algorithms10.1016/S0196-6774(03)00044-048:1(16-58)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1016/S0196-6774%2803%2900044-0

Abstract

Cited By

Index Terms

Recommendations

Fully persistent lists with catenation

Discrete-time single-server finite-buffer queues under discrete Markovian arrival process with vacations

Purely functional, real-time deques with catenation

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations