dvanhorn @ λ-calcul.us

A new SRFI for purely functional random-access lists:

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, sequential 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 sequential-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.