Strictly Functional, Real-Time Deques with Catenation

Abstract:

We describe an efficient purely functional implementation of
deques with catenation. In addition to being an intriguing problem in
its own right, functional implementation of catenable deques is the
tool 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 kth 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 and to avoid carry propagation in binary
counting.