SRFI 128  Comparators
The (srfi 128)
provides comparators, which bundle a type test predicate, an equality predicate, an ordering predicate, and a hash function into a single Scheme object. By packaging these procedures together, they can be treated as a single item for use in the implementation of data structures.
See the SRFI document for more information.
Predicates
Constructors
The following comparator constructors all supply appropriate type test predicates, equality predicates, ordering predicates, and hash functions based on the supplied arguments. They are allowed to cache their results: they need not return a newly allocated object, since comparators are pure and functional. In addition, the procedures in a comparator are likewise pure and functional.
makecomparator
makepaircomparator
makelistcomparator
makevectorcomparator
makeeqcomparator
makeeqvcomparator
makeequalcomparator
Standard Hash Functions
These are hash functions for some standard Scheme types, suitable for passing to makecomparator. Users may write their own hash functions with the same signature. However, if programmers wish their hash functions to be backward compatible with the reference implementation of SRFI 69, they are advised to write their hash functions to accept a second argument and ignore it.
Default Comparators
Accessors and Invokers
comparatortypetestpredicate
comparatorequalitypredicate
comparatororderingpredicate
comparatorhashfunction
comparatortesttype
comparatorchecktype
comparatorhash
Bounds and Salt
The following macros allow the callers of hash functions to affect their behavior without interfering with the calling signature of a hash function, which accepts a single argument (the object to be hashed) and returns its hash value. They are provided as macros so that they may be implemented in different ways: as a global variable, a SRFI 39 or R7RS parameter, or an ordinary procedure, whatever is most efficient in a particular implementation.
Comparison Predicates
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 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.
Syntax
comparator?
(comparator? obj)
Returns #t
if obj
is a comparator, and #f
otherwise.
comparatorordered?
(comparatorordered? comparator)
Returns #t
if comparator
has a supplied ordering predicate, and #f
otherwise.
comparatorhashable?
(comparatorhashable? comparator)
Returns #t
if comparator
has a supplied hash function, and #f
otherwise.
makecomparator
(makecomparator typetest equality ordering hash)
Returns a comparator which bundles the typetest
, equality
, ordering
, and hash
procedures provided. However, if ordering
or hash
is #f
, a procedure is provided that signals an error on application. The predicates comparatorordered?
and/or comparatorhashable?
, respectively, will return #f
in these cases.
Here are calls on makecomparator
that will return useful comparators for standard Scheme types:

(makecomparator boolean? boolean=? (lambda (x y) (and (not x) y)) booleanhash)
will return a comparator for booleans, expressing the ordering#f < #t
and the standard hash function for booleans. 
(makecomparator real? = < (lambda (x) (exact (abs x))))
will return a comparator expressing the natural ordering of real numbers and a plausible (but not optimal) hash function. 
(makecomparator string? string=? string<? stringhash)
will return a comparator expressing the implementation’s ordering of strings and the standard hash function. 
(makecomparator string? stringci=? stringci<? stringcihash)
will return a comparator expressing the implementation’s caseinsensitive ordering of strings and the standard caseinsensitive hash function.
makepaircomparator
(makepaircomparator carcomparator cdrcomparator)
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 carcomparator, and the cdr satisfies the type test predicate of cdrcomparator. 
The equality function returns
#t
if the cars are equal according to carcomparator and the cdrs are equal according to cdrcomparator, and#f
otherwise. 
The ordering function first compares the cars of its pairs using the equality predicate of carcomparator. If they are not equal, then the ordering predicate of carcomparator is applied to the cars and its value is returned. Otherwise, the predicate compares the cdrs using the equality predicate of cdrcomparator. If they are not equal, then the ordering predicate of cdrcomparator 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 carcomparator and cdrcomparator respectively and then hashes them together in an implementationdefined way.
makelistcomparator
(makelistcomparator elementcomparator typetest empty? head tail)
This procedure returns comparators whose functions behave as follows:

The type test returns
#t
if its argument satisfies typetest and the elements satisfy the type test predicate of elementcomparator. 
The total order defined by the equality and ordering functions is as follows (known as lexicographic order):
 The empty sequence, as determined by calling
