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 10

author

cowan

comment

ipnr

127.10.177.1

name

ComparatorsCowan

readonly

text

== Abstract ==

This proposal is a rewrite of SRFI 67, Compare Procedures, extending it from procedures that represent a total order to procedure bundles that represent one or more of a total order, an equality predicate, and a hash function.  By packaging these procedures together, along with a type check predicate, they can be treated as a single item for use in the implementation of data structures.

== Rationale ==

The four procedures above have complex dependencies on one another, and it is inconvenient to have to pass them all to other procedures that might or might not make use of all of them.  For example, a set implementation naturally requires only an equality 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 equality procedure, the set implementation can make use of whatever procedures are available and useful to it.

== Specification ==

== Definitions ==

A ''comparator'' is an object of a disjoint type.  It is a 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 its argument has the correct type to be passed as an argument to the other three procedures, and `#f` otherwise.

* The ''equality'' 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 equal 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 equality 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 it can handle any argument that satisfies the type check procedure, and that it returns the same value on two objects if the equality 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?'''

It is also the programmer's responsibility to ensure that all four procedures 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 particular, they must not depend in any way on memory addresses in implementations where the garbage collector can move objects in memory.  However, because of the expense of ensuring otherwise, the equality and compare procedures of a comparator are not required to terminate on circular structures.



=== Predicate ===

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

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

=== Standard atomic comparators ===

The following comparators are analogous 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 equality 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 to any of these comparators.

=== Constructors ===

Most of the following comparators are close analogues of 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 equality compare hash''`)`

Returns a comparator which bundles the ''type-check, equality, compare'', and ''hash'' procedures provided.  As a convenience, `#f` is accepted in place of any procedure, as follows:

* If ''type-check'' is `#f`, a type-check procedure that accepts any arguments is provided.
* If ''equality'' is `#f`, an equality 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.

It is an error if both ''equality'' and ''compare'' are specified as `#f`.

`(make-inexact-comparator `''epsilon rounding nan-handling''`)`

Returns a comparator that compares inexact numbers as follows:  if after rounding to the nearest ''epsilon'' they are the same, they compare equal; otherwise they compare as specified by `<`.  The direction of rounding is specified by the ''rounding'' argument, which is one of the symbols `floor`, `ceiling`, `truncate`, or `round`.

The argument `nan-handling` specifies how to compare NaN arguments to non-NaN arguments.  If it is `min`, NaN values precede all other values; if it is `max`, they follow all other values, and if it is `error`, an error is signaled if a NaN value is compared with a non-NaN.  In any case, two !NaNs are always treated as equal by this comparator.

`(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 equal that is the result; otherwise, the second elements are compared, and so on until non-equal elements are found.  If all elements are equal, the objects are equal.

If the implementation does not support bytevectors, the result of invoking `make-bytevector-comparator` is a comparator whose type checking procedure always returns `#f`.

`(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-car-comparator `''comparator''`)`

Returns a comparator that compares pairs on their cars alone using ''comparator''.

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

Returns a comparator that compares pairs on their cdrs alone using ''comparator''.

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

Returns a comparator that compares pairs first on their cars using ''car-comparator''.  If the cars are equal, compares the cdrs using ''cdr-comparator''.

`(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 whose procedures make use of the ''comparators'' as follows:

The type check procedure passes its argument to the type check procedures of ''comparators'' in the sequence given.  If any of them returns `#t`, so does the type check procedure; otherwise, it returns `#f`.

The arguments of the equality, compare, and hash procedures 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 equality, 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 equality 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 equality procedure returns `#t`, the compare procedure returns 0, and the hash procedure returns the XOR of what the hash procedures of all the relevant comparators return.  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.

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

Returns a comparator that behaves exactly like ''comparator'', except that it verifies all the programmer responsibilities (except stability) 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 (with the exception of circular structure) 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, except that NaN values must be accepted and treated as either preceding or following all numeric values.  The same should be true for any pair of objects of the same type if a standard 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 should compare either greater than or less than all values of every other 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 equality procedures of these comparators are `eq?`, `eqv?`, and `equal?` respectively.  When applied to non-equal objects, they compare objects the same way as `default-comparator` does.

=== Compare procedure constructors ===

`(make-compare< `''lt-pred''`)`

`(make-compare> `''gt-pred''`)`

`(make-compare<= `''le-pred''`)`

`(make-compare>= `''ge-pred''`)`

`(make-compare=/< `''eq-pred lt-pred''`)`

`(make-compare=/> `''eq-pred gt-pred''`)`

These procedures return a compare procedure given a less-than predicate, a greater-than predicate, a less-than-or-equal-to predicate, a greater-than-or-equal-to predicate, or the combination of an equality predicate and either a less-than or a greater-than predicate.  The first four invoke the predicate twice; the last two invoke the equality predicate before the ordering predicate.

They are based on the SRFI 67 `compare-by` procedures, but don't accept comparand arguments.

=== 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-equal? `''comparator obj,,1,, obj,,2,,''`)`

Invokes the equality 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 equality 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 allow testing of whether ''obj,,2,,'' is in a closed, open, or half-open interval defined by ''obj,,1,,'' and ''obj,,3,,''.  They 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.  '''Issues: Should these be renamed to express the interval types explicitly?  Should the `>` versions, which express the interval endpoints in reverse, be dropped?'''

`(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.

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,,1,, object,,2,,'' ...`)`

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-05 23:50:32