Numerical Representations as Purely Functional Data Structures: a New Approach

Article type: Research Article

Authors: Ivanović, Mirjana | Kunčak, Viktor

Affiliations: Faculty of Science and Mathematics, University of Novi Sad, Trg Dositeja Obradovića 4, 21000 Novi Sad, Yugoslavia. E-mail: [email protected] | Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA02139. E-mail: [email protected]

Abstract: This paper is concerned with design, implementation and verification of persistent purely functional data structures which are motivated by the representation of natural numbers using positional number systems. A new implementation of random-access list based on redundant segmented binary numbers is described. It uses 4 digits and an invariant which guarantees constant worst-case bounds for cons, head, and tail list operations as well as logarithmic time for lookup and update. The relationship of random-access list with positional number system is formalized and benefits of this analogy are demonstrated.

Keywords: data structures, purely functional language, random-accesss list, program derivation, recursive slowdown

DOI: 10.3233/INF-2002-13203

Journal: Informatica, vol. 13, no. 2, pp. 163-176, 2002