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:

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) [procedure]

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

(comparator-ordered? cmp) [procedure]

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

(comparator-hashable? cmp) [procedure]

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

Constructors

(make-comparator test equality ordering hash) [procedure]

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-pair-comparator car-comparator cdr-comparator) [procedure]

This procedure returns comparators whose functions behave as follows:

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

This procedure returns comparators whose functions behave as follows:

(make-vector-comparator element-comparator type-test length ref) [procedure]

This procedure returns comparators whose functions behave as follows:

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 [object]
eqv-comparator
equal-comparator

These objects implement comparators whose functions behave as follows:

boolean-comparator [object]

boolean-comparator is defined as follows:

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

real-comparator [object]

real-comparator is defined as follows:

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

char-comparator [object]

char-comparator is defined as follows:

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

char-ci-comparator [object]

char-ci-comparator is defined as follows:

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

string-comparator [object]

string-comparator is defined as follows:

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

string-ci-comparator [object]

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) [procedure]

Returns the type test predicate of comparator cmp.

(comparator-equality-predicate cmp) [procedure]

Returns the equality predicate of comparator cmp.

(comparator-ordering-predicate cmp) [procedure]

Returns the ordering predicate of comparator cmp.

(comparator-hash-function cmp) [procedure]

Returns the hash function of comparator cmp.

(comparator-test-type cmp obj) [procedure]

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) [procedure]

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) [procedure]

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 …) [procedure]
(<? 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 …) [procedure]
(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) [syntax]
(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) [syntax]

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.