228: A further comparator library

by Daphne Preston-Kendal

Status

This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-228@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

Further procedures and syntax forms for defining SRFI 128 comparators, and for extracting comparison procedures similar to those defined for Scheme’s built-in types using them.

Best enjoyed in combination with SRFI 162.

Issues

Outstanding issues are noted inline, denoted by a highlighted background.

Rationale

A typical pattern for defining comparison behaviour for record types and other user-defined Scheme types is some form of lexicographical order over their member slots. The comparator abstraction of SRFI 128 has useful potential for reducing the code bulk of defining such comparison behaviours. This library is intended to take advantage of that potential.

Specification

All identifiers defined in this SRFI are exported in the (srfi 228) library. However, as in the case of SRFI 162, it is hoped and intended that they will simply be added to the existing comparator libraries of RnRSes and Scheme implementations, rather than being in a separate library.

(make-wrapper-comparator type-test unwrap contents-comparator) (Procedure)

Returns a comparator which compares values satisfying the predicate type-test by first calling the given unwrap procedure on them, then comparing the output of that procedure with the given contents-comparator. The hash function of the wrapper comparator returns the same value as the contents-comparator run on the unwrapped value.

Add example.

(make-wrapper-comparator type-test comparator ... ) (Procedure)

Returns a comparator which compares values satisfying the given predicate type-test by comparing them with each of the given comparators in turn, left to right, and returning the result of the first non-equal comparison. If all the given comparators consider two values equal, the composed comparator also considers them equal. The hash function of the composed comparator hashes together the results of all the given comparators in an implementation-defined way.

Add example.

(compose-comparator type-test (unwrap comparator) ...) (Syntax)

Expands to a form which returns a comparator which compares values satisfying the given predicate type-test by running in turn, left to right, wrapper comparators made out of the given unwrap and comparator, according to the rules for make-composed-comparator. comparator may be omitted from each form, in which case the SRFI 128 default comparator is used.

This is equivalent to using the procedural forms make-composed-comparator and make-wrapper-comparator together.

(comparison-procedures comparator) (Procedure)

Returns five values, variadic procedures corresponding to <, <=, =, >=, and > respectively for the given comparator. Each one is equivalent to a partial application of the SRFI 128 procedures <?, <=?, =?, >=?, and >? with the given comparator.

This is admittedly a rather large number of return values. I hope that that R7RS will adopt some kind of keyword argument system, capable of being extended to keyword return values, and that it will then be possible to redefine comparison-procedures to return procedures associated with keyword names to make the order irrelevant and code using this procedure less opaque. In the meanwhile …?

As long as we’re stuck with positional return values, I should note that this isn’t the order usually used for the specification of comparison procedures (e.g. the char*? family in R7RS small uses the order char=?, char<?, char>?. char<=?, char>=?). I find the order here easier to remember, but perhaps it would be better to switch to that order for consistency.

I’d also like to provide a constructor for comparators which work on any iterable collection type (à la SRFI 158 generators). My initial plan was to use fold procedures for this, but that doesn’t actually work. Generator comparators seems like a better approach.

Examples

make-pair-comparator from SRFI 128 can be implemented in terms of this library as follows:

(define (make-pair-comparator car-comparator cdr-comparator)
  (compose-comparator pair? (car car-comparator) (cdr cdr-comparator)))

If one has defined a date record type consisting of year, month, and day fields such as:

(define-record-type <date>
  (make-date year month day)
  date?
  (year date-year)
  (month date-month)
  (day date-day))

these can be correctly compared by a comparator defined by:

(compose-comparator date?
  (date-year)  ;; Equivalent to (date-year (make-default-comparator))
  (date-month)
  (date-day))

And monomorphic comparison procedures matching those provided for Scheme’s built-in types can be defined by:

(define-values (date<? date<=? date=? date>=? date>?)
  (comparison-procedures the-date-comparator-above))

Implementation

A portable sample implementation and test suite for R7RS may be found in the repository for this SRFI.

Acknowledgements

Thanks in advance to all who will contribute to this SRFI mailing list. I hope to list you by name with your contributions here when this SRFI approaches finalization.

© 2021 Daphne Preston-Kendal.

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 (including the next paragraph) 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.


Editor: Arthur A. Gleckler