Next: srfi ralists spec repre, Up: srfi ralists spec [Index]
A random–access pair (or just pair) is a compound structure with two
fields called the car and the cdr fields (consistent with the historical
naming of pair fields in Scheme). Pairs are created by the procedure
cons. The car and cdr fields are accessed by the procedures
car and cdr.
Pairs are used primarily to represents lists. A list can be defined recursively as either the empty list or a pair whose cdr is a list. More precisely, the set of lists is defined as the smallest set X such that
The objects in the car fields of successive pairs of a list are the elements of the list. For example, a two–element list is a pair whose car is the first element and whose cdr is a pair whose car is the second element and whose cdr is the empty list. The length of a list is the number of elements, which is the same as the number of pairs.
The empty list is a special object of its own type. It is not a pair. It has no elements and its length is zero.
NOTE The above definitions imply that all lists have finite length and are terminated by the empty list.
A chain of pairs is defined recursively as either a non–pair object or a pair whose cdr is a chain of pairs (Note: every value is a chain of pairs). A chain of pairs ending in the empty list is a list. A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. Whether a given pair is a list depends upon what is stored in the cdr field.
The external representation of pairs is not specified by this SRFI, however the examples below do use the typical notation for writing pair and list values.
Random–access pairs and lists are specified to be fully functional, or,
to use the term from the academic literature, fully persistent [1].
Full persistence means that all operations on random–access lists,
notably including cons, list-ref, list-set, and
list-ref/update, are specified
It is usually taken for granted that standard Scheme lists have these properties. This SRFI explicitly specifies that random–access lists share them.
Syntax: ?datum should be a syntactic datum.
Semantics: (quote ?datum) evaluates to the datum value
represented by ?datum (see section 4.3 of R6RS). This
notation is used to include constants.
When the datum value represented by ?datum contains pair structure, quote produces random–access pairs.
(quote a) ⇒ a (quote #(a b c)) ⇒ #(a b c) (quote (+ 1 2)) ⇒ (+ 1 2)
As noted in section 4.3.5 of R6RS, (quote ?datum) may
be abbreviated as '?datum:
'"abc" ⇒ "abc" '145932 ⇒ 145932 'a ⇒ a '#(a b c) ⇒ #(a b c) '() ⇒ () '(+ 1 2) ⇒ (+ 1 2) '(quote a) ⇒ (quote a) ''a ⇒ (quote a)
As noted in section 5.10 of R6RS, constants are immutable.
NOTE Different constants that are the value of quote expression may share the same locations.
The equal? predicate returns #t if and only if the (possibly
infinite) unfoldings of its arguments into regular trees are equal as
ordered trees.
The equal? predicate treats pairs and vectors as nodes with
outgoing edges, uses string=? to compare strings, uses
bytevector=? to compare bytevectors, and uses eqv? to
compare other nodes.
(equal? 'a 'a) ⇒ #t
(equal? '(a) '(a)) ⇒ #t
(equal? '(a (b) c)
'(a (b) c)) ⇒ #t
(equal? "abc" "abc") ⇒ #t
(equal? 2 2) ⇒ #t
(equal? (make-vector 5 'a)
(make-vector 5 'a)) ⇒ #t
(equal? '#vu8(1 2 3 4 5)
(u8-list->bytevector
'(1 2 3 4 5)) ⇒ #t
(equal? (lambda (x) x)
(lambda (y) y)) ⇒ unspecified
(let* ((x (list 'a))
(y (list 'a))
(z (list x y)))
(list (equal? z (list y x))
(equal? z (list x x)))) ⇒ (#t #t)
Return #t if obj is a pair, and otherwise returns #f.
This operation must take O(1) time.
(pair? '(a . b)) ⇒ #t (pair? '(a b c)) ⇒ #t (pair? '()) ⇒ #f (pair? '#(a b)) ⇒ #f
Return a newly allocated pair whose car is obj1 and whose cdr is
obj2. The pair is guaranteed to be different (in the sense of
eqv?) from every existing object. This operation must take
O(1) time.
(cons 'a '()) ⇒ (a)
(cons '(a) '(b c d)) ⇒ ((a) b c d)
(cons "a" '(b c)) ⇒ ("a" b c)
(cons 'a 3) ⇒ (a . 3)
(cons '(a b) 'c) ⇒ ((a b) . c)
Return the contents of the car field of pair. This operation must take O(1) time.
(car '(a b c)) ⇒ a (car '((a) b c d)) ⇒ (a) (car '(1 . 2)) ⇒ 1 (car '()) error→ &assertion exception
Return the contents of the cdr field of pair. This operation must take O(1) time.
(cdr '((a) b c d)) ⇒ (b c d) (cdr '(1 . 2)) ⇒ 2 (cdr '()) error→ &assertion exception
These procedures are compositions of car and cdr, where for example
caddr could be defined by:
(define caddr
(lambda (x)
(car (cdr (cdr x)))))
Arbitrary compositions, up to four deep, are provided. There are twenty–eight of these procedures in all. These operations must take O(1) time.
Return #t if obj is the empty list, #f otherwise. This
procedure is equivalent to the null? procedure of the R6RS
base library.
Return #t if obj is a list, #f otherwise. By
definition, all lists are chains of pairs that have finite length and
are terminated by the empty list. This operation must take time bounded
by O(\log(n)), where n is the number of pairs in the chain
forming the potential list.
(list? '(a b c)) ⇒ #t (list? '()) ⇒ #t (list? '(a . b)) ⇒ #f
Return a newly allocated list of its arguments. This operation must take time bounded by O(n), where n is the number of arguments to list.
(list 'a (+ 3 4) 'c) ⇒ (a 7 c) (list) ⇒ ()
Return a newly allocated list of k elements. If a second argument is given, then each element is initialized to obj. Otherwise the initial contents of each element is unspecified. This operation must take time and space bounded by O(\log(k)).
(make-list 5 0) ⇒ (0 0 0 0 0)
Return the length of list. This operation must take time bounded by O(\log(n)), where n is the length of the list.
(length '(a b c)) ⇒ 3 (length '(a (b) (c))) ⇒ 3 (length '()) ⇒ 0
Return true if obj is a chain of at least k pairs and
#f otherwise. This operation must take time bounded by
O(\log(\min(k,n))), where n is the length of the chain of
pairs.
(length<=? 'not-a-list 0) ⇒ #t (length<=? '(a . b) 0) ⇒ #t (length<=? '(a . b) 1) ⇒ #t (length<=? '(a . b) 2) ⇒ #f
Return a chain of pairs consisting of the elements of the first list followed by the elements of the other lists, with obj as the cdr of the final pair. An improper list results if obj is not a list. This operation must take time bounded by O(\log(n)), where n is the total number of elements in the given lists.
(append '(x) '(y)) ⇒ (x y) (append '(a) '(b c d)) ⇒ (a b c d) (append '(a (b)) '((c))) ⇒ (a (b) (c)) (append '(a b) '(c . d)) ⇒ (a b c . d) (append '() 'a) ⇒ a
Return a newly allocated list consisting of the element of list in reverse order. This operation must take time bounded by O(n) where n is the length of the list.
(reverse '(a b c)) ⇒ (c b a) (reverse '(a (b c) 'd '(e (f)))) ⇒ ((e (f)) d (b c) a)
obj should be a chain of pairs with a count of at least k.
The list-tail procedure returns the object obtained by omitting
the first k elements in obj. This operation must take time
bounded by O(\log(\min(k,n))), where n is the length of
the chain of pairs.
(list-tail '(a b c d) 0) ⇒ (a b c d) (list-tail '(a b c d) 2) ⇒ (c d) (list-tail 'not-a-list 0) ⇒ not-a-list
Implementation responsibilities: The implementation must check that obj is a chain of pairs whose count is at least k.
pair must be a chain of pairs whose count is at least k +
1. The list-ref procedure returns the k-th element of
pair. This operation must take time bounded by
O(\min(k,\log(n))), where n is the length of the chain of
pairs.
(list-ref '(a b c d) 2) ⇒ c
Implementation responsibilities: The implementation must check that pair is a chain of pairs whose count is at least k + 1.
pair must be a chain of pairs whose count is at least k +
1. The list-set procedure returns the chain of pairs obtained
by replacing the k-th element with obj. This operation must
take time bounded by O(\min(k,\log(n))), where n is the
length of the chain of pairs.
(list-set '(a b c d) 2 'x) ⇒ (a b x d)
Implementation responsibilities: The implementation must check that pair is a chain of pairs whose count is at least k + 1.
Return the same results as:
(values (list-ref pair k)
(list-set pair k (proc (list-ref pair k))))
but it may be implemented more efficiently.
(list-ref/update '(7 8 9 10) 2 -) ⇒ 9 (7 8 -9 10)
The lists should all have the same length. proc should accept as many arguments as there are lists and return a single value.
The map procedure applies proc element–wise to the
elements of the lists and returns a list of the results, in order.
proc is always called in the same dynamic environment as
map itself. The order in which proc is applied to the
elements of the lists is unspecified.
(map cadr '((a b) (d e) (g h)))
⇒ (b e h)
(map (lambda (n)
(expt n n))
'(1 2 3 4 5))
⇒ (1 4 27 256 3125)
(map + '(1 2 3) (4 5 6))
⇒ (5 7 9)
(let ((count 0))
(map (lambda (ignored)
(set! count (+ count 1))
count)
'(a b)))
⇒ (1 2) or (2 1)
Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.
The lists should all have the same length. proc should accept as many arguments as there are lists.
The for-each procedure applies proc element–wise to the
elements of the lists for its side effects, in order from the first
element to the last. proc is always called in the same dynamic
environment as for-each itself. The return values of
for-each are unspecified.
(let ((v (make-vector 5)))
(for-each (lambda (i)
(vector-set! v i (* i i)))
'(0 1 2 3 4))
v)
⇒ #(0 1 4 9 16)
(for-each (lambda (x) x) '(1 2 3 4))
⇒ unspecified
(for-each even? '())
⇒ unspecified
Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.
NOTE Implementations of
for-eachmay or may not tail–call proc on the last element.
Next: srfi ralists spec repre, Up: srfi ralists spec [Index]