This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home.

Source for wiki ComparatorsCowan version 3

author

cowan

comment

ipnr

127.10.177.1

name

ComparatorsCowan

readonly

text

== Abstract ==

A ''comparator'' is an object of a disjoint type.  It is bundle of procedures that are useful for comparing two objects either for equality or for ordering.  There are four procedures in the bundle:

* The ''type check'' procedure returns `#t` if the two objects have the correct types to be passed to the other procedures, and `#f` otherwise.  Note that there is no requirement that both objects have the same type: it is possible, for example, to have a comparator that will compare a number to a string.

* The ''equivalence'' procedure returns `#t` if the two objects are the same in the sense of the particular 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 check procedure.

* The ''compare'' procedure returns -1, 0, or 1 if the first object precedes the second, is equivalent to the second, or follows the second, respectively, in a total order defined by this comparator.  It is the programmer's responsibility to ensure that it is reflexive, weakly antisymmetric, transitive, can handle any arguments that satisfy the type check procedure, and returns 0 iff the equivalence procedure returns `#t`.  Compare procedures are compatible with the compare procedures of [http://srfi.schemers.org/srfi-67/srfi-67.html SRFI 67]; see SRFI 67 for the rationale for adopting this return convention.

* The ''hash'' procedure takes one argument, and returns an exact non-negative integer which corresponds to it in the sense of a hash function.  It is the programmer's responsibility to ensure that the hash procedure returns the same value on two objects if the equivalence procedure says they are the same (but not necessarily the converse).  '''Issue:  Should this procedure accept a second argument such that its result must be less than this argument?'''

All four procedures must provide the same result whenever they are applied to the same object(s) unless the object(s) have been mutated since the last invocation.  In other words, they must not depend in any way on memory addresses in systems where the garbage collector can move objects in memory.

== Rationale ==

The four procedures above have complex dependencies on one another, and it is inconvenient to have to pass them all to various higher-level procedures that might or might not make use of all of them.  For example, a set implementation naturally requires only an equivalence procedure, but if it is implemented using a hash table, an appropriate hash procedure is also required if the implementation does not provide one; alternatively, if it is implemented using a tree, a compare procedure is required.  By passing a comparator rather than a bare equivalence procedure, the set implementation can make use of whatever procedures are useful to it.

== Specification ==

=== Predicate ===

`(comparator? `''obj''`)`

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

=== Standard atomic comparators ===

The following comparators are analogues to the standard compare procedures of SRFI 67.  They all provide appropriate hash functions as well.

`boolean-comparator`

Compares booleans using the total order `#f < #t`.

`char-comparator`

Compares characters using the total order implied by `char<?`.

`char-ci-comparator`

Compares characters using the total order implied by `char-ci<?`.

`string-comparator`

Compares strings using the total order implied by `string<?`.  Note that this order is implementation-dependent.

`string-ci-comparator`

Compares strings using the total order implied by `string-ci<?`.  Note that this order is implementation-dependent.

`symbol-comparator`

Compares symbols using the total order implied by applying `symbol->string` to the symbols and comparing them using the total order implied by `string<?`.  It is not a requirement that the hash procedure of `symbol-comparator` be consistent with the hash procedure of `string-comparator`, however.

`exact-integer-comparator`

`integer-comparator`

`rational-comparator`

`real-comparator`

`complex-comparator`

`number-comparator`

These comparators compare exact integers, integers, rational numbers, real numbers, complex numbers, and any numbers using the total order implied by `<`.  They must be compatible with the R5RS numerical tower in the following sense: If S is a subtype of the numerical type T and the two objects are members of both S and T, then the equivalence and compare procedures (but not necessarily the hash procedure) of S-comparator and T-comparator compute the same results on those objects.

Since non-real numbers cannot be compared with `<`, the following least-surprising ordering is defined: If the real parts are < or >, so are the complex numbers; otherwise, the complex numbers are ordered by their imaginary parts.

It is an error to pass a NaN value to any of these comparators.

=== Constructors ===

Most of the following comparators are analogues to the standard compare procedures of SRFI 67.  They all provide appropriate hash functions as well.

Note that comparator constructors are allowed to cache their results: they need not return a newly allocated object, since comparators are purely functional.

`(make-comparator `''type-check equivalence compare hash''`)`

Returns a comparator which bundles the ''type-check, equivalence, compare'', and ''hash'' procedures provided.  If ''type-check'' is `#f`, a type-check procedure that accepts any arguments is provided.  If ''equivalence'' is `#f` but ''compare'' is not, an equivalence procedure is provided that returns `#t` iff ''compare'' returns 0.  If ''compare'' or ''hash'' is `#f`, a procedure is provided that signals an error on application.

`(make-vector-comparator `''element-comparator''`)`

`(make-bytevector-comparator `''element-comparator''`)`

Returns a comparator which compares two vectors (or bytevectors) as follows: shorter objects precede longer ones, and objects of the same size are compared lexicographically: that is, the first elements are compared using ''element-comparator'', and if they are not equivalent that is the result; otherwise, the second elements are compared, and so on until non-equivalent elements are found.  If all elements are equivalent, the objects are equivalent.

`(make-list-comparator `''element-comparator''`)`

Returns a comparator which compares two lists as follows: the empty list precedes all other lists, and other lists are compared lexicographically.

`(make-vectorwise-comparator `''type-check element-comparator length ref''`)`

Returns a comparator which compares two objects that satisfy ''type-check'' as if they were vectors, using the ''length'' procedure to determine the length of the object, and the ''ref'' procedure to access a particular element.  The `make-vector-comparator` procedure may be defined thus:

{{{
(define (make-vector-comparator element-comparator)
  (make-vectorwise-comparator
    (lambda (x y) (and (vector? x) (vector? y)))
    element-comparator
    vector-length
    vector-ref))
}}}

`(make-listwise-comparator `''type-check element-comparator empty? head tail''`)`

Returns a comparator which compares two objects that satisfy ''type-check'' as if they were lists, using the ''empty?'' procedure to determine if an object is empty, and the ''head'' and ''tail'' procedures to access particular elements.  The `make-list-comparator` procedure may be defined thus:

{{{
(define (make-list-comparator element-comparator)
  (make-listwise-comparator
    (lambda (x y) (and (list? x) (list? y)))
    element-comparator
    null?
    car
    cdr))
}}}

`(make-pair-comparator-car `''comparator''`)`

`(make-pair-comparator-cdr `''comparator''`)`

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

Return comparators that compare pairs on their cars alone, their cdrs alone, or first the cars and then, if the cars are equivalent, the cdrs.

`(make-improper-list-comparator `''comparator''`)`

Returns a comparator that compares arbitrary objects as follows:  the empty list precedes all pairs, which precede all other objects.  Pairs are compared using ''comparator'' on their cars, and if they compare equal, on their cdrs.  Other objects are compared using ''comparator''.

`(make-selecting-comparator `''comparator,,1,, comparator,,2,,'' ...`)`

Returns a comparator that makes use of the ''comparators'' as follows:  Its arguments are passed to the type check procedure of each ''comparator'' in sequence.  The first comparator whose type check procedure is satisfied is used to select the comparator whose equivalence, compare, and hash procedures are to be used when comparing those arguments.  All other comparators are ignored.  If no type check procedure is satisfied, an error is signaled; to avoid this, make sure that the type check procedure of the final comparator is satisfied by any arguments.

This procedure is analogous to the expression types `select-compare` and `cond-compare` from SRFI 67.

`(make-refining-comparator `''comparator,,1,, comparator,,2,,'' ...`)`

Returns a comparator that makes use of the ''comparators'' in the same way as `make-selecting-comparator`, except that if the compare procedure returns 0 (or, if there is no compare procedure, if the equivalence procedure returns `#t`), then the next comparator whose type check procedure is satisfied is used instead.  If there are no more such comparators, then the equivalence procedure returns `#t`, the compare procedure returns 0, and the hash procedure returns whatever the hash procedure of the last comparator examined returns.  If no type check procedure is satisfied, an error is signaled; to avoid this, make sure that the type check procedure of the final comparator is satisfied by any arguments.  '''Issue:  Is this the right treatment of hash procedures?'''

`(make-debug-comparator `''comparator''`)`

Returns a comparator that behaves exactly like ''comparator'', except that it verifies all the programmer responsibilities whenever its procedures are invoked, and an error is signaled if any of them are violated.  Transitivity is not tested on the first call to a debug comparator, because it requires three arguments; it is tested on all future calls using an arbitrarily chosen argument from the previous invocation.  Note that this may cause unexpected storage leaks. 

=== The default comparator ===

`default-comparator`

This is a comparator that accepts any two Scheme values and orders them in some implementation-defined way, subject to the following constraints:

* When applied to booleans, characters, strings, and numbers, its behavior must be the same as `boolean-comparator`, `character-comparator`, `string-comparator`, and `number-comparator` respectively.  The same should be true for any pair of objects of the same type if a comparator is defined for that type.

* When applied to lists, vectors, and bytevectors, its behavior must be the same as `(make-list-comparator default-comparator)`, `(make-vector-comparator default-comparator)`, and `(make-bytevector-comparator default-comparator)` respectively.  The same should be true for any pair of sequences of the same type if an element-wise comparator is defined for that type.

* All objects of a disjoint type must compare either greater than or less than all values of another disjoint type.  In other words, type trumps structure.

=== Standard convenience comparators ===

`list-comparator`

`vector-comparator`

`bytevector-comparator`

These comparators compare lists, vectors, and bytevectors in the same way that the results of applying `make-list-comparator`, `make-vector-comparator`, and `make-bytevector-comparator` do when applied to `default-comparator`.

`eq-comparator`

`eqv-comparator`

`equal-comparator`

The equivalence procedures of these comparators are `eq?`, `eqv?`, and `equal?` respectively.  When applied to non-equivalent objects, they compare objects the same way as `default-comparator` does.

=== Primitive applicators ===

`(comparator-type-check `''comparator obj,,1,, obj,,2,,''`)`

Invokes the type check procedure of ''comparator'' on ''obj,,1,,'' and ''obj,,2,,'' and returns what it returns.

`(comparator-equivalent? `''comparator obj,,1,, obj,,2,,''`)`

Invokes the equivalence procedure of ''comparator'' on ''obj,,1,,'' and ''obj,,2,,'' and returns what it returns.

`(comparator-compare `''comparator obj,,1,, obj,,2,,''`)`

Invokes the compare procedure of ''comparator'' on ''obj,,1,,'' and ''obj,,2,,'' and returns what it returns.

`(comparator-hash `''comparator obj''`)`

Invokes the hash procedure of ''comparator'' on ''obj'' and returns what it returns.

=== Comparison syntax ===

The following expression types allow the convenient use of comparators.  They come directly from SRFI 67.

`(if3 `''<expr> <less> <equal> <greater>''`)`

The expression ''<expr>'' is evaluated; it will typically, but not necessarily, be a call on `comparator-compare`.  If the result is -1, ''<less>'' is evaluated and its value(s) are returned; if the result is 0, ''<equal>'' is evaluated and its value(s) are returned; if the result is 1, ''<greater>'' is evaluated and its value(s) are returned.  Otherwise an error is signaled.

`(if=? `''<expr> <consequent>'' [ ''<alternate>'' ]`)`

`(if<? `''<expr> <consequent>'' [ ''<alternate>'' ]`)`

`(if>? `''<expr> <consequent>'' [ ''<alternate>'' ]`)`

`(if<=? `''<expr> <consequent>'' [ ''<alternate>'' ]`)`

`(if>=? `''<expr> <consequent>'' [ ''<alternate>'' ]`)`

`(if-not=? `''<expr> <consequent>'' [ ''<alternate>'' ]`)`

The expression ''<expr>'' is evaluated; it will typically, but not necessarily, be a call on `comparator-compare`.  If the result is consistent with one of the six relations, ''<consequent>'' is evaluated and its value(s) are returned.  Otherwise, if ''<alternate>'' is present, it is evaluated and its value(s) are returned; if it is absent, an unspecified value is returned.

=== Comparison procedures ===

The following procedures allow the convenient use of comparators in situations where the expression types are not usable.  They are analogous to their SRFI 67 equivalents.  However, in SRFI 67, the analogous procedures return curried compare procedures if the comparand arguments are omitted.  Because there is no notion of a curried comparator in this proposal, these arguments are required.

`(=? ` [ ''comparator '' ] ''obj,,1,, obj,,2,,''`)`

`(<? ` [ ''comparator '' ] ''obj,,1,, obj,,2,,''`)`

`(>? ` [ ''comparator '' ] ''obj,,1,, obj,,2,,''`)`

`(<=? ` [ ''comparator '' ] ''obj,,1,, obj,,2,,''`)`

`(>=? ` [ ''comparator '' ] ''obj,,1,, obj,,2,,''`)`

`(not=? ` [ ''comparator '' ] ''obj,,1,, obj,,2,,''`)`

These procedures return `#t` if, when ''obj,,1,,'' and ''obj,,2,,'' are compared using the equivalence or compare procedures of ''comparator'', the objects bear the specified relation to one another, and `#f` otherwise.  If ''comparator'' is omitted, ''default-comparator'' is used.  If the objects do not satisfy the type check procedure, an error is signaled.

`(</<? `[ ''comparator'' ] ''obj,,1,, obj,,2,, obj,,3,,''`)` 

`(</<=? `[ ''comparator'' ] ''obj,,1,, obj,,2,, obj,,3,,''`)`

`(<=/<? `[ ''comparator'' ] ''obj,,1,, obj,,2,, obj,,3,,''`)` 

`(<=/<=? `[ ''comparator''  ] ''obj,,1,, obj,,2,, obj,,3,,''`)` 

`(>/>? `[ ''comparator'' ] ''obj,,1,, obj,,2,, obj,,3,,''`)` 

`(>/>=? `[ ''comparator''  ] ''obj,,1,, obj,,2,, obj,,3,,''`)` 

`(>=/>? `[ ''comparator''  ] ''obj,,1,, obj,,2,, obj,,3,,''`)` 

`(>=/>=? `[ ''comparator''  ] ''obj,,1,, obj,,2,, obj,,3,,'') 

These procedures apply the compare procedure of ''comparator'' to the three objects, and return `#t` if the result of comparing ''obj,,1,,'' and ''obj,,2,,'' is consistent with the relation specified before the slash, and the result of comparing ''obj,,2,,'' and ''obj,,3,,'' is consistent with the relation specified after the slash.  Otherwise, `#f` is returned.  If ''comparator'' is omitted, ''default-comparator'' is used.  The order in which the comparisons are done is unspecified, but both of them are always performed to ensure type checking.

`(chain=? `''comparator object'' ...`)`

`(chain<? `''comparator object'' ...`)`

`(chain>? `''comparator object'' ...`)`

`(chain<=? `''comparator object'' ...`)`

`(chain>=? `''comparator object'' ...`)`

These procedures are analogous to the number, character, and string comparison procedures of Scheme.  They apply the compare procedure of ''comparator'' to the ''objects'' as follows.  If the specified relation returns `#t` for all ''object,,i,,'' and ''object,,j,,'' where ''n'' is the number of objects and `(<= 1 `''object,,i,,'' ''object,,j,, n''`)` returns true, then the procedures return `#t`, but otherwise `#f`.  In particular this applies where ''n'' is 0 or 1.  Note that the comparator must be provided, in order to handle the case of comparing comparators with `default-comparator`.

The order in which the values are compared is unspecified, but each value is compared at least once, even if there is just one, to ensure type checking.  The reason that two different relations are provided is to handle half-open intervals easily and correctly.

Because the relations are transitive, it suffices to compare each object with its successor.

`(comparator-min `''comparator object,,1,, object,,2,,'' ...`)`

`(comparator-max `''comparator object'' ...`)`

These procedures are analogous to `min` and `max` respectively.  They apply the compare procedure of ''comparator'' to the ''objects'' to determine the first object that is minimal (or maximal).  The order in which the values are compared is unspecified, but each value is compared at least once, even if there is just one, to ensure type checking.

Note:  The SRFI 67 procedures `pairwise-not=?` and `kth-largest` involve sorting their arguments, and are not provided by this proposal in order to avoid an unnecessary implementation dependency.  They are easily provided by a sorting package that makes use of comparators.

time

2013-06-03 09:24:22