RaList: Purely Functional Random-Access Lists

David Van Horn <dvanhorn@ccs.neu.edu>

Random-access lists 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 sequential list data structure (cons?, cons, car, cdr), which additionally supports fast index-based addressing and updating (list-ref, list-set).

This document outlines the API for the random-access list library. This implementation is based on Okasaki, FPCA ’95.

Report a bug.

    1 Bindings

      1.1 Checked and Unchecked contracts

      1.2 Pairs and Lists

      1.3 Sequences

      1.4 Iterations and Comprehensions

      1.5 Match patterns

      1.6 Values

    2 Contract

    3 Tests

      3.1 Tree tests

      3.2 RaList tests

      3.3 Garden fence tests

      3.4 Frequency counting tests

    4 Benchmarks

      4.1 Random-access vs. Sequential-access lists

      4.2 Contracted vs. Uncontracted bindings

      4.3 Frequency counting

      4.4 Garden fence encryption