source: project/wiki/eggref/5/srfi-146 @ 39199

Last change on this file since 39199 was 39199, checked in by wasamasa, 3 months ago

srfi-146: Release v0.1

File size: 37.7 KB
Line 
1== srfi-146
2
3[[toc:]]
4
5=== Introduction
6
7This egg provides the reference implementation of
8[[https://srfi.schemers.org/srfi-146/srfi-146.html|SRFI-146]].  The
9{{(srfi 146)}} API uses the bundled {{rbtree}} implementation whereas
10the {{(srfi 146 hash)}} API relies on the
11[[/eggref/5/hash-trie|hash-trie]] egg.
12
13=== Author
14
15Vasilij Schneidermann
16
17=== Repository
18
19[[https://depp.brause.cc/srfi-146]]
20
21=== Specification
22
23Mappings form a new type as if created by {{define-record-type}}.  The
24effect of using record-type inspection or inheritance for the mapping
25type is unspecified.
26
27The two mapping types as exported from {{(srfi 146)}} and {{(srfi 146
28hash)}} (see below) are mutually disjoint.
29
30This specification uses the notion of equality of comparators.  The
31exact equality predicate is left implementation-dependent but is
32always at least as fine as {{equal?}} (and not finer than {{eq?}}).
33
34It is an error for any procedure defined in this SRFI to be invoked on
35mappings with distinct comparators, except if noted otherwise.
36
37It is an error to mutate any key while it is contained in an
38association in a mapping.
39
40It is an error to add any association to a mapping whose key does not
41satisfy the type test predicate of the comparator.
42
43It is an error to apply any procedures defined in this SRFI whose
44names end in {{!}} to a mapping while iterating over it.
45
46When part of an R7RS implementation, the library {{(srfi 146)}} should
47export exactly those identifiers that are described in this
48specification with the appropriate bindings.  Should this SRFI become
49an essential part of a future Scheme system based on R7RS (''e.g.''
50R7RS-large), the library's name would become {{(scheme mapping)}}.
51
52=== Linear update
53
54The procedures of this SRFI, like those of SRFI 113, by default, are
55"pure functional" — they do not alter their parameters.  However, this
56SRFI also defines "linear-update" procedures, all of whose names end
57in {{!}}.  They have hybrid pure-functional/side-effecting semantics:
58they are allowed, but not required, to side-effect one of their
59parameters in order to construct their result.  An implementation may
60legally implement these procedures as pure, side-effect-free
61functions, or it may implement them using side effects, depending upon
62the details of what is the most efficient or simple to implement in
63terms of the underlying representation.
64
65It is an error to reference a (mapping) parameter after a
66linear-update procedure has been invoked.  For example, this is not
67guaranteed to work:
68
69<enscript highlight="scheme">
70  (let* ((mapping1
71         (mapping (make-default-comparator) 'a 1 'b 2 'c 3)) ; mapping1 = {a↩1,b↩2,c↩3}.
72    (mapping2 (mapping-set! mapping1 'd 4))) ; mapping2 = {a↩1,b↩2,c↩3,d↩4}
73  mapping1) ; mapping1 = {a↩1,b↩2,c↩3} or mapping1 = {a↩1,b↩2,c↩3;d↩4} ???
74</enscript>
75
76However, this is well-defined:
77
78<enscript highlight="scheme">
79  (let ((mapping1 (mapping (make-default-comparator) 'a 1 'b 2 'c 3)))
80    (mapping-set! mapping1 'd 4)) ; ⇒ {a↩1,b↩2,c↩3;d↩4}
81</enscript>
82
83So clients of these procedures write in a functional style, but must
84additionally be sure that, when the procedure is called, there are no
85other live pointers to the potentially-modified mapping (hence the
86term "linear update").
87
88There are two benefits to this convention:
89
90* Implementations are free to provide the most efficient possible implementation, either functional or side-effecting.
91* Programmers may nonetheless continue to assume that mappings are purely functional data structures: they may be reliably shared without needing to be copied, uniquified, and so forth (as long as the mapping in question is not an argument of a "linear-update" procedure).
92
93In practice, these procedures are most useful for efficiently
94constructing mappings in a side-effecting manner, in some limited
95local context, before passing the mapping outside the local
96construction scope to be used in a functional manner.
97
98Scheme provides no assistance in checking the linearity of the
99potentially side-effected parameters passed to these functions —
100there's no linear type checker or run-time mechanism for detecting
101violations.
102
103Note that if an implementation uses no side effects at all, it is
104allowed to return existing mappings rather than newly allocated ones,
105even where this SRFI explicitly says otherwise.  For example,
106{{mapping-copy}} could be a no-op.
107
108=== Comparator restrictions
109
110The library {{(srfi 146)}} described in this SRFI requires comparators
111to provide an ordering predicate.  Any implementation shall also
112provide the library {{(srfi 146 hash)}} which implements essentially
113the same interface (see below) as {{(srfi 146)}} but requires
114comparators to provide a hash function instead of an ordering
115predicate, unless the equality predicate of the comparator is {{eq?}},
116{{eqv?}}, {{equal?}}, {{string=?}}, or {{string-ci=?}}.
117
118The library {{(srfi 146 hash)}} exports exactly the same identifiers
119(up to a simple prefix-replacing textual substitution as described in
120the next paragraph), except for those bound to locations which make no
121sense when an ordering predicate is absent (e.g. {{mapping-split}}).
122Should {{(srfi 146)}} once become known as {{(scheme mapping)}}, it is
123recommended that the library {{(srfi 146 hash)}} receives the
124alternative name {{(scheme hashmap)}}.
125
126To make it possible for a program to easily import {{(srfi 146)}} and
127{{(srfi 146 hash)}} at the same time, the prefix {{mapping}} that
128prefixes the identifiers in {{(srfi 146)}} is substituted by
129{{hashmap}} in {{(srfi 146 hash)}}.  For example, {{mapping}} becomes
130{{hashmap}}, {{mapping?}} becomes {{hashmap?}}, and {{mapping-ref}}
131becomes {{hashmap-ref}}. {{comparator?}} remains unchanged. For
132simplicity, the rest of this SRFI refers to the identifiers by their
133names in {{(srfi 146)}}.
134
135=== API
136
137==== Constructors
138
139<procedure>(mapping comparator arg ...)</procedure>
140
141Returns a newly allocated mapping.  The {{comparator}} argument is a
142[[https://srfi.schemers.org/srfi-128/srfi-128.html|SRFI 128]]
143comparator, which is used to control and distinguish the keys of the
144mapping.  The {{arg}}s alternate between keys and values and are used
145to initialize the mapping.  In particular, the number of {{arg}}s has
146to be even.  Earlier associations with equal keys take precedence over
147later arguments.
148
149<procedure>(mapping-unfold stop? mapper successor seed comparator)</procedure>
150
151Create a newly allocated mapping as if by {{mapping}} using
152{{comparator}}.  If the result of applying the predicate {{stop?}} to
153{{seed}} is true, return the mapping. Otherwise, apply the procedure
154{{mapper}} to {{seed}}. {{Mapper}} returns two values which are added
155to the mapping as the key and the value, respectively.  Then get a new
156seed by applying the procedure {{successor}} to {{seed}}, and repeat
157this algorithm.  Associations earlier in the list take precedence over
158those that come later.
159
160''Note that the choice of precedence in {{mapping}} and
161{{mapping-unfold}} is compatible with {{mapping-adjoin}} and
162{{alist->mapping}} detailed below and with {{alist->hash-table}}
163from SRFI 125, but different from the one in {{mapping-set}} from
164below.''
165
166==== Predicates
167
168<procedure>(mapping? obj)</procedure>
169
170Returns {{#t}} if {{obj}} is a mapping, and {{#f}} otherwise.
171
172<procedure>(mapping-contains? mapping key)</procedure>
173
174Returns {{#t}} if {{key}} is the key of an
175association of {{mapping}} and {{#f}} otherwise.
176
177<procedure>(mapping-empty? mapping)</procedure>
178
179Returns {{#t}} if {{mapping}} has no associations and {{#f}} otherwise.
180
181<procedure>(mapping-disjoint? mapping1 mapping2)</procedure>
182
183Returns {{#t}} if {{mapping1}} and {{mapping2}} have no keys in common
184and {{#f}} otherwise.
185
186==== Accessors
187
188The following three procedures, given a key, return the corresponding
189value.
190
191<procedure>(mapping-ref mapping key failure success)</procedure>
192<procedure>(mapping-ref mapping key failure)</procedure>
193<procedure>(mapping-ref mapping key)</procedure>
194
195Extracts the value associated to {{key}} in the mapping {{mapping}},
196invokes the procedure {{success}} in tail context on it, and returns
197its result; if {{success}} is not provided, then the value itself is
198returned.  If {{key}} is not contained in {{mapping}} and {{failure}}
199is supplied, then {{failure}} is invoked in tail context on no
200arguments and its values are returned.  Otherwise, it is an error.
201
202<procedure>(mapping-ref/default mapping key default)</procedure>
203
204Semantically equivalent to, but may be more efficient than, the
205following code:
206
207<enscript highlight="scheme">
208  (mapping-ref mapping key (lambda () default))
209</enscript>
210
211<procedure>(mapping-key-comparator mapping)</procedure>
212
213Returns the comparator used to compare the keys of the mapping
214{{mapping}}.
215
216==== Updaters
217
218<procedure>(mapping-adjoin mapping arg ...)</procedure>
219
220The {{mapping-adjoin}} procedure returns a newly allocated mapping
221that uses the same comparator as the mapping {{mapping}} and contains
222all the associations of {{mapping}}, and in addition new associations
223by processing the arguments from left to right. The {{arg}}s alternate
224between keys and values.  Whenever there is a previous association for
225a key, the previous association prevails and the new association is
226skipped. It is an error to add an association to {{mapping}} whose key
227that does not return {{#t}} when passed to the type test procedure of
228the comparator.
229
230<procedure>(mapping-adjoin! mapping arg ...)</procedure>
231
232The {{mapping-adjoin!}} procedure is the same as {{mapping-adjoin}},
233except that it is permitted to mutate and return the {{mapping}}
234argument rather than allocating a new mapping.
235
236<procedure>(mapping-set mapping arg ...)</procedure>
237
238The {{mapping-set}} procedure returns a newly allocated mapping that
239uses the same comparator as the mapping {{mapping}} and contains all
240the associations of {{mapping}}, and in addition new associations by
241processing the arguments from left to right. The {{arg}}s alternate
242between keys and values.  Whenever there is a previous association for
243a key, it is deleted.  It is an error to add an association to
244{{mapping}} whose key that does not return {{#t}} when passed to the
245type test procedure of the comparator.
246
247<procedure>(mapping-set! mapping arg ...)</procedure>
248
249The {{mapping-set!}} procedure is the same as {{mapping-set}}, except
250that it is permitted to mutate and return the {{mapping}} argument
251rather than allocating a new mapping.
252
253<procedure>(mapping-replace mapping key value)</procedure>
254
255The {{mapping-replace}} procedure returns a newly allocated mapping
256that uses the same comparator as the mapping {{mapping}} and contains
257all the associations of {{mapping}} except as follows: If {{key}} is
258equal (in the sense of {{mapping}}'s comparator) to an existing key of
259{{mapping}}, then the association for that key is omitted and replaced
260the association defined by the pair {{key}} and {{value}}. If there is
261no such key in {{mapping}}, then {{mapping}} is returned unchanged.
262
263<procedure>(mapping-replace! mapping key value)</procedure>
264
265The {{mapping-replace!}} procedure is the same as {{mapping-replace}},
266except that it is permitted to mutate and return the {{mapping}}
267argument rather than allocating a new mapping.
268
269<procedure>(mapping-delete mapping key ...)</procedure>
270
271<procedure>(mapping-delete! mapping key ...)</procedure>
272
273<procedure>(mapping-delete-all mapping key-list)</procedure>
274
275<procedure>(mapping-delete-all! mapping key-list)</procedure>
276
277The {{mapping-delete}} procedure returns a newly allocated mapping
278containing all the associations of the mapping {{mapping}} except for
279any whose keys are equal (in the sense of {{mapping}}'s comparator) to
280one or more of the {{key}}s.  Any {{key}} that is not equal to some
281key of the mapping is ignored.
282
283The {{mapping-delete!}} procedure is the same as {{mapping-delete}},
284except that it is permitted to mutate and return the {{mapping}}
285argument rather than allocating a new mapping.
286
287The {{mapping-delete-all}} and {{mapping-delete-all!}}  procedures are
288the same as {{mapping-delete}} and {{mapping-delete!}}, respectively,
289except that they accept a single argument which is a list of keys
290whose associations are to be deleted.
291
292<procedure>(mapping-intern mapping key failure)</procedure>
293
294Extracts the value associated to {{key}} in the mapping {{mapping}},
295and returns {{mapping}} and the value as two values.  If {{key}} is
296not contained in {{mapping}}, {{failure}} is invoked on no arguments.
297The procedure then returns two values, a newly allocated mapping that
298uses the same comparator as the {{mapping}} and contains all the
299associations of {{mapping}}, and in addition a new association mapping
300{{key}} to the result of invoking {{failure}}, and the result of
301invoking {{failure}}.
302
303<procedure>(mapping-intern! mapping key failure)</procedure>
304
305The {{mapping-intern!}} procedure is the same as {{mapping-intern}},
306except that it is permitted to mutate and return the {{mapping}}
307argument as its first value rather than allocating a new mapping.
308
309<procedure>(mapping-update mapping key updater failure success)</procedure>
310
311<procedure>(mapping-update mapping key updater failure)</procedure>
312
313<procedure>(mapping-update mapping key updater)</procedure>
314
315Semantically equivalent to, but may be more efficient than, the
316following code
317
318<enscript highlight="scheme">
319  (mapping-set mapping key (updater (mapping-ref mapping key failure success)))
320</enscript>
321
322The obvious semantics hold when {{success}} (and {{failure}}) are
323omitted (see {{mapping-ref}}).
324
325<procedure>(mapping-update! mapping key updater failure success)</procedure>
326
327<procedure>(mapping-update! mapping key updater failure)</procedure>
328
329<procedure>(mapping-update! mapping key updater)</procedure>
330
331The {{mapping-update!}} procedure is the same as {{mapping-update}},
332except that it is permitted to mutate and return the {{mapping}}
333argument rather than allocating a new mapping.
334
335<procedure>(mapping-update/default mapping key updater default)</procedure>
336
337Semantically equivalent to, but may be more efficient than, the
338following code
339
340<enscript highlight="scheme">
341  (mapping-set mapping key (updater (mapping-ref/default mapping key default)))
342</enscript>
343
344<procedure>(mapping-update!/default mapping key updater default)</procedure>
345
346The {{mapping-update!/default}} procedure is the same as
347{{mapping-update/default}}, except that it is permitted to mutate and
348return the {{mapping}} argument rather than allocating a new mapping.
349
350<procedure>(mapping-pop mapping failure)</procedure>
351<procedure>(mapping-pop mapping)</procedure>
352
353The {{mapping-pop}} procedure exported from {{(srfi 146)}} chooses the
354association with the least key from {{mapping}} and returns three
355values, a newly allocated mapping that uses the same comparator as
356{{mapping}} and contains all associations of {{mapping}} except the
357chosen one, and the key and the value of the chosen association. If
358{{mapping}} contains no association and {{failure}} is supplied, then
359{{failure}} is invoked in tail context on no arguments and its values
360returned.  Otherwise, it is an error.
361
362The {{hashmap-pop}} procedure exported by {{(srfi 146 hash)}} is
363similar but chooses an arbitrary association.
364
365<procedure>(mapping-pop! mapping failure)</procedure>
366<procedure>(mapping-pop! mapping)</procedure>
367
368The {{mapping-pop!}} procedure is the same as {{mapping-pop}}, except
369that it is permitted to mutate and return the {{mapping}} argument
370rather than allocating a new mapping.
371
372<procedure>(mapping-search mapping key failure success)</procedure>
373
374The mapping {{mapping}} is searched in order (that is in the order of
375the stored keys) for an association with key {{key}}.  If it is not
376found, then the {{failure}} procedure is tail-called with two
377continuation arguments, {{insert}} and {{ignore}}, and is expected to
378tail-call one of them.  If an association with key {{key}} is found,
379then the {{success}} procedure is tail-called with the matching key of
380{{mapping}}, the associated value, and two continuations, {{update}}
381and {{remove}}, and is expected to tail-call one of them.
382
383The {{hashmap-search}} procedure exported by {{(srfi 146 hash)}}
384searches in an arbitrary order.
385
386It is an error if the continuation arguments are invoked, but not in
387tail position in the {{failure}} and {{success}} procedures.  It is
388also an error if the {{failure}} and {{success}} procedures return to
389their implicit continuation without invoking one of their continuation
390arguments.
391
392The effects of the continuations are as follows (where {{obj}} is any
393Scheme object):
394
395
396* Invoking {{(insert value obj)}} causes a mapping to be newly allocated that uses the same comparator as the mapping {{mapping}} and contains all the associations of {{mapping}}, and in addition a new association mapping {{key}} to {{value}}.
397* Invoking {{(ignore obj)}} has no effects; in particular, no new mapping is allocated (but see below).
398* Invoking {{(update new-key new-value obj)}} causes a mapping to be newly allocated that uses the same comparator as the {{mapping}} and contains all the associations of {{mapping}}, except for the association with key {{key}}, which is replaced by a new association mapping {{new-key}} to {{new-value}}.
399* Invoking {{(remove obj)}} causes a mapping to be newly allocated that uses the same comparator as the {{mapping}} and contains all the associations of {{mapping}}, except for the association with key {{key}}.
400
401In all cases, two values are returned: the possibly newly allocated
402{{mapping}} and {{obj}}.
403
404<procedure>(mapping-search! mapping key failure success)</procedure>
405
406The {{mapping-search!}} procedure is the same as {{mapping-search}},
407except that it is permitted to mutate and return the {{mapping}}
408argument rather than allocating a new mapping.
409
410==== The whole mapping
411
412<procedure>(mapping-size mapping)</procedure>
413
414Returns the number of associations in {{mapping}} as an exact integer.
415
416<procedure>(mapping-find predicate mapping failure)</procedure>
417
418Returns the association with the least key of the mapping {{mapping}}
419consisting of a key and value as two values such that {{predicate}}
420returns a true value when invoked with key and value as arguments, or
421the result of tail-calling {{failure}} with no arguments if there is
422none.  There are no guarantees how many times and with which keys and
423values {{predicate}} is invoked.
424
425The {{hashmap-find}} procedure exported by {{(srfi 146 hash)}}
426searches in arbitrary order.
427
428<procedure>(mapping-count predicate mapping)</procedure>
429
430Returns the number of associations of the mapping {{mapping}} that
431satisfy {{predicate}} (in the sense of {{mapping-find}}) as an exact
432integer.  There are no guarantees how many times and with which keys
433and values {{predicate}} is invoked.
434
435<procedure>(mapping-any? predicate mapping)</procedure>
436
437Returns {{#t}} if any association of the mapping {{mapping}} satisfies
438{{predicate}} (in the sense of {{mapping-find}}), or {{#f}} otherwise.
439There are no guarantees how many times and with which keys and values
440{{predicate}} is invoked.
441
442<procedure>(mapping-every? predicate mapping)</procedure>
443
444Returns {{#t}} if every association of the mapping {{mapping}}
445satisfies {{predicate}} (in the sense of {{mapping-find}}), or {{#f}}
446otherwise.  There are no guarantees how many times and with which keys
447and values {{predicate}} is invoked.
448
449<procedure>(mapping-keys mapping)</procedure>
450
451Returns a newly allocated list of all the keys in increasing order in
452the mapping {{mapping}}.
453
454If {{hashmap-keys}} is imported from {{(srfi 146 hash)}}, the list is
455returned in arbitrary order.
456
457<procedure>(mapping-values mapping)</procedure>
458
459Returns a newly allocated list of all the values in increasing order
460of the keys in the mapping {{mapping}}.
461
462If {{hashmap-values}} is imported from {{(srfi 146 hash)}}, the list
463is returned in arbitrary order.
464
465<procedure>(mapping-entries mapping)</procedure>
466
467Returns two values, a newly allocated list of all the keys in the
468mapping {{mapping}}, and a newly allocated list of all the values in
469the mapping {{mapping}} in increasing order of the keys.
470
471If {{hashmap-entries}} is imported from {{(srfi 146 hash)}}, the lists
472are returned in arbitrary, but consistent order.
473
474==== Mapping and folding
475
476<procedure>(mapping-map proc comparator mapping)</procedure>
477
478Applies {{proc}}, which returns two values, on two arguments, the key
479and value of each association of {{mapping}} in increasing order of
480the keys and returns a newly allocated mapping that uses the
481comparator {{comparator}}, and which contains the results of the
482applications inserted as keys and values. Note that this is more akin
483to {{set-mapping}} from SRFI 113 than to {{hash-table-mapping}} from
484SRFI 125. For example:
485
486<enscript highlight="scheme">
487  (mapping-map (proc (key value)
488             (values (symbol->string key) value))
489           (make-default-comparator)
490           (mapping (make-default-comparator) 'foo 1 'bar 2 'baz 3))
491  ; ⇒ (mapping (make-default-comparator) "foo" 1 "bar" 2 "baz" 3)
492</enscript>
493
494Note that, when {{proc}} defines a mapping that is not 1:1 between the
495keys, some of the mapped objects may be equivalent in the sense of the
496{{comparator}}'s equality predicate, and in this case duplicate
497associations are omitted as in the mapping constructor.  It is
498unpredictable which one will be preserved in the result.
499
500If {{hashmap-map}} is imported from {{(srfi 146 hash)}}, the
501associations are mapped in arbitrary order.
502
503<procedure>(mapping-for-each proc mapping)</procedure>
504
505Invokes {{proc}} for every association in the mapping {{mapping}} in
506increasing order of the keys, discarding the returned values, with two
507arguments: the key of the association and the value of the
508association.  Returns an unspecified value.
509
510If {{hashmap-for-each}} is imported from {{(srfi 146 hash)}}, the
511associations are processed in arbitrary order.
512
513<procedure>(mapping-fold proc nil mapping)</procedure>
514
515Invokes {{proc}} for each association of the mapping {{mapping}} in
516increasing order of the keys with three arguments: the key of the
517association, the value of the association, and an accumulated result
518of the previous invocation.  For the first invocation, {{nil}} is used
519as the third argument.  Returns the result of the last invocation, or
520{{nil}} if there was no invocation.
521
522If {{hashmap-fold}} is imported from {{(srfi 146 hash)}}, the
523associations are accumulated in arbitrary order.
524
525<procedure>(mapping-map->list proc mapping)</procedure>
526
527Calls {{proc}} for every association in increasing order of the keys
528in the mapping {{mapping}} with two arguments: the key of the
529association and the value of the association.  The values returned by
530the invocations of {{proc}} are accumulated into a list, which is
531returned.
532
533If {{hashmap->list}} is imported from {{(srfi 146 hash)}}, the
534associations are processed in arbitrary order.
535
536<procedure>(mapping-filter predicate mapping)</procedure>
537
538Returns a newly allocated mapping with the same comparator as the
539mapping {{mapping}}, containing just the associations of {{mapping}}
540that satisfy {{predicate}} (in the sense of {{mapping-find}}).
541
542<procedure>(mapping-filter! predicate mapping)</procedure>
543
544A linear update procedure that returns a mapping containing just the
545associations of {{mapping}} that satisfy {{predicate}}.
546
547<procedure>(mapping-remove predicate mapping)</procedure>
548
549Returns a newly allocated mapping with the same comparator as the
550mapping {{mapping}}, containing just the associations of {{mapping}}
551that do not satisfy {{predicate}} (in the sense of {{mapping-find}}).
552
553<procedure>(mapping-remove! predicate mapping)</procedure>
554
555A linear update procedure that returns a mapping containing just the
556associations of {{mapping}} that do not satisfy {{predicate}}.
557
558<procedure>(mapping-partition predicate mapping)</procedure>
559
560Returns two values: a newly allocated mapping with the same comparator
561as the mapping {{mapping}} that contains just the associations of
562{{mapping}} that satisfy {{predicate}} (in the sense of
563{{mapping-find}}), and another newly allocated mapping, also with the
564same comparator, that contains just the associations of {{mapping}}
565that do not satisfy {{predicate}}.
566
567<procedure>(mapping-partition! predicate mapping)</procedure>
568
569A linear update procedure that returns two mappings containing the
570associations of {{mapping}} that do and do not, respectively, satisfy
571{{predicate}}.
572
573==== Copying and conversion
574
575<procedure>(mapping-copy mapping)</procedure>
576
577Returns a newly allocated mapping containing the associations of the
578mapping {{mapping}}, and using the same comparator.
579
580<procedure>(mapping->alist mapping)</procedure>
581
582Returns a newly allocated association list containing the associations
583of the {{mapping}} in increasing order of the keys. Each association
584in the list is a pair whose car is the key and whose cdr is the
585associated value.
586
587If {{hashmap->alist}} is imported from {{(srfi 146 hash)}}, the
588association list is in arbitrary order.
589
590<procedure>(alist->mapping comparator alist)</procedure>
591
592Returns a newly allocated mapping, created as if by {{mapping}} using
593the comparator {{comparator}}, that contains the associations in the
594list, which consist of a pair whose car is the key and whose cdr is
595the value.  Associations earlier in the list take precedence over
596those that come later.
597
598<procedure>(alist->mapping! mapping alist)</procedure>
599
600A linear update procedure that returns a mapping that contains the
601associations of both {{mapping}} and {{alist}}.  Associations in the
602mapping and those earlier in the list take precedence over those that
603come later.
604
605==== Submappings
606
607All predicates in this subsection take a {{comparator}} argument,
608which is a comparator used to compare the values of the associations
609stored in the mappings.  Associations in the mappings are equal if
610their keys are equal with mappings' key comparator and their values
611are equal with the given comparator.  Two mappings are equal if and
612only if their associations are equal, respectively.
613
614Note: None of these five predicates produces a total order on
615mappings.  In particular, {{mapping=?}}, {{mapping<?}}, and
616{{mapping>?}} do not obey the trichotomy law.
617
618<procedure>(mapping=? comparator mapping1 mapping2 ...)</procedure>
619
620Returns {{#t}} if each mapping {{mapping}} contains the same
621associations, and {{#f}} otherwise.
622
623Furthermore, it is explicitly not an error if {{mapping=?}} is invoked
624on mappings that do not share the same (key) comparator.  In that
625case, {{#f}} is returned.
626
627<procedure>(mapping<? comparator mapping1 mapping2 ...)</procedure>
628
629Returns {{#t}} if the set of associations of each mapping {{mapping}}
630other than the last is a proper subset of the following {{mapping}},
631and {{#f}} otherwise.
632
633<procedure>(mapping>? comparator mapping1 mapping2 ...)</procedure>
634
635Returns {{#t}} if the set of associations of each mapping {{mapping}}
636other than the last is a proper superset of the following {{mapping}},
637and {{#f}} otherwise.
638
639<procedure>(mapping<=? comparator mapping1 mapping2 ...)</procedure>
640
641Returns {{#t}} if the set of associations of each mapping {{mapping}}
642other than the last is a subset of the following {{mapping}}, and
643{{#f}} otherwise.
644
645<procedure>(mapping>=? comparator mapping1 mapping2 ...)</procedure>
646
647Returns {{#t}} if the set of associations of each mapping {{mapping}}
648other than the last is a superset of the following {{mapping}}, and
649{{#f}} otherwise.
650
651==== Set theory operations
652
653<procedure>(mapping-union mapping1 mapping2 ...)</procedure>
654
655<procedure>(mapping-intersection mapping1 mapping2 ...)</procedure>
656
657<procedure>(mapping-difference mapping1 mapping2 ...)</procedure>
658
659<procedure>(mapping-xor mapping1 mapping2)</procedure>
660
661Return a newly allocated mapping whose set of associations is the
662union, intersection, asymmetric difference, or symmetric difference of
663the sets of associations of the mappings {{mapping}}s.  Asymmetric
664difference is extended to more than two mappings by taking the
665difference between the first mapping and the union of the others.
666Symmetric difference is not extended beyond two mappings.  When
667comparing associations, only the keys are compared.  In case of
668duplicate keys (in the sense of the {{mapping}}s comparators),
669associations in the result mapping are drawn from the first mapping in
670which they appear.
671
672<procedure>(mapping-union! mapping1 mapping2 ...)</procedure>
673
674<procedure>(mapping-intersection! mapping1 mapping2 ...)</procedure>
675
676<procedure>(mapping-difference! mapping1 mapping2 ...)</procedure>
677
678<procedure>(mapping-xor! mapping1 mapping2)</procedure>
679
680These procedures are the linear update analogs of the corresponding
681pure functional procedures above.
682
683==== Additional procedures for mappings with ordered keys
684
685The following procedures are only exported by the {{(srfi 146)}}
686library and not by {{(srfi 146 hash)}}:
687
688<procedure>(mapping/ordered comparator arg ...)</procedure>
689
690<procedure>(mapping-unfold/ordered stop? mapper successor seed comparator)</procedure>
691
692These are the same as {{mapping}} and {{mapping-unfold}}, except that
693it is an error if the keys are not in order, and they may be more
694efficient.
695
696<procedure>(alist->mapping/ordered comparator alist)</procedure>
697
698<procedure>(alist->mapping/ordered! mapping alist)</procedure>
699
700These are the same as {{alist->mapping}} and {{alist->mapping!}},
701except that it is an error if the keys are not in order, and they may
702be more efficient.
703
704<procedure>(mapping-min-key mapping)</procedure>
705<procedure>(mapping-max-key mapping)</procedure>
706
707Returns the least/greatest key contained in the mapping {{mapping}}.
708It is an error for {{mapping}} to be empty.
709
710<procedure>(mapping-min-value mapping)</procedure>
711<procedure>(mapping-max-value mapping)</procedure>
712
713Returns the value associated with the least/greatest key contained in
714the mapping {{mapping}}.  It is an error for {{mapping}} to be empty.
715
716''Note: It does not make sense to ask for the least/greatest value
717contained in {{mapping}} because the values have no specified order.''
718
719<procedure>(mapping-min-entry mapping)</procedure>
720<procedure>(mapping-max-entry mapping)</procedure>
721
722Returns the entry associated with the least/greatest key contained in
723the mapping {{mapping}} as two values, the key and its associated
724value.  It is an error for {{mapping}} to be empty.
725
726<procedure>(mapping-key-predecessor mapping obj failure)</procedure>
727<procedure>(mapping-key-successor mapping obj failure)</procedure>
728
729Returns the key contained in the mapping {{mapping}} that immediately
730precedes/succeeds {{obj}} in the mapping's order of keys.  If no such
731key is contained in {{mapping}} (because {{obj}} is the
732minimum/maximum key, or because {{mapping}} is empty), returns the
733result of tail-calling the thunk {{failure}}.
734
735<procedure>(mapping-range= mapping obj)</procedure>
736<procedure>(mapping-range< mapping obj)</procedure>
737<procedure>(mapping-range> mapping obj)</procedure>
738<procedure>(mapping-range<= mapping obj)</procedure>
739<procedure>(mapping-range>= mapping obj)</procedure>
740
741Returns a mapping containing only the associations of the {{mapping}}
742whose keys are equal to, less than, greater than, less than or equal
743to, or greater than or equal to {{obj}}.
744
745''Note: Note that since keys in mappings are unique,
746{{mapping-range=}} returns a mapping with at most one association.''
747
748<procedure>(mapping-range=! mapping obj)</procedure>
749<procedure>(mapping-range<! mapping obj)</procedure>
750<procedure>(mapping-range>! mapping obj)</procedure>
751<procedure>(mapping-range<=! mapping obj)</procedure>
752<procedure>(mapping-range>=! mapping obj)</procedure>
753
754Linear update procedures returning a mapping containing only the
755associations of the {{mapping}} whose keys are equal to, less than,
756greater than, less than or equal to, or greater than or equal to
757{{obj}}.
758
759<procedure>(mapping-split mapping obj)</procedure>
760
761Returns five values, equivalent to the results of invoking
762{{(mapping-range< mapping obj)}}, {{(mapping-range<= mapping obj)}},
763{{(mapping-range= mapping obj)}}, {{(mapping-range>= mapping obj)}},
764and {{(mapping-range> mapping obj)}}, but may be more efficient.
765
766<procedure>(mapping-split! mapping obj)</procedure>
767
768The {{mapping-split!}} procedure is the same as {{mapping-split}},
769except that it is permitted to mutate and return the {{mapping}}
770rather than allocating a new mapping.
771
772<procedure>(mapping-catenate comparator mapping1 key value mapping2</procedure>
773
774Returns a newly allocated mapping using the comparator {{comparator}}
775whose set of associations is the union of the sets of associations of
776the mapping {{mapping}}, the association mapping {{key}} to {{value}},
777and the associations of {{mapping2}}.  It is an error if the keys
778contained in {{mapping1}} in their natural order, the key {{key}}, and
779the keys contained in {{mapping2}} in their natural order (in that
780order) do not form a strictly monotone sequence with respect to the
781ordering of {{comparator}}.
782
783<procedure>(mapping-catenate! mapping1 key value mapping2)</procedure>
784
785The {{mapping-catenate!}} procedure is the same as
786{{mapping-catenate}}, except that it is permitted to mutate and return
787one of the {{mapping}}s rather than allocating a new mapping.
788
789<procedure>(mapping-map/monotone proc comparator mapping)</procedure>
790
791Equivalent to {{(mapping-map proc comparator mapping)}}, but it is an
792error if {{proc}} does not induce a strictly monotone mapping between
793the keys with respect to the ordering of the comparator of {{mapping}}
794and the ordering of {{comparator}}.  Maybe be implemented more
795efficiently than {{mapping-map}}.
796
797<procedure>(mapping-map/monotone! proc comparator mapping)</procedure>
798
799The {{mapping-map/monotone!}} procedure is the same as
800{{mapping-map/monotone}}, except that it is permitted to mutate and
801return the {{mapping}} argument rather than allocating a new mapping.
802
803<procedure>(mapping-fold/reverse proc nil mapping)</procedure>
804
805Equivalent to {{(mapping-fold proc nil mapping)}} except that the
806associations are processed in reverse order with respect to the
807natural ordering of the keys.
808
809==== Comparators
810
811<procedure>(comparator? obj)</procedure>
812
813Type predicate for comparators as exported by {{(srfi 128)}}.
814
815''Rationale:'' The reason why {{comparator?}} is reexported from
816{{(srfi 128)}} is that it helps to detect if an implementation of the
817R7RS module system is broken in the sense that it does not allow
818interdependent libraries.  If a program's imports are {{(import (srfi
819128) (srfi 146))}}, it would be an error (principally detectable at
820expansion time) if the Scheme system loaded {{(srfi 128)}} twice, once
821for importing into the program, and once for importing into {{(srfi
822146)}}.  Namely, in that case the main program would import
823{{comparator?}} with two different bindings, and it would be
824impossible to invoke any procedure of {{(srfi 146)}} with a comparator
825created in the top-level program.
826
827If {{(srfi 146)}} didn't export {{comparator?}}, multiple loadings of
828{{(srfi 128)}} would not be detected early; only when a {{(srfi 146)}}
829procedure is invoked with a comparator created in the top-level
830program.
831
832One may view exporting {{comparator?}} as a hack only necessary
833because the R7RS library system fails to say anything about
834interdependent libraries (although it is usually assumed that
835interdependent libraries are possible); one can, however, also make
836independent sense out of it: By exporting {{comparator?}}, this
837specification declares or announces the actual type of comparators, on
838which its procedures depend.
839
840<procedure>(make-mapping-comparator comparator)</procedure>
841
842Returns a comparator for mappings that is compatible with the equality
843predicate {{(mapping=? comparator mapping1 mapping2)}}. If
844{{make-mapping-comparator}} is imported from {{(srfi 146)}}, it
845provides a (partial) ordering predicate that is applicable to pairs of
846mappings with the same (key) comparator. If
847{{(make-hashmap-comparator)}} is imported from {{(srfi 146 hash)}}, it
848provides an implementation-dependent hash function.
849
850If {{make-mapping-comparator}} is imported from {{(srfi 146)}}, the
851lexicographic ordering with respect to the keys (and, in case a
852tiebreak is necessary, with respect to the ordering of the values) is
853used for mappings sharing a comparator.
854
855The existence of comparators returned by {{make-mapping-comparator}}
856allows mappings whose keys are mappings themselves, and it allows to
857compare mappings whose values are mappings.
858
859The following comparator is used to compare mappings when
860{{(make-default-comparator)}} from SRFI 128 is invoked:
861
862{{mapping-comparator}}
863
864{{mapping-comparator}} is constructed by invoking
865{{make-mapping-comparator}} on {{(make-default-comparator)}}.
866
867=== Examples
868
869<enscript highlight="scheme">
870(import scheme)
871(import (srfi 128))
872(import (srfi 146))
873(import (srfi 146 hash))
874
875(define comparator (make-default-comparator))
876
877(define m (mapping comparator 'c 3 'e 5))
878(set! m (mapping-set m 'b 2))
879(set! m (mapping-set m 'd 4))
880(set! m (mapping-set m 'a 1))
881(mapping-for-each (lambda (k v) (print (list k v))) m)
882;; (a 1)
883;; (b 2)
884;; (c 3)
885;; (d 4)
886;; (e 5)
887
888(define ht (hashmap comparator 'c 3 'e 5))
889(set! ht (hashmap-set ht 'b 2))
890(set! ht (hashmap-set ht 'd 4))
891(set! ht (hashmap-set ht 'a 1))
892(hashmap-for-each (lambda (k v) (print (list k v))) ht)
893;; (e 5)
894;; (d 4)
895;; (c 3)
896;; (b 2)
897;; (a 1)
898
899</enscript>
900
901=== License
902
903 Copyright (c) 2020, Vasilij Schneidermann
904 
905 Permission is hereby granted, free of charge, to any person obtaining a copy
906 of this software and associated documentation files (the "Software"), to deal
907 in the Software without restriction, including without limitation the rights
908 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
909 copies of the Software, and to permit persons to whom the Software is
910 furnished to do so, subject to the following conditions:
911 
912 The above copyright notice and this permission notice shall be included in
913 all copies or substantial portions of the Software.
914 
915 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
916 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
917 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
918 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
919 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
920 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
921 THE SOFTWARE.
922
923=== Version history
924
925==== 0.1
926
927* Initial release
Note: See TracBrowser for help on using the repository browser.