LISP and Symbolic Computation, 2(2)105-113
Arrays in Pure Functional Programming LanguagesKlaus E. Grue, DIKU, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen East, Denmark
|
Abstract: In pure functional programs it is common to represent
arrays by association lists. Association lists have the disadvantage
that the access time varies linearly both with the size of the array
(counted in number of entries) and with the size of the index (counted
in cons nodes). This paper presents another simple representation of
arrays for which the access time varies linearly in the size of the
index but is independent of the size of the array. The paper compares
this representation with association lists in functional languages and
arrays in imperative languages.
This paper also considers lazy programming and states how to use potentially infinite arrays for time optimization for certain programs. |
This article is not available online.
![[picture of journal cover]](../LISP.JPG)