Version: 4.1.5.4

## Purely Functional Random-Access Lists

 (require (planet dvanhorn/ralist:1:6))

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 xs) → list? x : any xs : list?

Cons x onto xs.

 empty : empty?

The empty list.

 (list x ...) → list? x : any/c

Returns a list containing the given xs as its elements.

 (list* x ... xs) → list? x : any/c xs : list?

Returns a list containing the give xs as its elements and xs as its tail.

 (empty? x) → boolean? x : any/c

Is x the empty list?

 (cons? x) → boolean? x : any/c

Is x a cons (a non-empty list)?

 (list? x) → boolean? x : any/c

Is x a list?

 (first xs) → any xs : cons?

Returns the first element of the list xs.

 (rest xs) → list? xs : cons?

Returns the rest of the element of the list xs.

 (list-ref xs i) → any/c xs : cons? i : natural-number/c

Returns the element of xs at position i. This operation runs in O((min i (log2 (length xs)))).

 (list-set xs i v) → cons? xs : cons? i : natural-number/c v : any/c

Returns a list identical to xs, except v is the ith element. This operation runs in O((min i (log2 (length xs)))).

 (list-update xs i f) → cons? xs : cons? i : natural-number/c f : procedure?

Returns (list-set xs i (f (list-ref xs i))).

(list-ref/set xs i v)
 any/c cons?
xs : cons?
i : natural-number/c
v : any/c

Returns (values (list-ref xs i) (list-set xs i v)), but is more efficient.

(list-ref/update xs i f)
 any/c cons?
xs : cons?
i : natural-number/c
f : procedure?

Returns (values (list-ref xs i) (list-set xs i (f (list-ref xs i)))), but is more efficient.

 (map f xs ...+) → list? f : procedure? xs : list?

Applies f to each element of xss from the first element to the last. The f argument must accept the same number of arguments as the number of supplied xss. The result is a list containing each result of proc in order.

 (foldr proc init xs ...+) → any proc : procedure? init : any/c xs : list?

Like foldr but for random-access lists.

 (foldl proc init xs ...+) → any proc : procedure? init : any/c xs : list?

Like foldl but for random-access lists.

 (andmap proc xs ...+) → any proc : procedure? xs : list?

Like andmap but for random-access lists.

 (ormap proc xs ...+) → any proc : procedure? xs : list?

Like ormap but for random-access lists.

 (make-list n x) → list? n : natural-number/c x : any?

Returns a list with n elements, all of which are x. Equivalent to (build-list n (lambda (i) x)).

 (build-list n proc) → list? n : natural-number/c proc : procedure?

Like build-list but produces a random-access list.

 (length xs) → natural-number/c xs : list?

Returns the length of the list. This operation runs in O((log2 (length xs))).

 (list-tail xs i) → list? xs : list? i : natural-number/c

Returns the list after the first i elements of xs. This operation, like its pair counterpart runs in O(i).

 (append xs ...) → list? xs : list?

Returns a list with all the elements of the given lists in order.

 (reverse xs) → list? xs : list?

Returns a list with all the elements of xs in reverse order.

 (in-list xs) → list? xs : list?

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.