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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>SRFI 225: Dictionaries</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">
<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>225: Dictionaries</h1>
<p>by John Cowan (spec) and Arvydas Silanskas (implementation)</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+225+at+srfi+dotschemers+dot+org">srfi-225@<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-225">archive</a>.</p>
<ul>
<li>Received: 2021-06-26</li>
<li>60-day deadline: 2021-09-16</li>
<li>Draft #1 published: 2021-07-18</li>
<li>Draft #2 published: 2021-07-26</li>
<li>Draft #3 published: 2021-08-07</li>
<li>Draft #4 published: 2021-10-29</li>
<li>Draft #5 published: 2021-11-13</li>
<li>John Cowan's <a href="https://github.com/pre-srfi/dictionaries">personal
Git repo for this SRFI</a> for reference while the SRFI is in
<em>draft</em> status (<a href="https://htmlpreview.github.io/?https://github.com/johnwcowan/srfi-225/blob/master/srfi-225.html">preview</a>)</li>
</ul>
<h2 id="abstract">Abstract</h2>
<p>The procedures of this SRFI allow callers to
manipulate an object that maps keys to values
without the caller needing to know exactly what the type
of the object is.
However, what procedures can be called on the dictionary
is partly determined by whether it is persistent or mutable.
Such an object is called a <em>dict</em> in this SRFI.
<h2 id="issues">Issues</h2>
None at present.
<h2 id="rationale">Rationale</h2>
<p>Until recently there was only one universally available mechanism for managing key-value pairs: alists. Most Schemes also support hash tables, but until R6RS there was no standard interface to them, and many implementations do not provide that interface.</p>
<p>Now, however, the number of such mechanisms is growing. In addition to both R6RS and R7RS hash tables, there are R7RS persistent ordered and hashed mappings from SRFI 146, ordered mappings with fixnum keys from SRFI 224, and ordered bytevector key-value stores (often on a disk or a remote machine) from SRFI 167.</p>
<p>It’s inconvenient for users if SRFIs or other libraries have to insist on accepting only a specific type of dictionary. This SRFI exposes a number of accessors, mutators, and other procedures that can be called on any dictionary, provided that a <em>dictionary type descriptor</em> (DTD, with apologies to SGML and XML users) is available for it: either exported from this SRFI, or from other SRFIs or libraries, or created by the user. DTDs are of an unspecified type.</p>
<p>This in turn requires that the DTD provides a predicate that can recognize its dictionaries, plus several primitive generic procedures.</p>
<p>By using the procedures of this SRFI, a procedure can take a DTD and a dictionary as an argument and make flexible use of the dictionary without knowing its exact type. For the purposes of this SRFI, such a procedure is called a <em>generic procedure</em>.</p>
<p>However, dictionaries need to be constructed using type-specific constructors, as the required and optional arguments differ in each case. In addition, the dictionary type provided by the caller of a generic procedure doesn't necessarily have the right performance characteristics needed by the generic procedure itself. Consequently there are no <code>make-dict</code>, <code>dict</code>, <code>dict-unfold</code>, <code>dict-copy</code> or similar procedures in this SRFI.</p>
<h2 id="specification">Specification</h2>
<p>We call a specific key-value combination an <em>association</em>. This is why an alist, or association list, is called that; it is a list of associations represented as pairs.</p>
<p>A <em>dictionary</em> or <em>dict</em> is a collection of associations which may be ordered or unordered. In principle an <em>equality predicate</em> is enough, given a key, to determine whether an association with that key exists in the dictionary. However, for efficiency most dictionaries require an <em>ordering predicate</em> or a <em>hash function</em> as well.
<p>When a key argument is said to be the same as some key of the dictionary, it means that they are the same in the sense of the dictionary’s implicit or explicit equality predicate. It is assumed that no dictionary contains two keys that are the same in this sense.
Two dictionaries are <em>similar</em> if they are of the same type and have the same equality predicate and the same ordering predicate and/or hash function.</p>
<h3 id="alists">Alists</h3>
<p>Alists are supported as dictionaries, but are given special treatment. New values are added to the beginning of the alist and the new alist is returned. If an association has been updated, then both the new and the old association may be processed by the whole-dictionary procedures; by the same token, if an association is removed, any later association with the same key will be exposed. The examples in this SRFI use alists.</p>
<p>An alist (unlike a hashtable or mapping) does not know which equality predicate its users intend to use on it. Therefore, rather than exporting a single DTD for all alists, this SRFI provides a procedure <code>make-alist-dtd</code> that takes an equality predicate and returns a DTD specialized for manipulation of alists using that predicate. For convenience, DTDs for <code>eqv?</code> and <code>equal?</code> are exported.</p>
<p>Each of the following examples is assumed to be prefixed by the following definitions:</p>
<blockquote><pre>(define dict (list '(1 . 2) '(3 . 4) '(5 . 6)))
(define aed alist-eqv-dtd)
</pre></blockquote>
Consequently, previous examples don't affect later ones.
<p>The <em>dtd</em> argument is not discussed in the individual procedure descriptions below, but it is an error if invoking <code>dictionary?</code> on <em>dtd</em> and <em>dict</em> would return <code>#f</code>. The <code>dictionary?</code> procedure itself is an exception to this.</p>
<h3 id="predicates">Predicates</h3>
<p><code>(dictionary?</code> <em>dtd obj</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>obj</em> answers <code>#t</code> to the type predicate stored in <em>dtd</em> and <code>#f</code> otherwise.</p>
<blockquote><pre>(dictionary? aed dict) => #t
(dictionary? aed 35) => #t</pre></blockquote>
<p><code>(dict-empty?</code> <em>dtd dict</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>dict</em> contains no associations and <code>#f</code> if it does contain associations.</p>
<blockquote><pre>(dict-empty? aed '()) => #t
(dict-empty? aed dict) => #f</pre></blockquote>
<p><code>(dict-contains?</code> <em>dtd dict key</em><code>)</code></p>
<blockquote><pre>(dict-contains? aed dict 1) => #t
(dict-contains? aed dict 2) => #f</pre></blockquote>
<p>Returns <code>#t</code> if one of the keys of <em>dict</em> is the same as <em>key</em>, and <code>#f</code> otherwise.</p>
<p><code>(dict=?</code> <em>dtd = dict1 dict2</em><code>)</code></p>
<p>Returns <code>#t</code> if the keys of <em>dtd dict1</em> and <em>dict2</em> are the same, and the corresponding values are the same in the sense of the <em>=</em> argument.</p>
<blockquote><pre>
(define dicta '((5 . 6) (3 . 4) (1 . 2))
(define dictb '((1 . 2) (3 . 4))
(dict=? aed = dict dicta) => #t
(dict=? aed = dict dictb) => #f</pre></blockquote>
<p><code>(dict-mutable?</code> <em>dtd dict</em><code>)</code></p>
<p>Returns <code>#t</code> if the dictionary type supports mutations and <code>#f</code> if it supports functional updates.</p>
<blockquote><pre>
(dict-mutable? hash-table-dtd (make-hash-table)) => #t
(dict-mutable? aed dict) => #f
</pre></blockquote>
<h3 id="lookup">Lookup</h3>
<p><code>(dict-ref</code> <em>dtd dict key</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>
<p>If <em>key</em> is the same as some key of <em>dict</em>, then invokes <em>success</em> on the corresponding value and returns its result. If <em>key</em> is not a key of <em>dict</em>, then invokes the thunk <em>failure</em> and returns its result. The default value of <em>failure</em> signals an error; the default value of <em>success</em> is the identity procedure.</p>
<blockquote><pre>(dict-ref aed dict 1 (lambda () '()) list) =>
(1) ; Success wraps value in a list
(dict-ref aed dict 2 (lambda () '()) list) =>
() ; Failure returns empty list</pre></blockquote>
<p><code>(dict-ref/default</code> <em>dtd dict key default</em><code>)</code></p>
<p>If <em>key</em> is the same as some key of <em>dict</em>, returns the corresponding value. If not, returns <em>default</em>.</p>
<blockquote><pre>(dict-ref/default aed dict 1 #f) => 1
(dict-ref/default aed dict 1 #f) => #f</pre></blockquote>
<h3 id="mutation">Functional update and mutation</h3>
<p>All these procedures exist in pairs, with and without a final <code>!</code>. The descriptions apply to the procedures without <code>!</code>; the procedures with <code>!</code> mutate their dictionary argument and do not return a dictionary value. Only one set of procedures is supported by any dictionary: for example, SRFI 125 hash tables support only mutation, whereas SRFI 146 mappings support only functional update. The <code>dict-mutable?</code> procedure can be used to determine which set is usable.</p>
<p><code>(dict-set</code> <em>dtd dict obj</em> …<code>)</code><br>
<code>(dict-set!</code> <em>dtd dict obj</em> …<code>)</code></p>
<p>Returns a dictionary that contains all the associations of <em>dict</em> plus those specified by <em>objs</em>, which alternate between keys and values. If a key to be added already exists in <em>dict</em>, the new value prevails.</p>
<blockquote><pre>; new values are prepended
(dict-set aed dict 7 8) =>
((7 . 8) (1 . 2) (3 . 4) (5 . 6))
(dict-set aed dict 3 5) =>
((3 . 5) (1 . 2) (3 . 4) (5 . 6))</pre></blockquote>
<p><code>(dict-adjoin</code> <em>dtd dict objs</em><code>)</code><br>
<code>(dict-adjoin!</code> <em>dtd dict objs</em><code>)</code></p>
<p>Returns a dictionary that contains all the associations of <em>dict</em> plus those specified by <em>objs</em>, which alternate between keys and values. If a key to be added already exists in <em>dict</em>, the old value prevails.</p>
<blockquote><pre>; new values are prepended to alists
(dict-adjoin aed dict 7 8) =>
((7 . 8) (1 . 2) (3 . 4) (5 . 6))
(dict-adjoin aed dict 3 5) =>
((1 . 2) (3 . 4) (5 . 6))</pre></blockquote>
<p><code>(dict-delete</code> <em>dtd dict key</em> …<code>)</code><br>
<code>(dict-delete!</code> <em>dtd dict key</em> …<code>)</code></p>
<p>Returns a dictionary that contains all the associations of <em>dict</em> except those whose keys are the same as one of the <em>keys</em>.</p>
<blockquote><pre>; new values are prepended
(dict-delete aed dict 1 3) =>
((5. 6)) ; may share
(dict-delete aed dict 5) =>
((1 . 2) (3 . 4))</pre></blockquote>
<p><code>(dict-delete-all</code> <em>dtd dict keylist</em><code>)</code><br>
<code>(dict-delete-all!</code> <em>dtd dict keylist</em><code>)</code></p>
<p>Returns a dictionary with all the associations of <em>dict</em> except those whose keys are the same as some member of <em>keylist</em>.</p>
<blockquote><pre>(dict-delete-all aed dict '(1 3)) => ((5 . 6))</pre></blockquote>
<p><code>(dict-replace</code> <em>dtd dict key value</em><code>)</code><br>
<code>(dict-replace!</code> <em>dtd dict key value</em><code>)</code></p>
<p>Returns a dictionary that contains all the associations of <em>dict</em> except as follows: If <em>key</em> is the same as a key of <em>dict</em>, then the association for that key is omitted and replaced by the association defined by the pair <em>key</em> and <em>value</em>. If there is no such key in <em>dict</em>, then dictionary is returned unchanged.</p>
<blockquote><pre>(dict-replace aed dict 1 3) =>
((1 . 3) (1 . 2) (3 . 4) (5 . 6)) </pre></blockquote>
<p><code>(dict-intern</code> <em>dtd dict key failure</em>)<br>
<code>(dict-intern!</code> <em>dtd dict key failure</em>)</p>
<p>If there is a key in <em>dict</em> that is the same as <em>key</em>, returns two values, <em>dict</em> and the value associated with <em>key</em>.
Otherwise, returns two values, a dictionary that contains all the associations of <em>dict</em> and in addition a new association that maps <em>key</em> to the result of invoking <em>failure</em>, and the result of invoking <em>failure</em>.<br>
<blockquote><pre>(dict-intern aed dict 1 (lambda () #f)) => ; 2 values
((1 . 2) (3 . 4) (5 . 6))
2
(dict-intern aed dict 2 (lambda () #f)) => ; 2 values
((2 . #f) (1 . 2) (3 . 4) (5 . 6))
#f</pre></blockquote>
<p><code>(dict-update</code> <em>dtd dict key updater</em> [<em>failure</em> [<em>success</em>] ]<code>)</code><br>
<code>(dict-update!</code> <em>dtd dict key updater</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>
<p>Retrieves the value of <em>key</em> as if by <code>dict-ref</code>, invokes <em>updater</em> on it, and sets the value of <em>key</em> to be the result of calling <em>updater</em> as if by <code>dict-set</code>, but may do so more efficiently. Returns the updated dictionary. The default value of <em>failure</em> signals an error; the default value of <em>success</em> is the identity procedure.</p>
<blockquote><pre>
(dict-update aed dict 1 (lambda (x) (+ 1 x))) =>
((1 3) (1 2) (3 4) (5 6))
(dict-update aed dict 2 (lambda (x) (+ 1 x))) =>
<em>error</em>
</pre></blockquote>
<p><code>(dict-update/default</code> <em>dtd dict key updater default</em><code>)</code><br>
<code>(dict-update/default!</code> <em>dtd dict key updater default</em><code>)</code></p>
<p>Retrieves the value of <em>key</em> as if by <code>dict-ref/default</code>, invokes <em>updater</em> on it, and sets the value of <em>key</em> to be the result of calling <em>updater</em> as if by <code>dict-set</code>, but may do so more efficiently. Returns the updated dictionary.</p>
<blockquote><pre>
(dict-update/default aed dict 1
(lambda (x) (+ 1 x)) 0) =>
((1 3) (1 2) (3 4) (5 6))
(dict-update/default aed dict 2
(lambda (x) (+ 1 x)) 0) =>
((1 0) (1 2) (3 4) (5 6))
</pre></blockquote>
<p><code>(dict-pop</code> <em>dtd dict</em><code>)</code><br>
<code>(dict-pop!</code> <em>dtd dict</em><code>)</code></p>
<p>Chooses an association from <em>dict</em> and returns three values: a dictionary that contains all associations of <em>dict</em> except the chosen one, and the key and the value of the association chosen. If the dictionary is ordered, the first association is chosen; otherwise the chosen association is arbitrary.</p>
<p>If dictionary contains no associations, it is an error.</p>
<blockquote><pre>(dict-pop aed dict) => ; 3 values
((3 . 4) (5 . 6))
1
2</pre></blockquote>
<p><code>(dict-map</code> <em>dtd proc dict</em><code>)</code><br>
<code>(dict-map!</code> <em>dtd proc dict</em><code>)</code></p>
<p>Returns a dictionary similar to <em>dict</em> that maps each key of <em>dict</em> to the <em>proc</em> on the key and corresponding value of <em>dict</em>.</p>
<blockquote><pre>(dict-map (lambda (k v) (cons v k)) aed dict) =>
((2 . 1) (4 . 3) (6 . 5))</pre></blockquote>
<p><code>(dict-filter</code> <em>dtd pred dict</em><code>)</code><br>
<code>(dict-filter!</code> <em>dtd pred dict</em><code>)</code><br>
<code>(dict-remove</code> <em>dtd pred dict</em><code>)</code><br>
<code>(dict-remove!</code> <em>dtd pred dict</em><code>)</code></p>
<p>Returns a dictionary similar to <em>dict</em> that contains just the associations of <em>dict</em> that satisfy / do not satisfy <em>pred</em> when it is invoked on the key and value of the association.</p>
<blockquote><pre>(dict-filter (lambda (k v) (= k 1)) aed dict) =>
((1 . 2))
(dict-remove (lambda (k) (= k 1)) aed dict) =>
((3 . 4) (5 . 6))</pre></blockquote>
<p><code>(dict-alter</code> <em>dtd dict key failure success</em><code>)</code><br>
<code>(dict-alter!</code> <em>dtd dict key failure success</em><code>)</code></p>
<p>This procedure is a workhorse for dictionary lookup, insert, and delete. The dictionary <em>dict</em> is searched for an association whose key is the same as <em>key</em>. If one is not found, then the <em>failure</em> procedure is tail-called with two procedure arguments, <em>insert</em> and <em>ignore</em>.</p>
<p>If such an association is found, then the <em>success</em> procedure is tail-called with the matching key of <em>dict</em>, the associated value, and two procedure arguments, <em>update</em> and <em>remove</em>.</p>
<p>In either case, the values returned by <em>failure</em> or <em>success</em> are returned.</p>
<ul>
<li><p>Invoking <code>(</code><em>insert value</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, and in addition a new association that maps <em>key</em> to <em>value</em>.</p></li>
<li><p>Invoking <code>(</code><em>ignore</em><code>)</code> has no effects and returns <em>dict</em> unchanged.</p></li>
<li><p>Invoking <code>(</code><em>update new-key new-value</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, except for the association whose key is the same as <em>key</em>, which is replaced or hidden by a new association that maps <em>new-key</em> to <em>new-value</em>. It is an error if <em>key</em> and <em>new-key</em> are not the same in the sense of the dictionary’s equality predicate.</p></li>
<li><p>Invoking <code>(</code><em>remove</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, except for the association with key key.</p></li>
</ul>
<p>Here are four examples of <code>dict-alter</code>,
one for each of the four procedures:
<blockquote><pre>
;; ignore
(define-values
(dict value)
(dict-alter (alist->dict '((a . b))) 'c
(lambda (insert ignore)
(ignore))
(lambda args
(error))))
(dict->alist aed dict)) => ((a . b))
;; insert
(define-values
(dict value)
(dict-alter (alist->dict '((a . b))) 'c
(lambda (insert ignore)
(insert 'd))
(lambda args
(error))))
(dict-ref aed dict 'a)) => b
(dict-ref aed dict 'c)) => 'd
;; update
(define-values
(dict value)
(dict-alter (alist->dict '((a . b))) 'a
(lambda args
(error))
(lambda (key value update delete)
(update 'a2 'b2))))
(dict->alist aed dict) => ((a2 . b2)
;; delete
(define-values
(dict value)
(dict-alter (alist->dict '((a . b) (c . d))) 'a
(lambda args
(error))
(lambda (key value update delete)
(delete))))
(dict->alist aed dict)) => ((c . d))
</pre></blockquote>
<h3 id="the-whole-dictionary">The whole dictionary</h3>
<p><code>(dict-size</code> <em>dtd dict</em><code>)</code></p>
<p>Returns an exact integer representing the number of associations in <em>dict</em>.</p>
<blockquote><pre>(dict-size aed dict) => 3</pre></blockquote>
<p><code>(dict-count</code> <em>dtd pred dict</em><code>)</code></p>
<p>Passes each association of dictionary as two arguments to <em>pred</em> and returns the number of times that <em>pred</em> returned true as an an exact integer.</p>
<blockquote><pre>(dict-count aed dict (lambda (k v) (even? k))) => 0</pre></blockquote>
<p><code>(dict-any</code> <em>dtd pred dict</em><code>)</code></p>
<p>Passes each association of <em>dict</em> as two arguments to <em>pred</em> and returns the value of the first call to <em>pred</em> that returns true, after which no further calls are made. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. If all calls return false, <code>dict-any</code> returns false.</p>
<blockquote><pre>(define (both-even? k v) (and (even? k) (even? v)))
(dict-any aed both-even? '((2 . 4) (3 . 5))) => #t
(dict-any aed both-even? '((1 . 2) (3 . 4))) => #f</pre></blockquote>
<p><code>(dict-every</code> <em>dtd pred dict</em><code>)</code></p>
<p>Passes each association of <em>dict</em> as two arguments to <em>pred</em> and returns <code>#f</code> after the first call to <em>pred</em> that returns false, after which no further calls are made. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. If all calls return true, <code>dict-any</code> returns the value of the last call, or <code>#t</code> if no calls are made.</p>
<blockquote><pre>(define (some-even? k v) (or (even? k) (even? v)))
(dict-every aed some-even? '((2 . 3) (3 . 4))) => #t
(dict-every aed some-even? '((1 . 3) (3 . 4))) => #f</pre></blockquote>
<p><code>(dict-keys</code> <em>dtd dict</em><code>)</code></p>
<p>Returns a list of the keys of <em>dict</em>. If the dictionary type is inherently ordered, associations appear in the inherent order; otherwise in an arbitrary order. The order may change when new elements are added to <em>dict</em>.</p>
<blockquote><pre>(dict-keys aed dict) => (1 3 5)</pre></blockquote>
<p><code>(dict-values</code> <em>dtd dict</em><code>)</code></p>
<p>Returns a list of the values of <em>dict</em>. The results returned by <code>dict-keys</code> and <code>dict-values</code> are not necessarily ordered consistently.</p>
<blockquote><pre>(dict-values aed dict) => (2 4 6)</pre></blockquote>
<p><code>(dict-entries</code> <em>dtd dict</em><code>)</code></p>
<p>Returns two values, the results of calling <code>dict-keys</code> and the result of calling <code>dict-values</code> on <em>dict</em>.</p>
<blockquote><pre>(dict-entries aed dict) => ; 2 values
(1 3 5)
(2 4 6)</pre></blockquote>
<p><code>(dict-fold</code> <em>dtd proc knil dict</em><code>)</code></p>
<p>Invokes <em>proc</em> on each association of <em>dict</em> with three arguments: the key of the association, the value of the association, and an accumulated result of the previous invocation. For the first invocation, <em>knil</em> is used as the third argument. Returns the result of the last invocation, or <em>knil</em> if there was no invocation. Note that there is no guarantee of a consistent result if the dictionary does not have an inherent order.</p>
<blockquote><pre>(dict-fold + 0 '((1 . 2) (3 . 4))) => 10</pre></blockquote>
<p><code>(dict-map->list</code> <em>dtd proc dict</em><code>)</code></p>
<p>Returns a list of values that result from invoking <em>proc</em> on the keys and corresponding values of <em>dict</em>.</p>
<blockquote><pre>
(dict-map->list (lambda (k v) v) dict) =>
(2 4 6),
(dict-map->list - aed dict) =>
(-1 -1 -1) ; subtract value from key
</pre></blockquote>
<p><code>(dict->alist</code> <em>dtd dict</em><code>)</code></p>
<p>Returns an alist whose keys and values are the keys and values of <em>dict</em>.</p>
<p>Add <code>dict-map</code>,
<code>dict-filter</code>, <code>dict-remove</code>,
and <code>dict-alter</code>.
</p>
<p><code>(dict-comparator</code> <em>dtd dict</em><code>)</code></p>
<p>Return a comparator representing the type predicate, equality predicate, ordering predicate, and hash function of <em>dict</em>. The last two may be <code>#f</code> if the dictionary does not make use of these functions.</p>
<p>If no comparator is relevant to the dictionary type, returns <code>#f</code>.</p>
<h3 id="iteration">Iteration</h3>
<p><code>(dict-for-each</code> <em>dtd proc dict</em><code>)</code></p>
<p>Invokes <em>proc</em> on each key of <em>dict</em> and its corresponding value in that order. This procedure is used for doing operations on the whole dictionary. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. Returns an unspecified value.</p>
<blockquote><pre>(define (write-key key value) (write key))
(dict-for-each write-key aed dict) => unspecified
; writes "135" to current output</pre></blockquote>
<p><code>(dict-for-each<</code> <em>dtd proc dict key</em><code>)</code><br>
<code>(dict-for-each<=</code> <em>dtd proc dict key</em><code>)</code><br>
<code>(dict-for-each></code> <em>dtd proc dict key</em><code>)</code><br>
<code>(dict-for-each>=</code> <em>dtd proc dict key</em><code>)</code></p>
<p>Invokes <em>proc</em> on each key of <em>dict</em> that is less than / less than or equal to / greater than / greater than or equal to <em>key</em> and its corresponding value. This procedure is used for doing operations on part of the dictionary. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. Returns an unspecified value.</p>
<p><code>(dict-for-each-in-open-interval</code> <em>dtd proc dict key1 key2</em><code>)</code><br>
<code>(dict-for-each-in-closed-interval</code> <em>dtd proc dict key1 key2</em><code>)</code><br>
<code>(dict-for-each-in-open-closed-interval</code> <em>dtd proc dict key1 key2</em><code>)</code><br>
<code>(dict-for-each-in-closed-open-interval</code> <em>dtd proc dict key1 key2</em><code>)</code></p>
<p>Invokes <em>proc</em> on each key of <em>dict</em> that is that is within the specified interval between <em>key1</em> and <em>key2</em>, and its corresponding value. This procedure is used for doing operations on part of the dictionary. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. Returns an unspecified value.</p>
<h3 id="generator-procedures">Generator procedures</h3>
<p><code>(make-dict-generator</code> <em>dtd dict</em><code>)</code></p>
<p>Returns a <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">generator</a> that when invoked returns the associations of <em>dict</em> as pairs. When no associations are left, returns an end-of-file object. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. It is an error to mutate <em>dict</em> until the generator is exhausted.</p>
<p><code>(dict-set-accumulator</code> <em>dtd dict</em><code>)</code></p>
<p>Returns a SRFI 158 accumulator procedure that when invoked on a pair adds the <code>car</code> and <code>cdr</code> of the pair as a key and value, returning the new value of the dictionary. If invoked on an end-of-file object, no action is taken and <em>dict</em> is returned. If a key to be added already exists in dictionary, the new value prevails.</p>
<p><code>(dict-adjoin-accumulator</code> <em>dtd dict</em><code>)</code></p>
<p>The same as <code>dict-set-accumulator</code>, except that if a key to be added already exists in dictionary, the old value prevails.</p>
<h3 id="dictionary-type-descriptor-procedures">Dictionary type descriptor procedures</h3>
<p><code>(dtd?</code> <em>obj</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>obj</em> is a DTD, and <code>#f</code> otherwise.</p>
<p><code>(make-dtd</code> <em>arg</em> …<code>)</code><br>
<code>(dtd (</code><em>proc-id procname</em><code>)</code> …<code>)</code> [syntax]</p>
<p>Returns a new DTD providing procedures that allow manipulation of dictionaries of that type. The <em>args</em> are alternately <em>proc-ids</em> and corresponding <em>procs</em>.</p>
<p>A <em>proc-id</em> argument is the value of a variable whose name is the same as a procedure (except those in this section and the Exceptions section) suffixed with <code>-id</code>, and a <em>proc</em> argument is the specific procedure implementing it for this type.
Note that there is only one proc-id variable for each pair of mutation and functional-update procedures:
the proc-id variable for <code>dict-map-id</code> and <code>dict-map!</code> is <code>dict-map-id</code>.</p>
<p>The following proc-id variables (and corresponding primitive procedures) need to be provided in order for the DTD to support the full set of dictionary procedures:</p>
<ul>
<li><code>dictionary?-id</code></li>
<li><code>dict-alter-id</code></li>
<li><code>dict-comparator-id</code></li>
<li><code>dict-map-id</code></li>
<li><code>dict-mutable?-id</code></li>
<li><code>dict-remove-id</code></li>
<li><code>dict-size-id</code></li>
</ul>
<p>Note that it is not an error to omit any of these, but some dictionary procedures may be unavailable.</p>
<p>There are additional proc-id variables that may be provided with corresponding procedures in order to increase efficiency. For example, it is not necessary to provide a <code>dict-ref</code> procedure, because the default version is built on top of <code>dict-alter</code> or <code>dict-alter!</code>. But if the underlying dictionary provides its own <code>-ref</code> procedure, it may be more efficient to specify it to <code>make-dtd</code> using <code>dict-ref-id</code>. Here is the list of additional proc-id variables:</p>
<ul>
<li><code>dict->alist-id</code></li>
<li><code>dict-adjoin-accumulator-id</code></li>
<li><code>dict-adjoin-id</code></li>
<li><code>dict-any-id</code></li>
<li><code>dict-contains?-id</code></li>
<li><code>dict-count-id</code></li>
<li><code>dict-delete-all-id</code></li>
<li><code>dict-delete-id</code></li>
<li><code>dict-empty?-id</code></li>
<li><code>dict-entries-id</code></li>
<li><code>dict-every-id</code></li>
<li><code>dict-filter-id</code></li>
<li><code>dict-fold-id</code></li>
<li><code>dict-for-each<-id</code></li>
<li><code>dict-for-each<=-id</code></li>
<li><code>dict-for-each-id</code></li>
<li><code>dict-for-each-in-closed-interval-id</code></li>
<li><code>dict-for-each-in-closed-open-interval-id</code></li>
<li><code>dict-for-each-in-open-closed-interval-id</code></li>
<li><code>dict-for-each-in-open-interval-id</code></li>
<li><code>dict-for-each>-id</code></li>
<li><code>dict-for-each>=-id</code></li>
<li><code>dict-intern-id</code></li>
<li><code>dict-keys-id</code></li>
<li><code>dict-map->list-id</code></li>
<li><code>dict-map-id</code></li>
<li><code>dict-pop-id</code></li>
<li><code>dict-ref-id</code></li>
<li><code>dict-ref/default-id</code></li>
<li><code>dict-remove-id</code></li>
<li><code>dict-replace-id</code></li>
<li><code>dict-set-accumulator-id</code></li>
<li><code>dict-set-id</code></li>
<li><code>dict-update-id</code></li>
<li><code>dict-update/default-id</code></li>
<li><code>dict-values-id</code></li>
<li><code>dict=?-id</code></li>
<li><code>make-dict-generator-id</code></li>
</ul>
<p>The <code>dtd</code> macro behaves like a wrapper around <code>make-dtd</code> with parentheses around each <em>procid-procname</em> pair. The macro may also verify that the <em>proc-ids</em> are valid, that there are no duplicates, etc.</p>
<p><code>(make-alist-dtd</code> <em>equal</em><code>)</code></p>
<p>Returns a DTD for manipulating an alist using the equality predicate <em>equal</em>.</p>
<blockquote><code>(make-alist-dtd =) => a DTD for alists using numeric equality</code></blockquote>
<p><code>(dtd-ref</code> <em>dtd proc-id</em><code>)</code></p>
<p>Returns the procedure designated by <em>proc-id</em> from <em>dtd</em>.
This allows the ability to call a particular DTD procedure multiple times more efficiently.</p>
<h3 id="exceptions">Exceptions</h3>
<p><code>(dictionary-error</code> <em>message irritant</em> ... <code>)</code></p>
<p>Returns a dictionary error with the given <em>message</em> (a string) and
<em>irritants</em> (any objects).
If a particular procedure in a DTD cannot be implemented, it instead
should signal an appropriate dictionary error that can be reliably caught.
<p><code>(dictionary-error?</code> <em>obj</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>obj</em> is a dictionary error
and <code>#f</code> otherwise.
<p><code>(dictionary-message</code> <em>dictionary-error</em><code>)</code></p>
<p>Returns the message associated with <em>dictionary-error.</em></p>
<p><code>(dictionary-irritants</code> <em>dictionary-error</em><code>)</code></p>
<p>Returns a list of the irritants associated with <em>dictionary-error</em>.</p>
<h3 id="exported-dtds">Exported DTDs</h3>
<p>The following DTDs are exported from this SRFI:
<code>srfi-69-dtd</code>, <code>hash-table-dtd</code>, <code>srfi-126-dtd</code>,
<code>mapping-dtd</code>, <code>hash-mapping-dtd</code>,
<code>alist-eqv-dtd</code>, and <code>alist-equal-dtd</code>.
The last two provide DTDs for alists using <code>eqv?</code>
and <code>equal?</code> respectively.</p>
<h2 id="implementation">Implementation</h2>
<p>The sample implementation is found in the GitHub repository.</p>
<p>The following list of dependencies is designed to ease defining
new dictionary types that may not have complete dictionary APIs:</p>
<dl>
<dt>dict-empty?</dt>
<dd>dict-size</dd>
<dt>dict=?</dt>
<dd>dict-ref</dd>
<dd>dict-keys</dd>
<dd>dict-size</dd>
<dt>dict-contains?</dt>
<dd>dict-ref</dd>
<dt>dict-ref</dt>
<dd>dict-mutable?</dd>
<dd>dict-alter or dict-alter!</dd>
<dt>dict-ref/default</dt>
<dd>dict-ref</dd>
<dt>dict-set</dt>
<dd>dict-alter</dd>
<dt>dict-adjoin</dt>
<dd>dict-alter</dd>
<dt>dict-delete</dt>
<dd>dict-delete-all</dd>
<dt>dict-delete-all</dt>
<dd>dict-alter</dd>
<dt>dict-replace</dt>
<dd>dict-alter</dd>
<dt>dict-intern</dt>
<dd>dict-alter</dd>
<dt>dict-update</dt>
<dd>dict-alter</dd>
<dt>dict-update/default</dt>
<dd>dict-update</dd>
<dt>dict-pop</dt>
<dd>dict-for-each</dd>
<dd>dict-delete-all</dd>
<dd>dict-empty?</dd>
<dt>dict-map</dt>
<dd>dict-keys</dd>
<dd>dict-ref</dd>
<dd>dict-replace</dd>
<dt>dict-filter</dt>
<dd>dict-keys</dd>
<dd>dict-ref</dd>
<dd>dict-delete-all</dd>
<dt>dict-remove</dt>
<dd>dict-filter</dd>
<dt>dict-count</dt>
<dd>dict-fold</dd>
<dt>dict-any</dt>
<dd>dict-for-each</dd>
<dt>dict-every</dt>
<dd>dict-for-each</dd>
<dt>dict-keys</dt>
<dd>dict-fold</dd>
<dt>dict-values</dt>
<dd>dict-fold</dd>
<dt>dict-entries</dt>
<dd>dict-fold</dd>
<dt>dict-fold</dt>
<dd>dict-for-each</dd>
<dt>dict-map->list</dt>
<dd>dict-fold</dd>
<dt>dict->alist</dt>
<dd>dict-map->list</dd>
<dt>dict-for-each<</dt>
<dd>dict-for-each</dd>
<dt>dict-for-each<=</dt>
<dd>dict-for-each</dd>
<dt>dict-for-each></dt>
<dd>dict-for-each</dd>
<dt>dict-for-each>=</dt>
<dd>dict-for-each</dd>
<dt>dict-for-each-in-open-interval</dt>
<dd>dict-for-each</dd>
<dt>dict-for-each-in-closed-interval</dt>
<dd>dict-for-each</dd>
<dt>dict-for-each-in-open-closed-interval</dt>
<dd>dict-for-each</dd>
<dt>dict-for-each-in-closed-open-interval</dt>
<dd>dict-for-each</dd>
<dt>make-dict-generator</dt>
<dd>dict-entries</dd>
<dt>dict-set-accumulator</dt>
<dd>dict-set</dd>
<dt>dict-adjoin-accumulator</dt>
<dd>dict-set</dd>
</dl>
<h2 id="acknowledgements">Acknowledgements</h2>
<p>Thanks to the participants on the mailing list.</p>
<h2 id="copyright">Copyright</h2>
<p>© 2021 John Cowan, Arvydas Silanskas.</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>
|
