228: Composing Comparators

by Daphne Preston-Kendal

Status

This SRFI is currently in final 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 for defining SRFI 128 comparators.

Best enjoyed in combination with SRFI 162.

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. The identifiers in this library are not retroactively added to the exports of any other SRFI 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.

Constructors

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

(make-product-comparator comparator ... ) (Procedure)

Returns a comparator which compares values satisfying the type tests of all of the given comparators 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 product comparator also considers them equal.

The product comparator is formally defined as follows. The domain of the product comparator is the intersection of the domains of all the given comparators. The product comparator is then a comparator whose

If the ordering predicate or the hash function of any of the given comparators does not exist, the corresponding procedure in the product comparator will also not exist.

If there are no comparators given, this procedure returns the comparator-one, or a new comparator with identical behaviour to it.

Note: This procedure actually creates comparators which are more general than a comparator over a product type – for example, because each comparator has its own type test, it can be used to combine a comparator for one type with that of a subtype; or if more than one comparator looks at the same component of a type. However, in most cases it is expected that this procedure will be used together with make-wrapper-comparator to create comparators over record types, i.e. product types, hence the name.

(make-sum-comparator comparator ... ) (Procedure)

Returns a comparator which compares values satisfying the type-tests of any of the given comparators, such that values which satisfy the type-test of a given comparator are ordered before any values satisfying the type-tests of any comparators appear to the right of it, and values satisfying the same comparator’s type-test are tested for ordering and equality according that comparator.

The sum comparator is formally defined as follows. The domain of the sum comparator is the union of the domains of all the given comparators. The relevant comparator for a given value is the leftmost of the given comparators whose type test answers true for that value. The sum comparator is then a comparator whose

If the ordering predicate or the hash function of any of the given comparators does not exist, the corresponding procedure in the sum comparator will also not exist.

If there are no comparators given, this procedure returns the comparator-zero, or a new comparator with identical behaviour to it.

Base Cases

comparator-one (Comparator)

A comparator which has all values in its domain and considers all values to be equal. Specifically, its:

comparator-zero (Comparator)

A comparator whose type test always returns #f. Since this comparator has no values in its domain, it is always an error to invoke its equality predicate, ordering predicate, or hash function.

Examples

Personal names are often sorted lexicographically and case-insensitively by the last name, then the first name if the last names are the same. The following example shows how make-wrapper-comparator and make-product-comparator can be used to create a comparator which orders a record type of personal names in this way. 

(define-record-type Person
  (make-person first-name last-name)
  person?
  (first-name person-first-name)
  (last-name person-last-name))

(define person-name-comparator
  (make-product-comparator
   (make-wrapper-comparator person? person-last-name string-ci-comparator)
   (make-wrapper-comparator person? person-first-name string-ci-comparator)))

(<? person-name-comparator
    (make-person "John" "Cowan")
    (make-person "Daphne" "Preston-Kendal")) ;=> #t

(>? person-name-comparator
    (make-person "Tom" "Smith")
    (make-person "John" "Smith")) ;=> #t

This example can be extended with nested comparators to sort a catalogue in which CDs appear at the end of the list after books: 

(define-record-type Book
  (make-book author title)
  book?
  (author book-author)
  (title book-title))

(define book-comparator
  (make-product-comparator
   (make-wrapper-comparator book? book-author person-name-comparator)
   (make-wrapper-comparator book? book-title string-ci-comparator)))

(define-record-type CD
  (make-cd artist title)
  cd?
  (artist cd-artist)
  (title cd-title))

(define cd-comparator
  (make-product-comparator
   (make-wrapper-comparator cd? cd-artist person-name-comparator)
   (make-wrapper-comparator cd? cd-title string-ci-comparator)))

(define item-comparator
  (make-sum-comparator book-comparator cd-comparator))

(list-sort (lambda (a b) (<? item-comparator a b))
           (list (make-cd (make-person "The" "Beatles") "Abbey Road")
                 (make-book (make-person "Jacob" "Grimm") "Deutsche Grammatik")
                 (make-book (make-person "William" "Shakespeare") "Sonnets")
                 (make-book (make-person "William" "Shakespeare") "A Midsummer Night’s Dream")
                 (make-cd (make-person "Bob" "Dylan") "Blonde on Blonde")
                 (make-cd (make-person "The" "Beatles") "Revolver")))
;; => ({Book {Person "Jacob" "Grimm"} "Deutsche Grammatik"}
;;     {Book {Person "William" "Shakespeare"} "A Midsummer Night’s Dream"}
;;     {Book {Person "William" "Shakespeare"} "Sonnets"}
;;     {CD {Person "The" "Beatles"} "Abbey Road"}
;;     {CD {Person "The" "Beatles"} "Revolver"}
;;     {CD {Person "Bob" "Dylan"} "Blonde on Blonde"})

Implementation

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

Acknowledgements

make-sum-comparator, and by extension the inspiration for the name of make-product-comparator, is originally from Adam Nelson’s Schemepunk.

Shiro Kawai requested a clearer definition of the individual procedures of sum and product comparators. He also suggested defining the base cases of make-product-comparator and make-sum-comparator. Jakob Wuhrer produced a detailed analysis showing the correct behaviour of the base cases comparator-one and comparator-zero, and also pointed out bugs in the sample implementation.

Lassi Kortela and Marc Nieper-Wißkirchen pointed out that the names make-product-comparator and make-sum-comparator are confusing and, in the former case, slightly incorrect in the analogy to product types of type theory. However, since nobody on the list could come up with a better name which makes clear what the two comparator compositions do, and their relationship to one another, the names were retained.

Arthur Gleckler was extraordinarily patient. He also turned the examples above into the initial version of the test suite for this SRFI’s sample implementation.

Future Work

The author hopes that a future SRFI will add a procedure for creating comparators yielding lexicographical order over any sequence type by delegating to a common iteration protocol. An idea to do this using fold procedures foundered on two grounds: the first and more intrinsic one is that fold called on two sequences, one of which is a prefix of the other, cannot determine which of the two is longer, and a sort using fold-based iteration would incorrectly consider them equal; the second is that there is currently an inconsistency among Scheme libraries in what order the kons procedure argument to fold receives the accumulator and the next values in the sequence (compare SRFI 1 fold with SRFI 133 vector-fold). SRFI 158 generators were rejected on the ground that their sequences cannot contain any arbitrary Scheme datum.

Earlier drafts of this SRFI contained a procedure to convert a SRFI 128 comparator into a set of Scheme comparison procedures. This was dropped because a satisfactory interface, with sufficient efficiency and usability, could not be found. Thanks are due nonetheless to John Cowan and Marc Nieper-Wißkirchen for their suggestions to resolve this issue. Likewise, it is hoped that a future SRFI will respond to this need.

© 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