This SRFI is currently in ``draft'' status.
To see an explanation of
each status that a SRFI can hold, see here.
To provide input on this SRFI, please
mail to
<srfi minus 114 at srfi dot schemers dot org>. See
instructions here to
subscribe to the list. You can access previous messages via
the archive of the mailing list.
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 test predicate, they can be treated as a single item for use in the implementation of data structures.
Should the hash procedure accept an optional second argument, such that its result must be less than this argument?
(resolved)
(resolved)
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.
This SRFI could not have been written without the work of Sebastian Egner and Jens Axel Søgaard on SRFI 67; much of the credit for this SRFI is due to them, but none of the blame.
The procedures in this SRFI are in the (scheme comparators) and (srfi xxx) libraries (or (srfi :xxx) on R6RS). However, the sample implementation currently places them in the (comparators) library instead.
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:
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. It is recommended but not required that the equality and compare procedures of a comparator terminate on circular structures.
Predicates: comparator?
Standard atomic comparators: boolean-comparator, char-comparator, char-ci-comparator, string-comparator, string-ci-comparator, symbol-comparator, exact-integer-comparator, integer-comparator, rational-comparator, real-comparator, complex-comparator, number-comparator
Comparator constructors: make-comparator, make-inexact-comparator, make-vector-comparator, make-bytevector-comparator, make-list-comparator, make-vectorwise-comparator, make-listwise-comparator, make-car-comparator, make-cdr-comparator, make-pair-comparator, make-improper-list-comparator, make-selecting-comparator, make-refining-comparator, make-debug-comparator
The default comparator: default-comparator
Standard convenience comparators: list-comparator, vector-comparator, bytevector-comparator, eq-comparator, eqv-comparator, equal-comparator
Accessors: comparator-type-test-procedure, comparator-equality-predicate, comparator-compare-procedure, comparator-hash-function
Primitive applicators: comparator-test-type, comparator-check-type, comparator-equal?, comparator-compare, comparator-hash
Compare procedure constructors: make-compare<?, make-compare>?, make-compare<=?, make-compare>=?, make-compare=/< make-compare=/>
Comparison syntax: if3, if=?, if<?, if>?, if<=?, if>=?, if-not=?
Binary comparison predicates: =?, <? , >?, <=, >=?, not=?
Interval (ternary) comparison predicates: in-open-interval?, in-closed-interval?, in-open-closed-interval?, in-closed-open-interval?
Chain (multiple argument) comparison predicates: chain=?, chain<?, chain>?, chain<=?, chain>=?
Min/max comparison predicates: comparator-min, comparator-max
(comparator? obj)
Returns #t if obj is a comparator, and #f otherwise.
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. This can still produce surprising results if one real part is exact and the other is inexact.
It is an error to pass a NaN to any of these comparators.
Most of the following comparator constructors 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-test equality compare hash)
Returns a comparator which bundles the type-test, equality, compare, and hash procedures provided. As a convenience, #f is accepted in place of any procedure, as follows:
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 testing 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-test element-comparator length ref)
Returns a comparator which compares two objects that satisfy type-test 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-test element-comparator empty? head tail)
Returns a comparator which compares two objects that satisfy type-test 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 comparator1 comparator2 ...)
Returns a comparator whose procedures make use of the comparators as follows:
The type test procedure passes its argument to the type test procedures of comparators in the sequence given. If any of them returns #t, so does the type test procedure; otherwise, it returns #f.
The arguments of the equality, compare, and hash procedures are passed to the type test procedure of each comparator in sequence. The first comparator whose type test procedure is satisfied is used when comparing those arguments. All other comparators are ignored. If no type test procedure is satisfied, an error is signaled; to avoid this, make sure that the type test procedure of the final comparator accepts any argument.
This procedure is analogous to the expression types select-compare and cond-compare from SRFI 67.
(make-refining-comparator comparator1 comparator2 ...)
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 test 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 a value which depends, in an implementation-defined way, on what the hash procedures of all the relevant comparators return. If no type test procedure is satisfied, an error is signaled; to avoid this, make sure that the type test procedure of the final comparator is satisfied by any arguments.
This procedure is analogous to the expression type refine-compare from SRFI 67.
(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.
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:
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.
When applied to any other pair of objects, the implementation should FIXME FIXME
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.
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.
(comparator-type-test-procedure comparator)
Returns the type test procedure of comparator.
(comparator-equality-predicate comparator)
Returns the equality procedure of comparator.
(comparator-compare-procedure comparator)
Returns the compare procedure of comparator.
(comparator-hash-function comparator)
Returns the hash procedure of comparator.
(comparator-test-type comparator obj)
Invokes the type test procedure of comparator on obj and returns what it returns.
(comparator-check-type comparator obj)
Invokes the type test procedure of comparator on obj and returns true if it returns true and signals an error otherwise.
(comparator-equal? comparator obj1 obj2)
Invokes the equality procedure of comparator on obj1 and obj2 and returns what it returns.
(comparator-compare comparator obj1 obj2)
Invokes the compare procedure of comparator on obj1 and obj2 and returns what it returns.
(comparator-hash comparator obj)
Invokes the hash procedure of comparator on obj and returns what it returns.
(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.
They are based on the SRFI 67 compare-by procedures, but don't accept comparand arguments.
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.
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 ] [ obj1 obj2 ] )
(<? [ comparator ] [ obj1 obj2 ] )
(>? [ comparator ] [ obj1 obj2 ] )
(<=? [ comparator ] [ obj1 obj2 ] )
(>=? [ comparator ] [ obj1 obj2 ] )
(not=? [ comparator ] [ obj1 obj2 ] )
If obj1 and obj2 are provided, then these procedures return #t if comparing obj1 and obj2 using the equality or compare procedures of comparator shows that the objects bear the specified relation to one another, and #f otherwise. If obj1 and obj2 are not provided, then a predicate is returned which, when applied to two arguments, will produce results consistent with the three-argument version.
If comparator is omitted, default-comparator is used.
These procedures return true or false depending on whether an object is in an open, closed, or half-open interval. All comparisons are done in the sense of comparator, which is default-comparator if omitted.
(in-open-interval? [ comparator ] obj1 obj2 obj3)
Return #t if obj1 is less than obj2, which is less thanobj3, and #f otherwise.
(in-closed-interval? [ comparator ] obj1 obj2 obj3)
Returns #t if obj1 is less than or equal to obj2, which is less than or equal to obj3, and #f otherwise.
(in-open-closed-interval? [ comparator ] obj1 obj2 obj3)
Returns #t if obj1 is less than obj2, which is less than or equal to obj3, and #f otherwise.
(in-closed-open-interval? [ comparator ] obj1 obj2 obj3)
Returns #t if obj1 is less than or equal to obj2, which is less than obj3, and #f otherwise.
(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 objecti and objectj where n is the number of objects and 1 <= i < j <= n, 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 object1 object2 ...)
(comparator-max comparator object1 object2 ...)
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 testing.
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.
The implementation is not yet available. It will contain the files comparators-impl.scm, containing the syntax and procedure definitions; comparators.sld, an R7RS library exporting them; comparators.scm, a Chicken library; and comparators-test.scm, a test program using the Chicken test egg, available on Chibi as the (chibi test) library.
Copyright (C) John Cowan 2013. All Rights Reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.