Purely functional lists
Haim Y. Kaplan · 1997
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$\sp* k)$ time bound for the $k\sp{th}$ deque operation. Our solution is not only faster but simpler, and indeed we hope it may be practical. We also describe a purely functional representation of sorted lists, implemented as finger search trees. We obtain our representation as a generalization of a particular deque data structure, but one can also view it as a new kind of finger search tree. The time bounds for access, insert, and delete that our implementation achieve are the same as the best known bounds of any ephemeral implementation of these operations using finger search trees. The representation we present is the first that address the issues of persistence and pure functionality, and the first for which fast implementations of catenate and split are presented. Our solution is simple to implement and can be competitive with existing structures even in an ephemeral setting. The motivating insight in our work is a general technique that we call recursive slow-down. Recursive slow-down is an algorithmic design principle that can give constant worst-case time bounds for operations on data structures. We expect this technique to have additional applications. To implement recursive slow-down, we use a scheme related to a redundant binary representation of numbers.