2.28.5.6 Using compare procedures

The facilities defined in this section provide a mechanism for using a compare procedure (passed as a parameter) in the different situations arising in applications.

Syntax: if3 ?C ?less ?equal ?greater

Syntax: ?C, ?less, ?equal, and ?greater are expressions.

Semantics: if3 is the 3-way conditional for comparisons. First ?C is evaluated, resulting in value C. The value C must be an exact integer in {-1, 0, +1}, otherwise an error is signalled.

• If C = -1 then the value of the if3–expression is obtained by evaluating ?less.
• If C = 0 then ?equal is evaluated.
• If C = 1 then ?greater is evaluated.

NOTE As an example, the following procedure inserts x into the sorted list s, possibly replacing the first equivalent element.

(define (insert compare x s)
  (if (null? s)
      (list x)
    (if3 (compare x (car s))
         (cons x s)
         (cons x (cdr s)) ; replace
         (cons (car s) (insert compare x (cdr s))))))

RATIONALE if3 is the preferred way of branching on the result of a comparison in case all three branches are different.

Syntax: if=? ?C ?consequent

Syntax: if=? ?C ?consequent ?alternate

Syntax: if<? ?C ?consequent

Syntax: if<? ?C ?consequent ?alternate

Syntax: if>? ?C ?consequent

Syntax: if>? ?C ?consequent ?alternate

Syntax: if<=? ?C ?consequent

Syntax: if<=? ?C ?consequent ?alternate

Syntax: if>=? ?C ?consequent

Syntax: if>=? ?C ?consequent ?alternate

Syntax: if-not=? ?C ?consequent

Syntax: if-not=? ?C ?consequent ?alternate

