(lispkit comparator)

Comparators bundle a type test predicate, an equality predicate, an optional ordering predicate, and an optional hash function into a single object. By packaging these procedures together, they can be treated as a single item for use in the implementation of data structures that typically rely on a consistent combination of such functions.

Library (lispkit comparator) implements a large part of the API of SRFI 128 and thus, can be used as a drop-in replacement for the core functionality of library (srfi 128). A few procedures and objects from SRFI 162 were adopted as well.

Comparator objects

Comparators are objects of a distinct type which bundle procedures together that are useful for comparing two objects in a total order. It is an error, if any of the procedures have side effects. There are four procedures in the bundle:

• The type test predicate returns #t if its argument has the correct type to be passed as an argument to the other three procedures, and #f otherwise.

• The equality predicate returns #t if the two objects are the same in the sense of the comparator, and #f otherwise. It is the programmer's responsibility to ensure that it is reflexive, symmetric, transitive, and can handle any arguments that satisfy the type test predicate.

• The ordering predicate returns #t if the first object precedes the second in a total order, and #f otherwise. Note that if it is true, the equality predicate must be false. It is the programmer's responsibility to ensure that it is irreflexive, antisymmetric, transitive, and can handle any arguments that satisfy the type test predicate.

• The hash function takes an object and returns an exact non-negative integer. It is the programmer's responsibility to ensure that it can handle any argument that satisfies the type test predicate, and that it returns the same value on two objects if the equality predicate says they are the same (but not necessarily the converse).

It is also the programmer's responsibility to ensure that all four procedures provide the same result whenever they are applied to the same objects in the sense of eqv?, unless the objects have been mutated since the last invocation.

Comparator objects are not applicable to circular structure, or to objects containing any of these. Attempts to pass any such objects to any procedure defined here, or to any procedure that is part of a comparator defined here, has undefined behavior.

Predicates

(comparator? obj)

Returns #t if obj is a comparator, and #f otherwise.

(comparator-ordered? cmp)

Returns #t if comparator cmp has a supplied ordering predicate, and #f otherwise.

(comparator-hashable? cmp)

Returns #t if comparator cmp has a supplied hash function, and #f otherwise.

Constructors

(make-comparator test equality ordering hash)

Returns a comparator which bundles the test, equality, ordering, and hash procedures provided as arguments to make-comparator. If ordering or hash is #f, a procedure is provided that signals an error on application. The predicates comparator-ordered? and comparator-hashable? will return #f in the respective cases.

Here are calls on make-comparator that will return useful comparators for standard Scheme types:

• (make-comparator boolean? boolean=? (lambda (x y) (and (not x) y)) boolean-hash) will return a comparator for booleans, expressing the ordering #f < #t and the standard hash function for booleans

• (make-comparator real? = < (lambda (x) (exact (abs x)))) will return a comparator expressing the natural ordering of real numbers and a plausible hash function

• (make-comparator string? string=? string<? string-hash) will return a comparator expressing the implementation's ordering of strings and the standard hash function

• (make-comparator string? string-ci=? string-ci<? string-ci-hash) will return a comparator expressing the implementation's case-insensitive ordering of strings and the standard case-insensitive hash function

(make-pair-comparator car-comparator cdr-comparator)

This procedure returns comparators whose functions behave as follows:

• The type test returns #t if its argument is a pair, if the car satisfies the type test predicate of car-comparator, and the cdr satisfies the type test predicate of cdr-comparator

• The equality function returns #t if the cars are equal according to car-comparator and the cdrs are equal according to cdr-comparator, and #f otherwise. The ordering function first compares the cars of its pairs using the equality predicate of car-comparator. If they are not equal, then the ordering predicate of car-comparator is applied to the cars and its value is returned. Otherwise, the predicate compares the cdrs using the equality predicate of cdr-comparator. If they are not equal, then the ordering predicate of cdr-comparator is applied to the cdrs and its value is returned

• The hash function computes the hash values of the car and the cdr using the hash functions of car-comparator and cdr-comparator respectively and then hashes them together in an implementation-defined way

(make-list-comparator element-comparator type-test empty? head tail)

This procedure returns comparators whose functions behave as follows:

• The type test returns #t if its argument satisfies type-test and the elements satisfy the type test predicate of element-comparator

• The total order defined by the equality and ordering functions is lexicographic. It is defined as follows:

  • The empty sequence, as determined by calling empty?, compares equal to itself

  • The empty sequence compares less than any non-empty sequence

  • Two non-empty sequences are compared by calling the head procedure on each. If the heads are not equal when compared using element-comparator, the result is the result of that comparison. Otherwise, the results of calling the tail procedure are compared recursively.

• The hash function computes the hash values of the elements using the hash function of element-comparator and then hashes them together in an implementation-defined way

(make-vector-comparator element-comparator type-test length ref)

This procedure returns comparators whose functions behave as follows:

• The type test returns #t if its argument satisfies type-test and the elements satisfy the type test predicate of element-comparator.

