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. For a version of this page that may be more recent, see ComparatorsCowan in WG2's repo for R7RS-large.

Comparators­Cowan

cowan
2015-10-23 10:45:39
17history
source

Please see SRFI 114 for the successor to this proposal.

SRFI 114 has been deprecated by its author. Here is the first draft of a simpler and better replacement, which will eventually become a new SRFI.

Abstract

This SRFI provides comparators, 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.

Issues

None at present.

Rationale

The four procedures above have complex dependencies on one another, and it is inconvenient to have to pass them individually to other procedures that might or might not make use of all of them. For example, a set implementation by nature requires only an equality predicate, but if it is implemented using a hash table, an appropriate hash function is also required if the implementation does not provide one; alternatively, if it is implemented using a tree, a comparison procedure is required. By passing a comparator rather than a bare equality predicate, the set implementation can make use of whatever procedures are available and useful to it.

This SRFI is a simplified and enhanced rewrite of SRFI 114, and shares some of its design rationale and all of its acknowledgements. Special thanks to Taylan Ulrich Bayırlı/Kammer, whose insistence that SRFI 114 was over-complicated but also inadequate inspired this redesign.

Specification

The procedures in this SRFI are in the (srfi ???) library (or (srfi :???) on R6RS), but the sample implementation currently places them in the (comparators) library. This means it can't be used alongside SRFI 114, but there's no reason for anyone to do that.

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:

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) (in the sense of eqv?), 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.

Limitations

The comparator objects defined in this SRFI are not applicable to circular structure or to NaNs or objects containing them. Attempts to pass any such objects to any procedure defined here, or to any procedure that is part of a comparator defined here, is an error except as otherwise noted.

Index

Predicates

(comparator? obj)

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

(comparator-comparison-procedure? comparator)

Returns #t if comparator has a supplied comparison procedure, and #f otherwise.

(comparator-hash-function? comparator)

Returns #t if comparator has a supplied hash function, and #f otherwise.

Standard comparator constructors

The following comparator constructors all supply appropriate type test functions, equality predicates and comparison procedures, 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.

(make-comparator type-test equality compare hash)

Returns a comparator which bundles the type-test, equality, compare, and hash procedures provided. As a convenience, the following additional values are accepted:

(make-char-ci-comparator)

Returns a comparator that compares characters using the total order implied by char-ci<? On R6RS and R7RS systems, this is Unicode codepoint order after the characters have been folded to lower case.

(make-string-ci-comparator)

Returns a comparator that compares strings using the total order implied by string-ci<?. Note that this order is implementation-dependent on R5RS and R7RS systems, but on R6RS systems it is the lexicographical extension of Unicode codepoint order after the characters have been folded to lower case.

(make-real-number-comparator [ type-test ])

Returns a comparator that compares real numbers using < and =. The type-test serves as the type test predicate for the comparator returned. Its default value is real?. Different comparators returned by this procedure 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 S, then the equality predicate and comparison procedures (but not necessarily the hash function) of S-comparator and T-comparator compute the same results on those objects.

(make-list-comparator element-comparator type-test empty? head tail)

Returns a comparator which compares two sequences that satisfy type-test lexicographically, as follows: