1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<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>
.issue {
background-color: pink;
padding: 0.5em;
}
</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: Composing Comparators</h1>
<p>by Daphne Preston-Kendal</p>
<h2 id="status">Status</h2>
<p>This SRFI is currently in <em>draft</em> status. Here is <a href="https://srfi.schemers.org/srfi-process.html">an explanation</a> of each status that a SRFI can hold. To provide input on this SRFI, please send email to <code><a href="mailto:srfi+minus+228+at+srfi+dotschemers+dot+org">srfi-228@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="https://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-228">archive</a>.</p>
<ul>
<li>Received: 2021-08-28</li>
<li>60-day deadline: 2021-10-30</li>
<li>Draft #1 published: 2021-08-31</li>
<li>Draft #2 published: 2022-02-26</li>
</ul>
<h2 id="abstract">Abstract</h2>
<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>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.
<h2 id="specification">Specification</h2>
<p>All identifiers defined in this SRFI are exported in the <code>(srfi 228)</code> 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.
<dl>
<dt><code>(make-wrapper-comparator</code> <var>type-test</var> <var>unwrap</var> <var>contents-comparator</var><code>)</code> (Procedure)
<dd>
<p>Returns a comparator which compares values satisfying the predicate <var>type-test</var> by first calling the given <var>unwrap</var> procedure on them, then comparing the output of that procedure with the given <var>contents-comparator</var>. The hash function of the wrapper comparator returns the same value as the <var>contents-comparator</var> run on the unwrapped value.</p>
<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 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 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.
<pre><code>(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</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:
<pre><code>(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"})</code></pre>
<h2 id="implementation">Implementation</h2>
<p>A portable sample implementation and test suite for R7RS may be found <a href="https://github.com/scheme-requests-for-implementation/srfi-228">in the repository</a> for this SRFI.
<h2 id="acknowledgements">Acknowledgements</h2>
<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>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>
<p>
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:</p>
<p>
The above copyright notice and this permission notice (including the
next paragraph) shall be included in all copies or substantial
portions of the Software.</p>
<p>
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.</p>
<hr>
<address>Editor: <a href="mailto:srfi-editors+at+srfi+dot+schemers+dot+org">Arthur A. Gleckler</a></address></body></html>
|
