# (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 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: ```scheme (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: ```scheme (make-comparator boolean? boolean=? (lambda (x y) (and (not x) y)) boolean-hash)) ``` **real-comparator** `real-comparator` is defined as follows: ```scheme (make-comparator real? = < number-hash)) ``` **char-comparator** `char-comparator` is defined as follows: ```scheme (make-comparator char? char=? char `char-ci-comparator` is defined as follows: ```scheme (make-comparator char? char-ci=? char-ci `string-comparator` is defined as follows: ```scheme (make-comparator string? string=? string `string-ci-comparator` is defined as follows: ```scheme (make-comparator string? string-ci=? string-ci 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 ...*****)** \ \&#xNAN;**(\? *****cmp object1 object2 object3 ...*****)**\ \&#xNAN;**(<=? *****cmp object1 object2 object3 ...*****)**\ \&#xNAN;**(>=? *****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 ...*****)** \ \&#xNAN;**(comparator-min *****cmp obj1 obj2 ...*****)**\ \&#xNAN;**(comparator-max-in-list *****cmp list*****)**\ \&#xNAN;**(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*****)** \ \&#xNAN;**(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](https://srfi.schemers.org/srfi-128/srfi-128.html) and the [SRFI 162](https://srfi.schemers.org/srfi-162/srfi-162.html) specifications by John Cowan.