empty?
, comparesequal
to itself.  The empty sequence compares less than any nonempty sequence.
 Two nonempty sequences are compared by calling the head procedure on each. If the heads are not equal when compared using elementcomparator, the result is the result of that comparison. Otherwise, the results of calling the tail procedure are compared recursively.
 The empty sequence, as determined by calling

The hash function computes the hash values of the elements using the hash function of elementcomparator and then hashes them together in an implementationdefined way.
makevectorcomparator
(makevectorcomparator elementcomparator typetest length ref)
This procedure returns comparators whose functions behave as follows:

The type test returns
#t
if its argument satisfies typetest and the elements satisfy the type test predicate of elementcomparator. 
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 elementcomparator. 
The ordering predicate returns
#t
if the results of applying length to the first vector is less than the result of applyinglength
to the second vector. If the lengths are equal, then the elements are examined pairwise using the ordering predicate of elementcomparator. 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 elementcomparator and then hashes them together in an implementationdefined way.
Here is an example, which returns a comparator for byte vectors:
(makevectorcomparator
(makecomparator exactinteger? = < numberhash)
bytevector?
bytevectorlength
bytevectoru8ref)
makeeqcomparator
(makeeqcomparator)
makeeqvcomparator
(makeeqvcomparator)
makeequalcomparator
(makeequalcomparator)
These procedures return comparators whose functions behave as follows:

The type test returns
#t
in all cases. 
The equality functions are
eq?
,eqv?
, andequal?
respectively. 
The ordering function is implementationdefined, except that it must conform to the rules for ordering functions. It may signal an error instead.

The hash function is defaulthash.
These comparators accept circular structure and NaN
s.
booleanhash
(booleanhash obj)
charhash
(charhash obj)
charcihash
(charcihash obj)
stringhash
(stringhash obj)
stringcihash
(stringcihash obj)
symbolhash
(symbolhash obj)
numberhash
(numberhash obj)
makedefaultcomparator
(makedefaultcomparator)
Returns a comparator known as a default comparator that accepts Scheme values and orders them in some implementationdefined way, subject to the following conditions:

Given disjoint types a and b, one of three conditions must hold:
 All objects of type a compare less than all objects of type b.
 All objects of type a compare greater than all objects of type b.
 All objects of both type a and type b compare equal to each other. This is not permitted for any of the Scheme types mentioned below.

The empty list must be ordered before all pairs.

When comparing booleans, it must use the total order
#f < #t
. 
When comparing characters, it must use
char=?
andchar<?
.Note: In R5RS, this is an implementationdependent order that is typically the same as Unicode codepoint order; in R6RS and R7RS, it is Unicode codepoint order.

When comparing pairs, it must behave the same as a comparator returned by makepaircomparator with default comparators as arguments.

When comparing symbols, it must use an implementationdependent total order. One possibility is to use the order obtained by applying
symbol>string
to the symbols and comparing them using the total order implied bystring<?
. 
When comparing bytevectors, it must behave the same as a comparator created by the expression
(makevectorcomparator (makecomparator bytevector? = < numberhash) bytevector? bytevectorlength bytevectoru8ref)
. 
When comparing numbers where either number is complex, since nonreal numbers cannot be compared with
<,
the following leastsurprising ordering is defined: If the real parts are<
or>,
so are the numbers; otherwise, the numbers are ordered by their imaginary parts. This can still produce somewhat surprising results if one real part is exact and the other is inexact. 
When comparing real numbers, it must use
=
and<.

When comparing strings, it must use
string=?
andstring<?
.Note: In R5RS, this is lexicographic order on the implementationdependent order defined by
char<?
; in R6RS it is lexicographic order on Unicode codepoint order; in R7RS it is an implementationdefined order. 
When comparing vectors, it must behave the same as a comparator returned by
(makevectorcomparator (makedefaultcomparator) vector? vectorlength vectorref)
. 
When comparing members of types registered with
comparatorregisterdefault!
, it must behave in the same way as the comparator registered using that function.
Default comparators use defaulthash as their hash function.
defaulthash
(defaulthash obj)
This is the hash function used by default comparators, which accepts a Scheme value and hashes it in some implementationdefined way, subject to the following conditions:

When applied to a pair, it must return the result of hashing together the values returned by
defaulthash
when applied to the car and the cdr. 
When applied to a boolean, character, string, symbol, or number, it must return the same result as
booleanhash
,charhash
,stringhash
,symbolhash
, ornumberhash
respectively. 
When applied to a list or vector, it must return the result of hashing together the values returned by defaulthash when applied to each of the elements.
comparatorregisterdefault!
(comparatorregisterdefault! comparator)
Registers comparator for use by default comparators, such that if the objects being compared both satisfy the type test predicate of comparator, it will be employed by default comparators to compare them. Returns an unspecified value. It is an error if any value satisfies both the type test predicate of comparator and any of the following type test predicates: boolean?
, char?
, null?
, pair?
, symbol?
, bytevector?
, number?
, string?
, vector?
, or the type test predicate of a comparator that has already been registered.
This procedure is intended only to extend default comparators into territory that would otherwise be undefined, not to override their existing behavior. In general, the ordering of calls to comparatorregisterdefault! should be irrelevant. However, implementations that support inheritance of record types may wish to ensure that default comparators always check subtypes before supertypes.
comparatortypetestpredicate
(comparatortypetestpredicate comparator)
comparatorequalitypredicate
(comparatorequalitypredicate comparator)
comparatororderingpredicate
(comparatororderingpredicate comparator)
comparatorhashfunction
(comparatorhashfunction comparator)
comparatortesttype
(comparatortesttype comparator obj)
Invokes the type test predicate of comparator on obj
and returns what it returns. More convenient than comparatortypetestpredicate
, but less efficient when the predicate is called repeatedly.
comparatorchecktype
(comparatorchecktype comparator obj)
Invokes the type test predicate of comparator on obj
and returns true if it returns true, but signals an error otherwise. More convenient than comparatortypetestpredicate
, but less efficient when the predicate is called repeatedly.
comparatorhash
(comparatorhash comparator obj)
Invokes the hash function of comparator on obj
and returns what it returns. More convenient than comparatorhashfunction
, but less efficient when the function is called repeatedly.
Note: No invokers are required for the equality and ordering predicates, because =?
and <?
serve this function.
hashbound
Syntax
(hashbound)
Hash functions should be written so as to return a number between 0
and the largest reasonable number of elements (such as hash buckets) a data structure in the implementation might have. What that value is depends on the implementation. This value provides the current bound as a positive exact integer, typically for use by userwritten hash functions. However, they are not required to bound their results in this way.
hashsalt
Syntax
(hashsalt)
A salt is random data in the form of a nonnegative exact integer used as an additional input to a hash function in order to defend against dictionary attacks, or (when used in hash tables) against denialofservice attacks that overcrowd certain hash buckets, increasing the amortized O(1)
lookup time to O(n)
. Salt can also be used to specify which of a family of hash functions should be used for purposes such as cuckoo hashing. This macro provides the current value of the salt, typically for use by userwritten hash functions. However, they are not required to make use of the current salt.
The initial value is implementationdependent, but must be less than the value of (hashbound)
, and should be distinct for distinct runs of a program unless otherwise specified by the implementation. Implementations may provide a means to specify the salt value to be used by a particular invocation of a hash function.
=?
(=? comparator object1 object2 object3 ...)
<?
(<? comparator object1 object2 object3 ...)
>?
(>? comparator object1 object2 object3 ...)
<=?
(<=? comparator object1 object2 object3 ...)
>=?
(>=? comparator object1 object2 object3 ...)
comparatorif<=>
Syntax
(comparatorif<=> [ <comparator> ] <object1> <object2> <lessthan> <equalto> <greaterthan>)
It is an error unless <comparator>
evaluates to a comparator and <object1>
and <object2>
evaluate to objects that the comparator can handle. If the ordering predicate returns true when applied to the values of <object1>
and <object2>
in that order, then <lessthan>
is evaluated and its value returned. If the equality predicate returns true when applied in the same way, then <equalto>
is evaluated and its value returned. If neither returns true, <greaterthan>
is evaluated and its value returned.
If <comparator>
is omitted, a default comparator is used.