• The equality predicate returns #t if both of the following tests are satisfied in order: the lengths of the vectors are the same in the sense of =, and the elements of the vectors are the same in the sense of the equality predicate of element-comparator.

• The ordering predicate returns #t if the results of applying length to the first vector is less than the result of applying length to the second vector. If the lengths are equal, then the elements are examined pairwise using the ordering predicate of element-comparator. If any pair of elements returns #t, then that is the result of the list comparator's ordering predicate; otherwise the result is #f

• The hash function computes the hash values of the elements using the hash function of element-comparator and then hashes them together in an implementation-defined way

Here is an example, which returns a comparator for byte vectors:

(make-vector-comparator
  (make-comparator exact-integer? = < number-hash)
  bytevector?
  bytevector-length
  bytevector-u8-ref)

Default comparators

eq-comparator eqv-comparator equal-comparator

These objects implement comparators whose functions behave as follows:

• The type test returns #t in all cases

• The equality functions are eq?, eqv?, and equal? respectively

• The ordering function is implementation-defined, except that it must conform to the rules for ordering functions. It may signal an error instead.

• The hash functions are eq-hash, eqv-hash, and equal-hash respectively

boolean-comparator

boolean-comparator is defined as follows:

(make-comparator boolean? boolean=? (lambda (x y) (and (not x) y)) boolean-hash))

real-comparator

real-comparator is defined as follows:

(make-comparator real? = < number-hash))

char-comparator

char-comparator is defined as follows:

(make-comparator char? char=? char<? char-hash))

char-ci-comparator

char-ci-comparator is defined as follows:

(make-comparator char? char-ci=? char-ci<? char-ci-hash))

string-comparator

string-comparator is defined as follows:

(make-comparator string? string=? string<? string-hash))

string-ci-comparator

string-ci-comparator is defined as follows:

(make-comparator string? string-ci=? string-ci<? string-ci-hash))

Accessors and invokers

(comparator-type-test-predicate cmp)

Returns the type test predicate of comparator cmp.

(comparator-equality-predicate cmp)

Returns the equality predicate of comparator cmp.

(comparator-ordering-predicate cmp)

Returns the ordering predicate of comparator cmp.

(comparator-hash-function cmp)

Returns the hash function of comparator cmp.

(comparator-test-type cmp obj)

Invokes the type test predicate of comparator cmp on obj and returns what it returns. This procedure is convenient than comparator-type-test-predicate, but less efficient when the predicate is called repeatedly.

(comparator-check-type cmp obj)

Invokes the type test predicate of comparator cmp on obj and returns #t if it returns #t, but signals an error otherwise. This procedure is more convenient than comparator-type-test-predicate, but less efficient when the predicate is called repeatedly.

(comparator-hash cmp obj)

Invokes the hash function of comparator cmp on obj and returns what it returns. This procedure is more convenient than comparator-hash-function, but less efficient when the function is called repeatedly.

Comparison predicates

(=? cmp object1 object2 object3 ...) (<? cmp object1 object2 object3 ...) (>? cmp object1 object2 object3 ...) (<=? cmp object1 object2 object3 ...) (>=? cmp object1 object2 object3 ...)

These procedures are analogous to the number, character, and string comparison predicates of Scheme. They allow the convenient use of comparators to handle variable data types.

These procedures apply the equality and ordering predicates of comparator cmp to the objects as follows. If the specified relation returns #t for all objecti and objectj where n is the number of objects and 1 <= i < j <= n, then the procedures return #t, but otherwise #f. Because the relations are transitive, it suffices to compare each object with its successor. The order in which the values are compared is unspecified.

(comparator-max cmp obj1 obj2 ...) (comparator-min cmp obj1 obj2 ...) (comparator-max-in-list cmp list) (comparator-min-in-list cmp list)

These procedures are analogous to min and max respectively, but may be applied to any orderable objects, not just to real numbers. They apply the ordering procedure of comparator cmp to the objects obj1 ... to find and return a minimal or maximal object. The order in which the values are compared is unspecified. If two objects are equal in the sense of the comparator cmp, either may be returned.

The -in-list versions of the procedures accept a single list argument.

Syntax

(comparator-if<=> obj1 obj2 less-than equal-to greater-than) (comparator-if<=> cmp obj1 obj2 less-than equal-to greater-than)

It is an error unless comparator cmp evaluates to a comparator and obj1 and obj2 evaluate to objects that the comparator can handle. If the ordering predicate returns #t when applied to the values of obj1 and obj2 in that order, then expression less-than is evaluated and its value is returned. If the equality predicate returns #t when applied in the same way, then expression equal-to is evaluated and its value is returned. If neither returns #t, expression greater-than is evaluated and its value is returned.

If cmp is omitted, equal-comparator is used as a default.

(if<=> obj1 obj2 less-than equal-to greater-than)

This special form is equivalent to (comparator-if<=> obj1 obj2 less-than equal-to greater-than), i.e. it uses the predicates provided by equal-comparator to determine whether expression less-than, equal-to, or greater-than gets evaluated and its value returned.

---

This documentation was derived from the SRFI 128 and the SRFI 162 specifications by John Cowan.