Purely Functional Random-Access Lists

(require (planet dvanhorn/ralist))

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.

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.

(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,log(n))).

(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,log(n))).

(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.

(map proc xs) → list?

proc : procedure?

xs : list?

Applies proc to each element of xs from the first element to the last. 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. (Currently accepts only one list).

(foldl proc init xs) → any

proc : procedure?

init : any/c

xs : list?

Like foldl but for random-access lists. (Currently accepts only one list).

(build-list n proc) → list?

n : natural-number/c

proc : procedure?

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