2.33.3 Rationale

Functional programming and list hacking go together like peanut butter and jelly, eval and apply, syntax and semantics, or cursing and recursing. But the traditional approach to implementing pairs and lists results in index–based access (list-ref) requiring time proportional the index being accessed. Moreover, indexed–based functional update (list-set) becomes so inefficient as to be nearly unspeakable. Instead, programmers revert the imperatives of the state; they use a stateful data structure and imperative algorithms.

This SRFI intends to improve the situation by offering an alternative implementation strategy based on Okasaki’s purely functional random–access lists [1]. Random–access pairs and lists can be used as a replacement for traditional, linear–access pairs and lists with no asymptotic loss of efficiency. In other words, the typical list and pair operations such as cons, car, and cdr, all operate in O(1) time as usual. However, random–access lists additionally support index–based access and functional update operations that are asymptotically cheaper; O(\log(n)) for random–access lists versus O(n) for linear–access lists, where n is the length of the list being access or updated. As such, many purely functional index–based list algorithms become feasible by using a random–access list representation for pairs and lists.

The requirements of this SRFI have been designed in such a way as to admit portable library implementations of this feature, such as the reference implementation, while at the same time admit more radical implementations that embrace random–access pairs as the fundamental pair representation.