Purely Functional Random-Access Lists
David Van Horn
(at dvanhorn (dot ccs neu edu))
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.
Cons x onto xs.
The empty list.
Returns a list containing the given xs as its elements.
Returns a list containing the give xs as its elements
and xs as its tail.
Is x the empty list?
Is x a cons (a non-empty list)?
Is x a list?
Returns the first element of the list xs.
Returns the rest of the element of the list xs.
Returns the element of xs at position i. This operation
runs in O((min i (log2 (length xs)))).
Returns a list identical to xs, except v is the ith
element. This operation runs in O((min i (log2 (length xs)))).
Returns (values (list-ref xs i) (list-set xs i v)), but is more
Returns (values (list-ref xs i) (list-set xs i (f (list-ref xs i)))),
but is more efficient.
Applies proc to each element of xs from the first element
to the last. The result is a list containing each result of proc
Like foldr but for random-access lists. (Currently accepts
only one list).
Like foldl but for random-access lists. (Currently accepts
only one list).
Like build-list but produces a random-access list.
Returns the length of the list. This operation runs in
O((log2 (length xs))).
Returns the list after the first i elements of xs.
This operation, like its pair counterpart runs in O(i).
Returns a list with all the elements of xs and ys
in order. Like its pair counterpart, this operation runs in
Returns a list with all the elements of xs in reverse order.
Returns a sequence equivalent to xs. Since lists are sequences,
this is a list identity function, but an in-list application can
provide better performance when it appears directly in a for clause.