Syntax: ?C, ?consequent, and ?alternate are expressions. If ?alternate is not provided, (if #f #f) is used.

Semantics: These six macros are 2-way conditionals for comparisons. First ?C is evaluated, resulting in value C. The value C must be an exact integer in {-1, 0, +1}, otherwise an error is signalled. Then, depending on the value of C and the name of the macro, either ?consequent or ?alternate is evaluated, and the resulting value is the value of the conditional expression.

The branch is chosen according to the following table:

	?consequent	?alternate
if=?	C = 0	C \in {-1, 1}
if<?	C = -1	C \in {0, 1}
if>?	C = 1	C \in {-1, 0}
if<=?	C \in {-1, 0}	C = 1
if>=?	C \in {0, 1}	C = -1
if-not=?	C \in {-1, 1}	C = 0

NOTE The macros if<=? etc. are the preferred way of 2-way branching based on the result of a comparison.

Function: =?

Function: =? compare

Function: =? x y

Function: =? compare x y

Function: <?

Function: <? compare

Function: <? x y

Function: <? compare x y

Function: >?

Function: >? compare

Function: >? x y

Function: >? compare x y

Function: <=?

Function: <=? compare

Function: <=? x y

Function: <=? compare x y

Function: >=?

Function: >=? compare

Function: >=? x y

Function: >=? compare x y

Function: not=?

Function: not=? compare

Function: not=? x y

Function: not=? compare x y

If the values x and y are given, test if x and y are in the relation specified by the name of the procedure rel?, with respect to compare procedure compare; otherwise construct a predicate procedure.

In the forms:

(rel? x y)
(rel? compare x y)

the result is a boolean (either #t or #f) depending on (compare x y) and the test rel? as specified for if<? etc. If compare is not supplied, default-compare is used.

In the form:

(rel?)
(rel? compare)

the predicate procedure:

(lambda (x y) (rel? compare x y))

is constructed. Again, if compare is not supplied, default-compare is used.

A few examples for illustration:

(>? "laugh" "LOUD")                     ⇒ #t
(<? string-compare-ci "laugh" "LOUD")   ⇒ #t

(define char<=? (<=? char-compare))

(sort-by-less '(1 a "b") (<?))          ⇒ ("b" a 1)
(sort-by-less '(1 a "b") (>?))          ⇒ (1 a "b")

WARNING A common mistake is writing (<=? x y z) where (<=/<=? x y z) is meant; this will most likely manifest itself at the time the expression (x y z) is evaluated.

Function: </<?

Function: </<? compare

Function: </<? x y z

Function: </<? compare x y z

Function: </<=?

Function: </<=? compare

Function: </<=? x y y

Function: </<=? compare x y y

Function: <=/<?

Function: <=/<? compare

Function: <=/<? x y y

Function: <=/<? compare x y y

Function: <=/<=?

Function: <=/<=? compare

Function: <=/<=? x y y

Function: <=/<=? compare x y y

Function: >/>?

Function: >/>? compare

Function: >/>? x y y

Function: >/>? compare x y y

Function: >/>=?

Function: >/>=? compare

Function: >/>=? x y y

Function: >/>=? compare x y y

Function: >=/>?

Function: >=/>? compare

Function: >=/>? x y y

Function: >=/>? compare x y y

Function: >=/>=?

Function: >=/>=? compare

Function: >=/>=? x y y

Function: >=/>=? compare x y y

Test if x, y, and z form a chain with the two relations specified by the name of the procedure rel1/rel2?, with respect to the compare procedure compare.

If compare is not provided, default-compare is used. If x, y, z are not provided, a predicate procedure of three arguments is constructed. The order in which the values are compared is unspecified, but each value is compared at least once.

NOTE (<=/<? real-compare 0 x 1) tests if x is a real number in the half open interval [0, 1).

Function: chain=? compare x ...

Function: chain<? compare x ...

Function: chain>? compare x ...

Function: chain<=? compare x ...

Function: chain>=? compare x ...

Test if the values x ... (zero or more values) form a chain with respect to the relation specified by the name of the procedure, and with respect to the compare procedure compare. The result is a boolean (either #t or #f). The order in which the values are compared is unspecified, but each value is compared at least once (even if there is just one).

A sequence of values x1, …, xn forms a chain with respect to the relation rel? if:

(rel? compare xi xj)

for all 1 < i < j < n. In particular, this is the case for n \in {0, 1}.

Since the relations = , <, >, <=, and >= are transitive, it is sufficient to test:

(rel? compare xi xi+1)

for 1 < i < n.

NOTE The reason every xi participates in at least one comparison is type-checking: After testing if the values form a chain, these value may be assumed to be of the type comparable by compare—and this holds irrespectively of the number of values, or whether they form a chain.

Function: pairwise-not=? compare x ...

Test if the values x ... (zero or more values) are pairwise unequal with respect to the compare procedure compare. The result is a boolean (either #t or #f). The order in which the values are compared is unspecified, but each value is compared at least once (even if there is just one).

The values x1, …, xn are pairwise unequal if:

(not=? compare xi xj)

for all i \not\in j. In particular, this is the case for n \in {0, 1}.

Since compare defines a total ordering on the values, the property can be checked in time O(n \log n), and implementations are required to do this. (For example by first sorting and then comparing adjacent elements).

Function: (min-compare compare x1 x ...

Function: (max-compare compare x1 x ...

A minimum or maximum of the values x1, x, … (one or more values) with respect to the compare procedure compare.

The result is the first value that is minimal (maximal, respectively). The order in which the values are compared is unspecified, but each value is compared at least once (even if there is just one value).

Function: kth-largest compare k x0 x ...

The k-th largest element of values x0, x … (one or more values) with respect to the compare procedure compare.

More precisely:

(kth-largest compare k x0 ... xn-1)

returns the (modulo k n)–th element of the unique sequence obtained by stably sorting (x0 ... xn-1). (Recall that a sorting algorithm is stable if it does not permute items with equal key, i.e. equivalent w.r.t. compare).

The argument k is an exact integer, and n > 1. The order in which the values xi are compared is unspecified, but each value is compared at least once (even if there is just one value).

Note The 0-th largest element is the minimum, the (-1)-st largest element is the maximum. The median is the (n-1)/2-th largest element if n is odd, and the average of the (n/2-1)-st and n/2-th largest elements if n is even.

Function: compare-by< lt-pred

Function: compare-by< lt-pred x y

Function: compare-by> gt-pred

Function: compare-by> gt-pred x y

Function: compare-by<= le-pred

Function: compare-by<= le-pred x y

Function: compare-by>= ge-pred

Function: compare-by>= ge-pred x y

Function: compare-by=/< eq-pred lt-pred

Function: compare-by=/< eq-pred lt-pred x y

Function: compare-by=/> eq-pred gt-pred

Function: compare-by=/> eq-pred gt-pred x y

If optional arguments x and y are present then these are compared with respect to the total order defined by the predicate(s) given; the result is in {-1, 0, +1}. If x and y are not present then a procedure comparing its two arguments using the predicate(s) given is constructed and returned.

The predicate procedures mean the following: (lt-pred x y) tests if x < y, le-pred tests for <=, gt-pred for >, ge-pred for >=, and eq-pred tests if x and y are equivalent. The result returned by a predicate procedure is interpreted as a Scheme truth value (i.e. #f is false and non-#f is true).

The purpose of the procedures compare-bypredicate(s) is to define a compare procedure from an order predicate, and possibly an additional equivalence predicate. If an equivalence predicate eq-pred is given, it is called before the order predicate because the equivalence may be coarser than the total ordering, and it may also be cheaper.

NOTE char-compare could be defined in terms of char<=? as:

(define char-compare (compare-by<= char<=?))

Function: debug-compare compare

Construct a compare procedure equivalent to compare but with debugging code wrapped around the calls to compare. The debugging code signals an error if it detects a violation of the axioms of a compare function. For this it is assumed that compare has no side–effects.

More specifically, (debug-compare compare) evaluates to a compare procedure compare1 which checks reflexivity, antisymmetry, and transitivity of compare based on the arguments on which compare1 is called.

The procedure compare1 checks reflexivity on any value passed to compare, antisymmetry on any pair of values on which compare is called, and transitivity on triples where two of the arguments are from the current call to compare1 and the third is a pseudo–random selection from the two arguments of the previous call to compare1.

RATIONALE The test coverage is partial and determined pseudo–randomly, but the execution time of compare1 is only a constant factor larger than the execution time of compare.