diff options
| author |  Daphne Preston-Kendal
| 2022-10-20 20:57:47 +0200 |
|---|---|---|
| committer | Daphne Preston-Kendal
| 2022-10-20 20:57:47 +0200 |
| commit | 94d2ae7d2de61948ef213c7954ed96947e2e709b (patch) | |
| tree | 7609f1ba0e8b76f91a5913a4b3b5588c20654b36 /srfi-228.html | |
| parent | Ditch file-local variables (diff) | |
Address outstanding issues
Diffstat (limited to 'srfi-228.html')
| -rw-r--r-- | srfi-228.html | 52 |
1 files changed, 18 insertions, 34 deletions
diff --git a/srfi-228.html b/srfi-228.html index 3007772..618c9ed 100644 --- a/srfi-228.html +++ b/srfi-228.html @@ -2,7 +2,7 @@ <html lang="en"> <head> <meta charset="utf-8"> - <title>SRFI 228: A further comparator library</title> + <title>SRFI 228: Composing Comparators</title> <link href="/favicon.png" rel="icon" sizes="192x192" type="image/png"> <link rel="stylesheet" href="https://srfi.schemers.org/srfi.css" type="text/css"> <style> @@ -13,7 +13,7 @@ </style> <meta name="viewport" content="width=device-width, initial-scale=1"></head> <body> -<h1><a href="https://srfi.schemers.org/"><img class="srfi-logo" src="https://srfi.schemers.org/srfi-logo.svg" alt="SRFI surfboard logo" /></a>228: A further comparator library</h1> +<h1><a href="https://srfi.schemers.org/"><img class="srfi-logo" src="https://srfi.schemers.org/srfi-logo.svg" alt="SRFI surfboard logo" /></a>228: Composing Comparators</h1> <p>by Daphne Preston-Kendal</p> @@ -28,17 +28,17 @@ <h2 id="abstract">Abstract</h2> -<p>Further procedures and syntax forms for defining <a href="https://srfi.schemers.org/srfi-128/srfi-128.html">SRFI 128</a> comparators, and for extracting comparison procedures similar to those defined for Scheme’s built-in types using them. +<p>Further procedures for defining <a href="https://srfi.schemers.org/srfi-128/srfi-128.html">SRFI 128</a> comparators. <p>Best enjoyed in combination with <a href="https://srfi.schemers.org/srfi-162/srfi-162.html">SRFI 162</a>. <h2 id="issues">Issues</h2> -<p class=issue>Outstanding issues are noted inline, denoted by a highlighted background. +<p>No remaining issues. <h2 id="rationale">Rationale</h2> -<p>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. +<p>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. <h2 id="specification">Specification</h2> @@ -51,22 +51,16 @@ <dt><code>(make-product-comparator</code> <var>comparator</var> ... <code>)</code> (Procedure) <dd> - <p>Returns a comparator which compares values satisfying the type tests of all of the given <var>comparator</var>s 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 hash function of the product comparator hashes together the results of all the given comparators in an implementation-defined way. If the equality or ordering predicates or the hash function of any of the given comparators is <code>#f</code>, the corresponding procedure in the product comparator will also be <code>#f</code>.</p> + <p>Returns a comparator which compares values satisfying the type tests of all of the given <var>comparator</var>s 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 hash function of the product comparator hashes together the results of all the given comparators in an implementation-defined way. 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.</p> <dt><code>(make-sum-comparator</code> <var>comparator</var> ... <code>)</code> (Procedure) <dd> - <p>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 hash function of the sum comparator returns the value of the hash function of the leftmost comparator whose type-test is satisfied by the given value. If the equality or ordering predicates or the hash function of any of the given comparators is <code>#f</code>, the corresponding procedure in the product comparator will also be <code>#f</code>.</p> - - <dt><code>(comparison-procedures</code> <var>comparator</var><code>)</code> (Procedure) - <dd> - <p>Returns five values, variadic procedures corresponding to <code><</code>, <code><=</code>, <code>=</code>, <code>>=</code>, and <code>></code> respectively for the given comparator. Each one is equivalent to a partial application of the SRFI 128 procedures <code><?</code>, <code><=?</code>, <code>=?</code>, <code>>=?</code>, and <code>>?</code> with the given comparator.</p> - <p class=issue>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 <code>comparison-procedures</code> to return procedures associated with keyword names to make the order irrelevant and code using this procedure less opaque. In the meanwhile …?</p> - <p class=issue>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 <code>char*?</code> family in R7RS small uses the order <code>char=?</code>, <code>char<?</code>, <code>char>?</code>. <code>char<=?</code>, <code>char>=?</code>). I find the order here easier to remember, but perhaps it would be better to switch to that order for consistency.</p> + <p>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 hash function of the sum comparator returns the value of the hash function of the leftmost comparator whose type-test is satisfied by the given value. 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.</p> </dl> <h2 id=examples>Examples</h2> -<p>Personal names are usually 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 <code>make-wrapper-comparator</code> and <code>make-product-comparator</code> can be used to create a comparator which orders a record type of personal names in this way, and how <code>comparison-procedures</code> can then be used for this ordering. +<p>Personal names are usually 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 <code>make-wrapper-comparator</code> and <code>make-product-comparator</code> can be used to create a comparator which orders a record type of personal names in this way. <pre><code>(define-record-type Person (make-person first-name last-name) @@ -79,18 +73,13 @@ (make-wrapper-comparator person? person-last-name string-ci-comparator) (make-wrapper-comparator person? person-first-name string-ci-comparator))) -(define-values (person-name<? - person-name<=? - person-name=? - person-name>? - person-name>=?) - (comparison-procedures person-name-comparator)) - -(person-name<? (make-person "John" "Cowan") - (make-person "Daphne" "Preston-Kendal")) ;=> #t +(<? person-name-comparator + (make-person "John" "Cowan") + (make-person "Daphne" "Preston-Kendal")) ;=> #t -(person-name>? (make-person "Tom" "Smith") - (make-person "John" "Smith")) ;=> #t</code></pre> +(>? person-name-comparator + (make-person "Tom" "Smith") + (make-person "John" "Smith")) ;=> #t</code></pre> <p>This example can be extended with nested comparators to sort a catalogue in which CDs appear at the end of the list after books: @@ -119,14 +108,7 @@ (define item-comparator (make-sum-comparator book-comparator cd-comparator)) -(define-values (item<? - item<=? - item=? - item>? - item>=?) - (comparison-procedures item-comparator)) - -(list-sort item<? +(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") @@ -148,12 +130,14 @@ <p><code>make-sum-comparator</code>, and by extension the inspiration for the name of <code>make-product-comparator</code>, is originally from Adam Nelson’s Schemepunk. -<p>Marc Nieper-Wißkirchen and John Cowan suggested means of improving the <code>comparison-procedures</code> procedure; as of the current draft, this remains an open issue. +<p>Jakob Wuhrer pointed out bugs in the sample implementation. <h2 id=future-work>Future work</h2> <p>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 <code>fold</code> procedures foundered on two grounds: the first and more intrinsic one is that <code>fold</code> 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 <code>fold</code>-based iteration would incorrectly consider them equal; the second is that there is currently an inconsistency among Scheme libraries in what order the <var>kons</var> procedure argument to <code>fold</code> receives the accumulator and the next values in the sequence (compare <a href="https://srfi.schemers.org/srfi-1/srfi-1.html#fold">SRFI 1 <code>fold</code></a> with <a href="https://srfi.schemers.org/srfi-133/srfi-133.html#vector-fold">SRFI 133 <code>vector-fold</code></a>). <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158</a> generators were rejected on the ground that their sequences cannot contain any arbitrary Scheme datum. +<p>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 an 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. + <h2 id="copyright">Copyright</h2> <p>© 2021 Daphne Preston-Kendal.</p> |