Bootstrapping one-sided flexible arrays

ABSTRACT

The abstract data type one-sided flexible array, also called random-access list, supports look-up and update of elements and can grow and shrink at one end. We describe a purely functional implementation based on weight-balanced multiway trees that is both simple and versatile. A novel feature of the representation is that the running time of the operations can be tailored to one's needs---even dynamically at array-creation time. In particular, one can trade the running time of look-up operations for the running time of update operations. For instance, if the multiway trees have a fixed degree, the operations take θ(log n) time, where n is the size of the flexible array. If the degree doubles levelwise, look-up speeds up to θ(sqrtlog n) while update slows down to θ(2^{sqrt log n}). We show that different tree shapes can be conveniently modelled after mixed-radix number systems.

REFERENCES

• 1: A. Aasa , Sören Holmström , Christina Nilsson, An efficiency comparison of some representations of purely functional arrays, BIT, v.28 n.3, p.490-503, 1988
• 2: W. Braun and M. Rem. A logarithmic implementation of flexible arrays. Memorandum MR83/4, Eindhoven University of Technology, 1983.
• 3: Victor J. Dielissen , Anne Kaldewaij, A Simple, Efficient, and Flexible Implementation of Flexible Arrays, Mathematics of Program Construction, p.232-241, July 17-21, 1995
• 4: Anne Kaldewaij , Victor J. Dielissen, Leaf trees, Science of Computer Programming, v.26 n.1-3, p.149-165, May 1996 [doi>10.1016/0167-6423(95)00026-7]
• 5: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 6: Rolf Fagerberg, A generalization of binomial queues, Information Processing Letters, v.57 n.2, p.109-114, Jan. 29, 1996 [doi>10.1016/0020-0190(95)00194-8]
• 7: Ralf Hinze. Numerical representations as higher-order nested datatypes. Technical Report IAI-TR-98-12, Institut für Informatik III, Universität Bonn, December 1998.
• 8: Ralf Hinze. Constructing red-black trees. In Chris Okasaki, editor, Proceedings of the Workshop on Algorithmic Aspects of Advanced Programming Languages, WAAAPL'99, Paris, France, pages 89--99, September 1999. The proceedings appeared as a technical report of Columbia University, CUCS-023-99, also available from http://www.cs.columbia.edu/~cdo/waaapl.html.
• 9: Ralf Hinze, Manufacturing datatypes, Journal of Functional Programming, v.11 n.5, p.493-524, September 2001 [doi>10.1017/S095679680100404X]
• 10: Sören Holmström. A simple and efficient way to handle large datastructures in applicative languages. In Proceedings of the Joint SERC/Chalmers Workshop on Declarative Programming, University College, London, UK, 1983.
• 11: Rob R. Hoogerwoord, A Logarithmic Implementation of Flexible Arrays, Proceedings of the Second International Conference on Mathematics of Program Construction, p.191-207, June 29-July 03, 1992
• 12: Haim Kaplan , Robert E. Tarjan, Purely functional representations of catenable sorted lists, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.202-211, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237865]
• 13: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 14: Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
• 15: Chris Okasaki, Purely functional random-access lists, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.86-95, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224187]
• 16: Chris Okasaki, Purely functional data structures, Cambridge University Press, New York, NY, 1998
• 17: Chris Okasaki and Andy Gill. Fast mergeable integer maps. In The 1998 ACM SIGPLAN Workshop on ML, Baltimore, Maryland, pages 77--86, 1998.
• 18: Melissa E. O'Neill , F. Warren Burton, A new method for functional arrays, Journal of Functional Programming, v.7 n.5, p.487-513, September 1997 [doi>10.1017/S0956796897002852]
• 19: Simon Peyton Jones {editor}, John Hughes {editor}, Lennart Augustsson, Dave Barton, Brian Boutel, Warren Burton, Simon Fraser, Joseph Fasel, Kevin Hammond, Ralf Hinze, Paul Hudak, Thomas Johnsson, Mark Jones, John Launchbury, Erik Meijer, John Peterson, Alastair Reid, Colin Runciman, and Philip Wadler. Standard libraries for the Haskell 98 programming language. Available from http://www.haskell.org/definition/, February 1999.
• 20: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 21: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.3 Language Constructs and Features

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Arrays

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Performance

Keywords:
Haskell, flexible arrays, mixed-radix number systems, purely functional data structures, sub-logarithmic look-up