cons
empty
list
list*
empty?
cons?
list?
first
rest
list-ref
list-set
list-ref/ set
list-ref/ update
map
foldr
foldl
build-list
length
list-tail
append
reverse
in-list
Version: 4.1.5.3

Purely Functional Random-Access Lists

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

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-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 proc)  
any/c cons?
  xs : cons?
  i : natural-number/c
  proc : procedure?

Returns (values (list-ref xs i) (list-set xs i (f (list-ref xs i)))), 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.

(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 ys)  list?
  xs : list?
  ys : list?

Returns a list with all the elements of xs and ys in order. Like its pair counterpart, this operation runs in O((length xs)).

(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 inlist application can provide better performance when it appears directly in a for clause.