Real-time deques, multihead Turing machines, and purely functional programming
Tyng–Ruey Chuang, Benjamin Goldberg · 1993
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.We then show that the implementation has some interesting implications, and can be used to give a real-time simulation of a multihead Turing machine in a purely functional language.