2.2.5.3 Predicates

Note: the predicates proper-list?, circular-list?, and dotted-list? partition the entire universe of Scheme values.

Function: proper-list? x

Return true if, and only if, x is a proper list: a finite, nil–terminated list. More carefully: The empty list is a proper list. A pair whose cdr is a proper list is also a proper list:

<proper-list> ::= ()                            (Empty proper list)
              |   (cons <x> <proper-list>)      (Proper-list pair)

Note that this definition rules out circular lists. This function is required to detect this case and return false.

Nil–terminated lists are called “proper” lists by R5RS and Common Lisp. The opposite of proper is improper.

R5RS binds this function to the variable list?.

(not (proper-list? x)) = (or (dotted-list? x) (circular-list? x))

Function: circular-list? x

True if x is a circular list. A circular list is a value such that for every n >= 0, cdrn(x) is a pair.

Terminology: The opposite of circular is finite.

(not (circular-list? x)) = (or (proper-list? x) (dotted-list? x))

Function: dotted-list? x

True if x is a finite, non–nil–terminated list. That is, there exists an n >= 0 such that cdrn(x) is neither a pair nor (). This includes non–pair, non–() values (e.g. symbols, numbers), which are considered to be dotted lists of length 0.

(not (dotted-list? x)) = (or (proper-list? x) (circular-list? x))

Function: pair? object

R5RS Return #t if object is a pair; otherwise #f.

(pair? '(a . b)) =>  #t
(pair? '(a b c)) =>  #t
(pair? '())      =>  #f
(pair? '#(a b))  =>  #f
(pair? 7)        =>  #f
(pair? 'a)       =>  #f

Function: null? object

R5RS Return #tt if object is the empty list; otherwise #f.

Function: null-list? list

list is a proper or circular list. This procedure returns true if the argument is the empty list (), and #f otherwise. It is an error to pass this procedure a value which is not a proper or circular list. This procedure is recommended as the termination condition for list–processing procedures that are not defined on dotted lists.

Function: not-pair? x

Defined as: (lambda (x) (not (pair? x))). Provided as a procedure as it can be useful as the termination condition for list–processing procedures that wish to handle all finite lists, both proper and dotted.

Function: list= elt= list1 ...

Determines list equality, given an element–equality procedure elt=. Proper list AL equals proper list BL if they are of the same length, and their corresponding elements are equal, as determined by elt=. If the element–comparison procedure’s first argument is from listi, then its second argument is from listi+1, i.e. it is always called as (elt= a b) for a an element of list AL, and b an element of list BL.

In the n–ary case, every listi is compared to listi+1 (as opposed, for example, to comparing list1 to every listi, for i>1). If there are no list arguments at all, list= simply returns true.

It is an error to apply list= to anything except proper lists. While implementations may choose to extend it to circular lists, note that it cannot reasonably be extended to dotted lists, as it provides no way to specify an equality procedure for comparing the list terminators.

Note that the dynamic order in which the elt= procedure is applied to pairs of elements is not specified. For example, if list= is applied to three lists, AL, BL, and CL, it may first completely compare AL to BL, then compare BL to CL, or it may compare the first elements of AL and BL, then the first elements of BL and CL, then the second elements of AL and BL, and so forth.

The equality procedure must be consistent with eq?. That is, it must be the case that:

(eq? x y) => (elt= x y)

Note that this implies that two lists which are eq? are always list=, as well; implementations may exploit this fact to “short–cut” the element–by–element comparisons.

(list= eq?) => #t       ; Trivial cases
(list= eq? '(a)) => #t