SRFI 101: Purely Functional Random-Access Pairs and Lists

by David Van Horn

status: final (2013/2/24)


Random-access lists [1] are a purely functional data structure for representing lists of values. A random-access list may act as a drop in replacement for the usual linear-access pair and list data structures (pair?, cons, car, cdr), which additionally supports fast index-based addressing and updating (list-ref, list-set). The impact is a whole class of purely-functional algorithms expressed in terms of index-based list addressing become feasible compared with their linear-access list counterparts.

This document proposes a library API for purely functional random-access lists consistent with the R6RS [2] base library and list utility standard library [3].