Haim Kaplan
Robert E. Tarjan
Abstract
We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding 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 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 used to avoid carry propagation in binary counting.
- ALLEN, J. 1978. Anatomy of LISP. McGraw-Computer Science Series. McGraw-Hill, New York. Google Scholar
- BRODAL, G. S. 1996. Worst-case efficient priority queues. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 52-58. Google Scholar
- BUCHSBAUM,A.L.,SUNDAR, R., AND TARJAN, R. E. 1995. Data structural bootstrapping, linear path compression, and catenable heap ordered double ended queues. SIAM J. Computing 24,6, 1190-1206. Google Scholar
- BUCHSBAUM,A.L.,AND TARJAN, R. E. 1995. Confluently persistant deques via data structural bootstrapping. J. Algorithms 18, 513-547. Google Scholar
- BURTON, F. W. 1982. An efficient functional implementation of FIFO queues. Inf. Proc. Lett. 14,5, 205-206.Google Scholar
- CHAZELLE, B. 1985. How to search in history. Inf. Control 64, 77-99. Google Scholar
- CHAZELLE, B., AND GUIBAS, L. J. 1986. Fractional cascading: I. a data structuring technique. Algorithmica 1, 2, 133-162.Google Scholar
- CHUANG, T.-R., AND GOLDBERG, B. 1993. Real-time deques, multihead turing machines, and purely functional programming. In Proceedings of the Conference on Functional Programming and Computer Architecture. (Copenhagen). ACM, New York, pp. 289-298. Google Scholar
- CLANCY,M.J.,AND KNUTH, D. E. 1977. A programming and problem-solving seminar. Tech. Rep. STAN-CS-77-606. Department of Computer Science, Stanford University, Palo Alto, Calif. Google Scholar
- COLE, R. 1986. Searching and storing similar lists. J. Algorithms 7, 202-220. Google Scholar
- DIETZ, P. F. 1995. Fully persistent arrays. In Proceedings of the 1989 Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science. Springer-Verlag, New York, pp. 67-74. Google Scholar
- DOBKIN,D.P.,AND MUNRO, J. I. 1985. Efficient uses of the past. J. Algorithms 6, 455-465.Google Scholar
- DRISCOLL,J.R.,SARNAK, N., SLEATOR, D., AND TARJAN, R. 1989. Making data structures persistent. J. Comput. Syst. Sci. 38, 86-124. Google Scholar
- DRISCOLL, J., SLEATOR, D., AND TARJAN, R. 1994. Fully persistent lists with catenation. J. ACM 41, 5 (Sept.), 943-959. Google Scholar
- FELLEISEN, M. 1988. The theory and practice of first-class prompts. In Proceedings of the 15th ACM Symposium on Principles of Programming Languages (San Diego, Calif., Jan. 15-17). ACM, New York, pp. 180-190. Google Scholar
- FELLEISEN, M., WAND, M., FRIEDMAN,D.P.,AND DUBA, B. F. 1988. Abstract continuations: A mathematical semantics for handling full functional jumps. In Proceedings of the Conference on Lisp and Functional Programming (Snowbird, Ut., July 25-27). ACM, New York, pp. 52-62. Google Scholar
- FISHER,P.C.,MEYER,A.R.,AND ROSENBERG, A. L. 1972. Real-time simulation of multihead tape units. J. ACM 19, 4 (Oct.), 590-607. Google Scholar
- FREDERICKSON, G. N. 1993. Optimal selection in a min-heap. Inf. Comput. 104, 197-214. Google Scholar
- GAJEWSKA, H., AND TARJAN, R. E. 1986. Deques with heap order. Inf. Proc. Lett. 12, 4, 197-200. Google Scholar
- GRIES, D. 1981. The Science of Programming. In Texts and Monographs in Computer Science. Springer-Verlag, New York. Google Scholar
- HOOD, R. 1982. The efficient implementation of very-high-level programming language constructs. Ph.D. dissertation. Dept. of Computer Science, Cornell Univ. Ithaca, N.Y. Google Scholar
- HOOD, R., AND MELVILLE, R. 1981. Real-time queue operations in pure Lisp. Inf. Proc. Lett. 13, 50-54.Google Scholar
- HOOGERWOOD, R. R. 1992. A symmetric set of efficient list operations. J. Funct. Prog. 2,4, 505-513.Google Scholar
- JOHNSON,G.F.,AND DUGGAN, D. 1988. Stores and partial continuations as first-class objects in a language and its environment. In Proceedings of the 15th ACM Symposium on Principles of Programming Languages (San Diego, Calif., Jan. 15-17). ACM, New York, pp. 158-168. Google Scholar
- KAPLAN, H. 1996. Purely functional lists. Ph.D. dissertation. Dept. Computer Science, Princeton Univ., Princeton, N.J. Google Scholar
- KAPLAN, H., OKASAKI, C., AND TARJAN, R. E. 1998. Simple confluently persistent catenable lists (extended abstract). In Proceedings of the 6th Scandanavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 1432. Springer-Verlag, New York, pp. 119-130. Google Scholar
- KAPLAN, H., AND TARJAN, R. E. 1995. Persistent lists with catenation via recursive slow-down. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 93-102. Google Scholar
- KAPLAN, H., AND TARJAN, R. E. 1996. Purely functional representations of catenable sorted lists. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 202-211. Google Scholar
- KNUTH, D. E. 1973. Fundamental Algorithms, 2nd ed. Vol. 1, The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, second edition, 1973. Google Scholar
- KOSARAJU, S. R. 1979. Real-time simulation of concatenable double-ended queues by double-ended queues. In Proceedings of the 11th ACM Symposium on Theory of Computing (Atlanta, Ga., Apr. 30-May 2). ACM, New York, pp. 346-351. Google Scholar
- KOSARAJU, S. R. 1994. An optimal RAM implementation of catenable min double-ended queues. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 195-203. Google Scholar
- LEONG,B.L.,AND SEIFERAS, J. I. 1981. New real-time simulations of multihead tape units. J. ACM 28, 1, 166-180. Google Scholar
- OKASAKI, C. 1995. Amortization, lazy evaluation, and persistence: lists with catenation via lazy linking. In Proceedings of the 36th Symposium on Foundations of Computer Science. IEEE, New York, pp. 646-654. Google Scholar
- OKASAKI, C. 1995. Simple and efficient purely functional queues and deques. J. Funct. Prog. 5,4, 583-592.Google Scholar
- OKASAKI, C. 1998. Purely functional data structures. Cambridge University Press, Cambridge, Mass. Google Scholar
- OKASAKI, C. 1997. Catenable double-ended queues. In Proceedings of the ACM SIGPLAN Interna-tional Conference on Functional Programming. ACM, New York, pp. 66-74. Google Scholar
- OVERMARS, M. H. 1981a. Searching in the past. I. Tech. Rep. RUU-CS-81-7. Dept. Computer Science, Univ. Utrecht, Utrecht, The Netherlands.Google Scholar
- OVERMARS, M. H. 1981b. Searching in the past. II: General transforms. Tech. Rep. RUU-CS-81-9. Dept. Computer Science, Univ. Utrecht, Utrecht, The Netherlands.Google Scholar
- SARNAK, N. 1986. Persistent data structures. Ph.D. dissertation. Dept. of Computer Science, New York University, New York. Google Scholar
- SARNAK, N., AND TARJAN, R. E. 1986. Planar point location using persistent search trees. Commun. ACM 29, 7 (July), 669-679. Google Scholar
- SITARAM, D., AND FELLEISEN, M. 1990. Control delimiters and their hierarchies. LISP and Symbolic Computation: An International Journal 3, 67-99. Google Scholar
- SPITZER,J.M.,LEVITT,K.N.,AND ROBINSON, L. 1978. An example of hierarchical design and proof. Commun. ACM 21, 12 (Dec.), 1064-1075. Google Scholar
- STOSS, H.-J. 1970. K-band simulation von k-kopf-turing-maschinen. Computing 6, 3, 309-317.Google Scholar
- TARJAN, R. E. 1985. Amortized computational complexity. SIAM J. Alg. Disc. Meth. 6, 2, 306-318.Google Scholar
- TARJAN,R.E.,AND VAN LEEUWEN, J. 1984. Worst case analysis of set union algorithms. J. ACM 31, 1 (Mar.), 245-281. Google Scholar
Index Terms
- Purely functional, real-time deques with catenation
Recommendations
Fully persistent lists with catenation
This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution ...
Amortization, lazy evaluation, and persistence: lists with catenation via lazy linking
FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer ScienceAmortization has been underutilized in the design of persistent data structures, largely because traditional accounting schemes break down in a persistent setting. Such schemes depend on saving "credits" for future use, but a persistent data structure ...
Reviews
Susan M. Merritt
A real-time, purely functional implementation of deques with catenation is presented. The authors demonstrate that their data structure is both more efficient and simpler than previously proposed structures. They note that, in addition to being an interesting problem, the data structure provides a way to add fast catenation to list-based programming languages. The paper is extremely well written and clear. The authors discuss related work, at some length, from three areas of computer science—data structures, functional programming, and Turing machine complexity. The first result uses a Turing machine model to make a catenable list “fully persistent” (that is, old versions of the list exist even when the list is modified). Next, the authors use the notion of “recursive slow-down,” that is, the opportunity for an O 1 time bound for operations on a data structure if each operation requires O 1 time plus half an operation for a smaller recursive substructure. Then a simpler example of the first two concepts is given: a real-time, purely functional deque without catenation. Next, a catenable steque (deque without eject) is presented. Finally, from all of the previous ideas, a data structure is implemented that supports the full set of deque operations ( push, pop, inject, and eject ), and catenate, each in O 1 time. The set of references is excellent and comprehensive. The paper is a good exposition of an interesting and challenging problem with an ultimately simple solution. The authors finish with additive results, recent work, and open problems.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments