Purely Functional Random-Access Lists

David Van Horn <dvanhorn at ccs dot neu dot edu>

    1 Bindings

    2 Contract

    3 Tests

    4 Benchmarks

This is an implementation of purely functional random-access lists that enjoy O(1) first and rest operations and O(log n) list-ref and list-set operations.

Random-access lists implement the sequence interface, so (list? x) implies (sequence? x), and elements of a list may be extracted with any of the for syntactic forms.

This implementation is based on Okasaki, FPCA ’95.