1.17.5 Comparing lists and vectors

This section describes comparison procedures for Scheme lists, vectors and objects that can be accessed like lists or like vectors.

An object x can be accessed like a vector if there are procedures size and ref such that ‘(size x)’ is a non–negative integer n indicating the number of elements, and (ref x i) is the i-th element of x for i in {0, ..., n-1}.

The default vector access procedures are vector-length and vector-ref.

An object x can be accessed like a (proper) list if there are procedures empty?, head and tail such that (empty? x) is a boolean indicating that there are no elements in x, (head x) is the first element of x, and (tail x) is an object representing the residual elements of x.

The default list access procedures are null?, car and cdr.

Independently of the way the elements are accessed, the natural ordering of vectors and lists differs. The following comparison policies are defined:

As vectors

The shorter sequence is always smaller than the longer one, no matter the elements in it. Sequences of the same size are compared lexicographically (element by element, stopping at the first different one).

As lists

The empty sequence is smallest. Two non–empty sequences are compared by their first elements, and only if the first elements are equal the residual sequences are compared, recursively.

Function: vector-compare x y

Function: vector-compare compare x y

Function: vector-compare compare x y size ref

Function: vector-compare-as-list x y

Function: vector-compare-as-list compare x y

Function: vector-compare-as-list compare x y size ref

Function: list-compare x y

Function: list-compare compare x y

Function: list-compare compare x y empty? head tail

Function: list-compare-as-vector x y

Function: list-compare-as-vector compare x y

Function: list-compare-as-vector compare x y empty? head tail

Compare two sequences x and y, using compare for comparing elements. The result is an exact integer in {-1, 0, 1}. If compare is not supplied, default-compare is used.

The procedure named access-compare-as-order accesses the objects like access and compares them with respect to the order given by order. The names type-compare are abbreviations for type-compare-as-type.

In the following examples the difference between comparison as list and comparison as vector does not show:

(list-compare '()  '())                    ⇒ 0
(list-compare '(1) '())                    ⇒ +1
(list-compare '()  '(1))                   ⇒ -1

(list-compare '(1) '(1))                   ⇒ 0
(list-compare '(1) '(2))                   ⇒ -1
(list-compare '(2) '(1))                   ⇒ +1

(list-compare '(1 1) '(1 1))               ⇒ 0
(list-compare '(1 1) '(1 2))               ⇒ -1
(list-compare '(1 2) '(1 1))               ⇒ +1

(list-compare '(1 1 1) '(1 1))             ⇒ +1
(list-compare '(1 1)   '(1 1 1))           ⇒ -1

(list-compare-as-vector '()  '())          ⇒ 0
(list-compare-as-vector '(1) '())          ⇒ +1
(list-compare-as-vector '()  '(1))         ⇒ -1

(list-compare-as-vector '(1) '(1))         ⇒ 0
(list-compare-as-vector '(1) '(2))         ⇒ -1
(list-compare-as-vector '(2) '(1))         ⇒ +1

(list-compare-as-vector '(1 1) '(1 1))     ⇒ 0
(list-compare-as-vector '(1 1) '(1 2))     ⇒ -1
(list-compare-as-vector '(1 2) '(1 1))     ⇒ +1

(list-compare-as-vector '(1 1 1) '(1 1))   ⇒ +1
(list-compare-as-vector '(1 1)   '(1 1 1)) ⇒ -1

In the following examples the difference shows:

(vector-compare         '#(1 1 1) '#(2 1)) ⇒ +1
(vector-compare-as-list '#(1 1 1) '#(2 1)) ⇒ -1