#lang scribble/doc
@(require scribble/manual
(planet cce/scheme:4:1/planet)
(only-in (for-label scheme) for sequence?)
(for-label scheme/contract)
(for-label (this-package-in main)))
@title{Purely Functional Random-Access Lists}
@(defmodule/this-package)
David Van Horn
@scheme[(at dvanhorn (dot ccs neu edu))]
This is an implementation of purely functional random-access lists that
enjoy O(1) @scheme[first] and @scheme[rest] operations and O(log n)
@scheme[list-ref] and @scheme[list-set] operations.
Random-access lists implement the sequence interface, so @scheme[(list? x)]
implies @scheme[(sequence? x)], and elements of a list may be extracted with
any of the @scheme[for] syntactic forms.
This implementation is based on Okasaki, FPCA '95.
@defproc[(cons [x any] [xs list?]) list?]{
Cons @scheme[x] onto @scheme[xs].}
@defthing[empty empty?]{
The empty list.}
@defproc[(list [x any/c] ...) list?]{
Returns a list containing the given @scheme[x]s as its elements.}
@defproc[(list* [x any/c] ... [xs list?]) list?]{
Returns a list containing the give @scheme[x]s as its elements
and @scheme[xs] as its tail.}
@defproc[(empty? [x any/c]) boolean?]{
Is @scheme[x] the empty list?}
@defproc[(cons? [x any/c]) boolean?]{
Is @scheme[x] a cons (a non-empty list)?}
@defproc[(list? [x any/c]) boolean?]{
Is @scheme[x] a list?}
@defproc[(first [xs cons?]) any]{
Returns the first element of the list @scheme[xs].}
@defproc[(rest [xs cons?]) list?]{
Returns the rest of the element of the list @scheme[xs].}
@defproc[(list-ref [xs cons?] [i natural-number/c]) any/c]{
Returns the element of @scheme[xs] at position @scheme[i]. This operation
runs in O(@scheme[(min i (log2 (length xs)))]).}
@defproc[(list-set [xs cons?] [i natural-number/c] [v any/c]) cons?]{
Returns a list identical to @scheme[xs], except @scheme[v] is the @scheme[i]th
element. This operation runs in O(@scheme[(min i (log2 (length xs)))]).}
@defproc[(list-ref/set [xs cons?] [i natural-number/c] [v any/c])
(values any/c cons?)]{
Returns @scheme[(values (list-ref xs i) (list-set xs i v))], but is more
efficient.}
@defproc[(list-ref/update [xs cons?] [i natural-number/c] [proc procedure?])
(values any/c cons?)]{
Returns @scheme[(values (list-ref xs i) (list-set xs i (f (list-ref xs i))))],
but is more efficient.}
@defproc[(map [proc procedure?] [xs list?]) list?]{
Applies @scheme[proc] to each element of @scheme[xs] from the first element
to the last. The result is a list containing each result of @scheme[proc]
in order.}
@defproc[(foldr [proc procedure?] [init any/c] [xs list?]) any]{
Like @scheme[foldr] but for random-access lists. (Currently accepts
only one list).}
@defproc[(foldl [proc procedure?] [init any/c] [xs list?]) any]{
Like @scheme[foldl] but for random-access lists. (Currently accepts
only one list).}
@defproc[(build-list [n natural-number/c] [proc procedure?]) list?]{
Like @scheme[build-list] but produces a random-access list.}
@defproc[(length [xs list?]) natural-number/c]{
Returns the length of the list. This operation runs in
O(@scheme[(log2 (length xs))]).}
@defproc[(list-tail [xs list?] [i natural-number/c]) list?]{
Returns the list after the first @scheme[i] elements of @scheme[xs].
This operation, like its pair counterpart runs in O(@scheme[i]).}
@defproc[(append [xs list?] [ys list?]) list?]{
Returns a list with all the elements of @scheme[xs] and @scheme[ys]
in order. Like its pair counterpart, this operation runs in
O(@scheme[(length xs)]).}
@defproc[(reverse [xs list?]) list?]{
Returns a list with all the elements of @scheme[xs] in reverse order.}
@defproc[(in-list [xs list?]) list?]{
Returns a sequence equivalent to @scheme[xs]. Since lists are sequences,
this is a list identity function, but an @scheme[in-list] application can
provide better performance when it appears directly in a @scheme[for] clause.}