1993 · 61 citations · 28 references
ComputingComputer ScienceArtificial IntelligenceCompilersProgramming LanguagesFunctional ProgrammingTuring Machines
We answer the following question: Can a deque (doubleended queue) be implemented in a purely functional language such that each push or pop operation on either end of a queue is accomplished in 0(1) time in the worst case? The answer is yes, thus solving a problem posted by Gajewska and Tarjan [14] and by Ponder, McGeer, and Ng [25], and refining results of Sarnak [26] and Hoogerwoord [18]. We term such a deque real-time, since its constant worstcaae behavior might be useful in real time programs (assuming real-time garbage collection [3], etc.) Furthermore, we show that no restriction of the functional language is necessary, and that push and pop operations on previou$ versions of a deque can also be achieved in constant time. We present a purely functional implementation of realtime deques and its complexity analysis.
28
Imperative functional programming
Simon Jones, Philip Wadler · 1993 · 1.2K citations · Full text
Making data structures persistent
James R. Driscoll, Neil Sarnak, Daniel D. Sleator et al. · 1986 · 704 citations
List processing in real time on a serial computer
Henry G. Baker · Communications of the ACM · 1978 · 592 citations · Full text
Philip Wadler · 1990 · 575 citations · Full text
Amortized Computational Complexity
Robert E. Tarjan · SIAM Journal on Algebraic and Discrete Methods · 1985 · 525 citations