This is the authors' abstract. We don't add key points for this paper.
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 programming constructs to functional programming languages. Our solution has a worst-case running time of O (1) for each push, pop, inject, eject and catenation. The best previously known solution has an O (log * k ) time bound for the k th deque operation. Our solution is not only faster but simpler. A key idea used in our result is an algorithmic technique related to the redundant digital representations used to avoid carry propagation in binary counting.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Kaplan et al. (1999) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: