SRFI 101: Purely Functional Random-Access Pairs and Lists

by David Van Horn

status: final (2013-02-24)

keywords: Data Structure, R7RS Large, R7RS Large: Red Edition

• The SRFI Document
• Discussion Archive
• Git repo (on GitHub)
• srfi-101@nospamsrfi.schemers.org (subscribers only)
• Subscribe to srfi-101 mailing list

  daily digest?

• Unsubscribe from srfi-101 mailing list

Abstract

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 R⁶RS [2] base library and list utility standard library [3].