Next: lists conventions, Up: lists [Index]
Scheme does not properly have a list type, just as the C language does not have a string type. Rather, Scheme has a binary–tuple type, from which one can build binary trees. There is an interpretation of Scheme values that allows one to treat these trees as lists. Further complications ensue from the fact that Scheme allows side–effects to these tuples, raising the possibility of lists of unbounded length, and trees of unbounded depth (that is, circular data structures).
What follows is a classification of concrete values with respect to list as an abstract concept.
It is a special value which can be identified with the predicate
null?. Null is meant to represent empty lists and to be the
terminator for proper lists.
length applied to null returns zero. In light of what follows,
it makes sense to consider null as a list of length zero for all the
list classes: proper, circular, dotted, generalised.
A finite, null–terminated list; more precisely a proper list is defined as: A pair whose cdr is a proper list or null. The opposite of proper is improper; everything that is not null or a proper list, is an improper list.
(a b c) (32)
We can build a proper list in a single function call with list,
or we can do it in steps using cons and cons*; we can
detect if a list is proper with list?.
An infinite, unterminated list; a circular list is a value such that
cdr applied any number of times always returns a pair. The
opposite of circular is finite.
We can build a list having a circular tail as follows:
(define end (cons 1 '())) (define tail (cons* 3 2 end)) (define ell (cons* 5 4 tail)) (set-cdr! end tail)
the list structure bound to ‘ell’ looks like this:
cdr
----------------
| |
cdr cdr v cdr cdr |
O----->O----->O----->O----->O--
| | | | |
car| car| car| car| car|
v v v v v
5 4 3 2 1
so that the following happens:
(car ell) ⇒ 5 (cadr ell) ⇒ 4 (caddr ell) ⇒ 3 (cadddr ell) ⇒ 2 (cadddr (cdr ell)) ⇒ 1 (cdddr (cddr ell)) ⇒ tail (cadddr (cddr ell)) ⇒ 3 (cadddr (cdddr ell)) ⇒ 2
it is impossible to build a circular list without mutating a pair. Notice that the following is not a circular list:
car
--------------------
| |
cdr v cdr cdr cdr | cdr
O----->O----->O----->O----->O----->()
| | | |
car| car| car| car|
v v v v
5 4 3 2
it is a proper list in which the car of the last pair references one of the previous pairs.
We can build a circular list, a ring, with circular-list and we
can detect if a list is a ring or has a circular tail with
circular-list?.
A finite, non–nil terminated list, such as:
(a b c . d) (x . y)
a dotted list is a value for which there exists an integer n > 0,
such that cdr applied n times yields neither a pair nor
null. This means that, for a dotted list, either null? or
pair? return #t.
Users of the (vicare containers lists ---) libraries should note
that dotted lists are not commonly used, and are considered by many
Scheme programmers to be an ugly artifact of Scheme’s lack of a true
list type. However, dotted lists do play a noticeable role in the
syntax of Scheme, in the “rest” parameters used by n–ary lambdas:
(lambda (x y . rest) ---)
Dotted lists are not fully supported by the list libraries; most procedures are defined only on proper lists. The procedures that will also handle circular or dotted lists are specifically marked. While this design decision restricts the domain of possible arguments one can pass to these procedures, it has the benefit of allowing the procedures to catch the error cases where programmers inadvertently pass scalar values to a list procedure by accident (for example, by switching the arguments to a procedure call).
A finite, non–nil terminated list, such as:
(a b c . d) (x . y) 42 george
a improper list is a value for which there exists an integer n >=
0, such that cdr applied n times yields neither a pair
nor null. This includes non–pair, non–null values (symbols, numbers,
etc.), which are considered to be improper lists of length 0.
Dotted lists are improper lists.
Next: lists conventions, Up: lists [Index]