Purely functional, real-time deques with catenation

We describe an efficient, purely functional implementation of deques with c atenation. In addition to being an intriguing;problem in its own right, fin ding 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 krh deque operation. Our solution is not o nly faster but simpler. A key idea used in our result is an algorithmic tec hnique related to the redundant digital representations used to avoid carry propagation in binary counting.