You can edit this page using wiki syntax for markup.

Article contents:== srfi-146 [[toc:]] === Introduction This egg provides the reference implementation of [[https://srfi.schemers.org/srfi-146/srfi-146.html|SRFI-146]]. The {{(srfi 146)}} API uses the bundled {{rbtree}} implementation whereas the {{(srfi 146 hash)}} API relies on the [[/eggref/5/hash-trie|hash-trie]] egg. === Author Vasilij Schneidermann === Repository [[https://depp.brause.cc/srfi-146]] === Specification Mappings form a new type as if created by {{define-record-type}}. The effect of using record-type inspection or inheritance for the mapping type is unspecified. The two mapping types as exported from {{(srfi 146)}} and {{(srfi 146 hash)}} (see below) are mutually disjoint. This specification uses the notion of equality of comparators. The exact equality predicate is left implementation-dependent but is always at least as fine as {{equal?}} (and not finer than {{eq?}}). It is an error for any procedure defined in this SRFI to be invoked on mappings with distinct comparators, except if noted otherwise. It is an error to mutate any key while it is contained in an association in a mapping. It is an error to add any association to a mapping whose key does not satisfy the type test predicate of the comparator. It is an error to apply any procedures defined in this SRFI whose names end in {{!}} to a mapping while iterating over it. When part of an R7RS implementation, the library {{(srfi 146)}} should export exactly those identifiers that are described in this specification with the appropriate bindings. Should this SRFI become an essential part of a future Scheme system based on R7RS (''e.g.'' R7RS-large), the library's name would become {{(scheme mapping)}}. === Linear update The procedures of this SRFI, like those of SRFI 113, by default, are "pure functional" — they do not alter their parameters. However, this SRFI also defines "linear-update" procedures, all of whose names end in {{!}}. They have hybrid pure-functional/side-effecting semantics: they are allowed, but not required, to side-effect one of their parameters in order to construct their result. An implementation may legally implement these procedures as pure, side-effect-free functions, or it may implement them using side effects, depending upon the details of what is the most efficient or simple to implement in terms of the underlying representation. It is an error to reference a (mapping) parameter after a linear-update procedure has been invoked. For example, this is not guaranteed to work: <enscript highlight="scheme"> (let* ((mapping1 (mapping (make-default-comparator) 'a 1 'b 2 'c 3)) ; mapping1 = {a↦1,b↦2,c↦3}. (mapping2 (mapping-set! mapping1 'd 4))) ; mapping2 = {a↦1,b↦2,c↦3,d↦4} mapping1) ; mapping1 = {a↦1,b↦2,c↦3} or mapping1 = {a↦1,b↦2,c↦3;d↦4} ??? </enscript> However, this is well-defined: <enscript highlight="scheme"> (let ((mapping1 (mapping (make-default-comparator) 'a 1 'b 2 'c 3))) (mapping-set! mapping1 'd 4)) ; ⇒ {a↦1,b↦2,c↦3;d↦4} </enscript> So clients of these procedures write in a functional style, but must additionally be sure that, when the procedure is called, there are no other live pointers to the potentially-modified mapping (hence the term "linear update"). There are two benefits to this convention: * Implementations are free to provide the most efficient possible implementation, either functional or side-effecting. * 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). In practice, these procedures are most useful for efficiently constructing mappings in a side-effecting manner, in some limited local context, before passing the mapping outside the local construction scope to be used in a functional manner. Scheme provides no assistance in checking the linearity of the potentially side-effected parameters passed to these functions — there's no linear type checker or run-time mechanism for detecting violations. Note that if an implementation uses no side effects at all, it is allowed to return existing mappings rather than newly allocated ones, even where this SRFI explicitly says otherwise. For example, {{mapping-copy}} could be a no-op. === Comparator restrictions The library {{(srfi 146)}} described in this SRFI requires comparators to provide an ordering predicate. Any implementation shall also provide the library {{(srfi 146 hash)}} which implements essentially the same interface (see below) as {{(srfi 146)}} but requires comparators to provide a hash function instead of an ordering predicate, unless the equality predicate of the comparator is {{eq?}}, {{eqv?}}, {{equal?}}, {{string=?}}, or {{string-ci=?}}. The library {{(srfi 146 hash)}} exports exactly the same identifiers (up to a simple prefix-replacing textual substitution as described in the next paragraph), except for those bound to locations which make no sense when an ordering predicate is absent (e.g. {{mapping-split}}). Should {{(srfi 146)}} once become known as {{(scheme mapping)}}, it is recommended that the library {{(srfi 146 hash)}} receives the alternative name {{(scheme hashmap)}}. To make it possible for a program to easily import {{(srfi 146)}} and {{(srfi 146 hash)}} at the same time, the prefix {{mapping}} that prefixes the identifiers in {{(srfi 146)}} is substituted by {{hashmap}} in {{(srfi 146 hash)}}. For example, {{mapping}} becomes {{hashmap}}, {{mapping?}} becomes {{hashmap?}}, and {{mapping-ref}} becomes {{hashmap-ref}}. {{comparator?}} remains unchanged. For simplicity, the rest of this SRFI refers to the identifiers by their names in {{(srfi 146)}}. === API ==== Constructors <procedure>(mapping comparator arg ...)</procedure> Returns a newly allocated mapping. The {{comparator}} argument is a [[https://srfi.schemers.org/srfi-128/srfi-128.html|SRFI 128]] comparator, which is used to control and distinguish the keys of the mapping. The {{arg}}s alternate between keys and values and are used to initialize the mapping. In particular, the number of {{arg}}s has to be even. Earlier associations with equal keys take precedence over later arguments. <procedure>(mapping-unfold stop? mapper successor seed comparator)</procedure> Create a newly allocated mapping as if by {{mapping}} using {{comparator}}. If the result of applying the predicate {{stop?}} to {{seed}} is true, return the mapping. Otherwise, apply the procedure {{mapper}} to {{seed}}. {{Mapper}} returns two values which are added to the mapping as the key and the value, respectively. Then get a new seed by applying the procedure {{successor}} to {{seed}}, and repeat this algorithm. Associations earlier in the list take precedence over those that come later. ''Note that the choice of precedence in {{mapping}} and {{mapping-unfold}} is compatible with {{mapping-adjoin}} and {{alist->mapping}} detailed below and with {{alist->hash-table}} from SRFI 125, but different from the one in {{mapping-set}} from below.'' ==== Predicates <procedure>(mapping? obj)</procedure> Returns {{#t}} if {{obj}} is a mapping, and {{#f}} otherwise. <procedure>(mapping-contains? mapping key)</procedure> Returns {{#t}} if {{key}} is the key of an association of {{mapping}} and {{#f}} otherwise. <procedure>(mapping-empty? mapping)</procedure> Returns {{#t}} if {{mapping}} has no associations and {{#f}} otherwise. <procedure>(mapping-disjoint? mapping1 mapping2)</procedure> Returns {{#t}} if {{mapping1}} and {{mapping2}} have no keys in common and {{#f}} otherwise. ==== Accessors The following three procedures, given a key, return the corresponding value. <procedure>(mapping-ref mapping key failure success)</procedure> <procedure>(mapping-ref mapping key failure)</procedure> <procedure>(mapping-ref mapping key)</procedure> Extracts the value associated to {{key}} in the mapping {{mapping}}, invokes the procedure {{success}} in tail context on it, and returns its result; if {{success}} is not provided, then the value itself is returned. If {{key}} is not contained in {{mapping}} and {{failure}} is supplied, then {{failure}} is invoked in tail context on no arguments and its values are returned. Otherwise, it is an error. <procedure>(mapping-ref/default mapping key default)</procedure> Semantically equivalent to, but may be more efficient than, the following code: <enscript highlight="scheme"> (mapping-ref mapping key (lambda () default)) </enscript> <procedure>(mapping-key-comparator mapping)</procedure> Returns the comparator used to compare the keys of the mapping {{mapping}}. ==== Updaters <procedure>(mapping-adjoin mapping arg ...)</procedure> The {{mapping-adjoin}} procedure returns a newly allocated mapping that uses the same comparator as the mapping {{mapping}} and contains all the associations of {{mapping}}, and in addition new associations by processing the arguments from left to right. The {{arg}}s alternate between keys and values. Whenever there is a previous association for a key, the previous association prevails and the new association is skipped. It is an error to add an association to {{mapping}} whose key that does not return {{#t}} when passed to the type test procedure of the comparator. <procedure>(mapping-adjoin! mapping arg ...)</procedure> The {{mapping-adjoin!}} procedure is the same as {{mapping-adjoin}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-set mapping arg ...)</procedure> The {{mapping-set}} procedure returns a newly allocated mapping that uses the same comparator as the mapping {{mapping}} and contains all the associations of {{mapping}}, and in addition new associations by processing the arguments from left to right. The {{arg}}s alternate between keys and values. Whenever there is a previous association for a key, it is deleted. It is an error to add an association to {{mapping}} whose key that does not return {{#t}} when passed to the type test procedure of the comparator. <procedure>(mapping-set! mapping arg ...)</procedure> The {{mapping-set!}} procedure is the same as {{mapping-set}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-replace mapping key value)</procedure> The {{mapping-replace}} procedure returns a newly allocated mapping that uses the same comparator as the mapping {{mapping}} and contains all the associations of {{mapping}} except as follows: If {{key}} is equal (in the sense of {{mapping}}'s comparator) to an existing key of {{mapping}}, then the association for that key is omitted and replaced the association defined by the pair {{key}} and {{value}}. If there is no such key in {{mapping}}, then {{mapping}} is returned unchanged. <procedure>(mapping-replace! mapping key value)</procedure> The {{mapping-replace!}} procedure is the same as {{mapping-replace}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-delete mapping key ...)</procedure> <procedure>(mapping-delete! mapping key ...)</procedure> <procedure>(mapping-delete-all mapping key-list)</procedure> <procedure>(mapping-delete-all! mapping key-list)</procedure> The {{mapping-delete}} procedure returns a newly allocated mapping containing all the associations of the mapping {{mapping}} except for any whose keys are equal (in the sense of {{mapping}}'s comparator) to one or more of the {{key}}s. Any {{key}} that is not equal to some key of the mapping is ignored. The {{mapping-delete!}} procedure is the same as {{mapping-delete}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. The {{mapping-delete-all}} and {{mapping-delete-all!}} procedures are the same as {{mapping-delete}} and {{mapping-delete!}}, respectively, except that they accept a single argument which is a list of keys whose associations are to be deleted. <procedure>(mapping-intern mapping key failure)</procedure> Extracts the value associated to {{key}} in the mapping {{mapping}}, and returns {{mapping}} and the value as two values. If {{key}} is not contained in {{mapping}}, {{failure}} is invoked on no arguments. The procedure then returns two values, a newly allocated mapping that uses the same comparator as the {{mapping}} and contains all the associations of {{mapping}}, and in addition a new association mapping {{key}} to the result of invoking {{failure}}, and the result of invoking {{failure}}. <procedure>(mapping-intern! mapping key failure)</procedure> The {{mapping-intern!}} procedure is the same as {{mapping-intern}}, except that it is permitted to mutate and return the {{mapping}} argument as its first value rather than allocating a new mapping. <procedure>(mapping-update mapping key updater failure success)</procedure> <procedure>(mapping-update mapping key updater failure)</procedure> <procedure>(mapping-update mapping key updater)</procedure> Semantically equivalent to, but may be more efficient than, the following code <enscript highlight="scheme"> (mapping-set mapping key (updater (mapping-ref mapping key failure success))) </enscript> The obvious semantics hold when {{success}} (and {{failure}}) are omitted (see {{mapping-ref}}). <procedure>(mapping-update! mapping key updater failure success)</procedure> <procedure>(mapping-update! mapping key updater failure)</procedure> <procedure>(mapping-update! mapping key updater)</procedure> The {{mapping-update!}} procedure is the same as {{mapping-update}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-update/default mapping key updater default)</procedure> Semantically equivalent to, but may be more efficient than, the following code <enscript highlight="scheme"> (mapping-set mapping key (updater (mapping-ref/default mapping key default))) </enscript> <procedure>(mapping-update!/default mapping key updater default)</procedure> The {{mapping-update!/default}} procedure is the same as {{mapping-update/default}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-pop mapping failure)</procedure> <procedure>(mapping-pop mapping)</procedure> The {{mapping-pop}} procedure exported from {{(srfi 146)}} chooses the association with the least key from {{mapping}} and returns three values, a newly allocated mapping that uses the same comparator as {{mapping}} and contains all associations of {{mapping}} except the chosen one, and the key and the value of the chosen association. If {{mapping}} contains no association and {{failure}} is supplied, then {{failure}} is invoked in tail context on no arguments and its values returned. Otherwise, it is an error. The {{hashmap-pop}} procedure exported by {{(srfi 146 hash)}} is similar but chooses an arbitrary association. <procedure>(mapping-pop! mapping failure)</procedure> <procedure>(mapping-pop! mapping)</procedure> The {{mapping-pop!}} procedure is the same as {{mapping-pop}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-search mapping key failure success)</procedure> The mapping {{mapping}} is searched in order (that is in the order of the stored keys) for an association with key {{key}}. If it is not found, then the {{failure}} procedure is tail-called with two continuation arguments, {{insert}} and {{ignore}}, and is expected to tail-call one of them. If an association with key {{key}} is found, then the {{success}} procedure is tail-called with the matching key of {{mapping}}, the associated value, and two continuations, {{update}} and {{remove}}, and is expected to tail-call one of them. The {{hashmap-search}} procedure exported by {{(srfi 146 hash)}} searches in an arbitrary order. It is an error if the continuation arguments are invoked, but not in tail position in the {{failure}} and {{success}} procedures. It is also an error if the {{failure}} and {{success}} procedures return to their implicit continuation without invoking one of their continuation arguments. The effects of the continuations are as follows (where {{obj}} is any Scheme object): * 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}}. * Invoking {{(ignore obj)}} has no effects; in particular, no new mapping is allocated (but see below). * 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}}. * 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}}. In all cases, two values are returned: the possibly newly allocated {{mapping}} and {{obj}}. <procedure>(mapping-search! mapping key failure success)</procedure> The {{mapping-search!}} procedure is the same as {{mapping-search}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. ==== The whole mapping <procedure>(mapping-size mapping)</procedure> Returns the number of associations in {{mapping}} as an exact integer. <procedure>(mapping-find predicate mapping failure)</procedure> Returns the association with the least key of the mapping {{mapping}} consisting of a key and value as two values such that {{predicate}} returns a true value when invoked with key and value as arguments, or the result of tail-calling {{failure}} with no arguments if there is none. There are no guarantees how many times and with which keys and values {{predicate}} is invoked. The {{hashmap-find}} procedure exported by {{(srfi 146 hash)}} searches in arbitrary order. <procedure>(mapping-count predicate mapping)</procedure> Returns the number of associations of the mapping {{mapping}} that satisfy {{predicate}} (in the sense of {{mapping-find}}) as an exact integer. There are no guarantees how many times and with which keys and values {{predicate}} is invoked. <procedure>(mapping-any? predicate mapping)</procedure> Returns {{#t}} if any association of the mapping {{mapping}} satisfies {{predicate}} (in the sense of {{mapping-find}}), or {{#f}} otherwise. There are no guarantees how many times and with which keys and values {{predicate}} is invoked. <procedure>(mapping-every? predicate mapping)</procedure> Returns {{#t}} if every association of the mapping {{mapping}} satisfies {{predicate}} (in the sense of {{mapping-find}}), or {{#f}} otherwise. There are no guarantees how many times and with which keys and values {{predicate}} is invoked. <procedure>(mapping-keys mapping)</procedure> Returns a newly allocated list of all the keys in increasing order in the mapping {{mapping}}. If {{hashmap-keys}} is imported from {{(srfi 146 hash)}}, the list is returned in arbitrary order. <procedure>(mapping-values mapping)</procedure> Returns a newly allocated list of all the values in increasing order of the keys in the mapping {{mapping}}. If {{hashmap-values}} is imported from {{(srfi 146 hash)}}, the list is returned in arbitrary order. <procedure>(mapping-entries mapping)</procedure> Returns two values, a newly allocated list of all the keys in the mapping {{mapping}}, and a newly allocated list of all the values in the mapping {{mapping}} in increasing order of the keys. If {{hashmap-entries}} is imported from {{(srfi 146 hash)}}, the lists are returned in arbitrary, but consistent order. ==== Mapping and folding <procedure>(mapping-map proc comparator mapping)</procedure> Applies {{proc}}, which returns two values, on two arguments, the key and value of each association of {{mapping}} in increasing order of the keys and returns a newly allocated mapping that uses the comparator {{comparator}}, and which contains the results of the applications inserted as keys and values. Note that this is more akin to {{set-mapping}} from SRFI 113 than to {{hash-table-mapping}} from SRFI 125. For example: <enscript highlight="scheme"> (mapping-map (proc (key value) (values (symbol->string key) value)) (make-default-comparator) (mapping (make-default-comparator) 'foo 1 'bar 2 'baz 3)) ; ⇒ (mapping (make-default-comparator) "foo" 1 "bar" 2 "baz" 3) </enscript> Note that, when {{proc}} defines a mapping that is not 1:1 between the keys, some of the mapped objects may be equivalent in the sense of the {{comparator}}'s equality predicate, and in this case duplicate associations are omitted as in the mapping constructor. It is unpredictable which one will be preserved in the result. If {{hashmap-map}} is imported from {{(srfi 146 hash)}}, the associations are mapped in arbitrary order. <procedure>(mapping-for-each proc mapping)</procedure> Invokes {{proc}} for every association in the mapping {{mapping}} in increasing order of the keys, discarding the returned values, with two arguments: the key of the association and the value of the association. Returns an unspecified value. If {{hashmap-for-each}} is imported from {{(srfi 146 hash)}}, the associations are processed in arbitrary order. <procedure>(mapping-fold proc nil mapping)</procedure> Invokes {{proc}} for each association of the mapping {{mapping}} in increasing order of the keys 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, {{nil}} is used as the third argument. Returns the result of the last invocation, or {{nil}} if there was no invocation. If {{hashmap-fold}} is imported from {{(srfi 146 hash)}}, the associations are accumulated in arbitrary order. <procedure>(mapping-map->list proc mapping)</procedure> Calls {{proc}} for every association in increasing order of the keys in the mapping {{mapping}} with two arguments: the key of the association and the value of the association. The values returned by the invocations of {{proc}} are accumulated into a list, which is returned. If {{hashmap->list}} is imported from {{(srfi 146 hash)}}, the associations are processed in arbitrary order. <procedure>(mapping-filter predicate mapping)</procedure> Returns a newly allocated mapping with the same comparator as the mapping {{mapping}}, containing just the associations of {{mapping}} that satisfy {{predicate}} (in the sense of {{mapping-find}}). <procedure>(mapping-filter! predicate mapping)</procedure> A linear update procedure that returns a mapping containing just the associations of {{mapping}} that satisfy {{predicate}}. <procedure>(mapping-remove predicate mapping)</procedure> Returns a newly allocated mapping with the same comparator as the mapping {{mapping}}, containing just the associations of {{mapping}} that do not satisfy {{predicate}} (in the sense of {{mapping-find}}). <procedure>(mapping-remove! predicate mapping)</procedure> A linear update procedure that returns a mapping containing just the associations of {{mapping}} that do not satisfy {{predicate}}. <procedure>(mapping-partition predicate mapping)</procedure> Returns two values: a newly allocated mapping with the same comparator as the mapping {{mapping}} that contains just the associations of {{mapping}} that satisfy {{predicate}} (in the sense of {{mapping-find}}), and another newly allocated mapping, also with the same comparator, that contains just the associations of {{mapping}} that do not satisfy {{predicate}}. <procedure>(mapping-partition! predicate mapping)</procedure> A linear update procedure that returns two mappings containing the associations of {{mapping}} that do and do not, respectively, satisfy {{predicate}}. ==== Copying and conversion <procedure>(mapping-copy mapping)</procedure> Returns a newly allocated mapping containing the associations of the mapping {{mapping}}, and using the same comparator. <procedure>(mapping->alist mapping)</procedure> Returns a newly allocated association list containing the associations of the {{mapping}} in increasing order of the keys. Each association in the list is a pair whose car is the key and whose cdr is the associated value. If {{hashmap->alist}} is imported from {{(srfi 146 hash)}}, the association list is in arbitrary order. <procedure>(alist->mapping comparator alist)</procedure> Returns a newly allocated mapping, created as if by {{mapping}} using the comparator {{comparator}}, that contains the associations in the list, which consist of a pair whose car is the key and whose cdr is the value. Associations earlier in the list take precedence over those that come later. <procedure>(alist->mapping! mapping alist)</procedure> A linear update procedure that returns a mapping that contains the associations of both {{mapping}} and {{alist}}. Associations in the mapping and those earlier in the list take precedence over those that come later. ==== Submappings All predicates in this subsection take a {{comparator}} argument, which is a comparator used to compare the values of the associations stored in the mappings. Associations in the mappings are equal if their keys are equal with mappings' key comparator and their values are equal with the given comparator. Two mappings are equal if and only if their associations are equal, respectively. Note: None of these five predicates produces a total order on mappings. In particular, {{mapping=?}}, {{mapping<?}}, and {{mapping>?}} do not obey the trichotomy law. <procedure>(mapping=? comparator mapping1 mapping2 ...)</procedure> Returns {{#t}} if each mapping {{mapping}} contains the same associations, and {{#f}} otherwise. Furthermore, it is explicitly not an error if {{mapping=?}} is invoked on mappings that do not share the same (key) comparator. In that case, {{#f}} is returned. <procedure>(mapping<? comparator mapping1 mapping2 ...)</procedure> Returns {{#t}} if the set of associations of each mapping {{mapping}} other than the last is a proper subset of the following {{mapping}}, and {{#f}} otherwise. <procedure>(mapping>? comparator mapping1 mapping2 ...)</procedure> Returns {{#t}} if the set of associations of each mapping {{mapping}} other than the last is a proper superset of the following {{mapping}}, and {{#f}} otherwise. <procedure>(mapping<=? comparator mapping1 mapping2 ...)</procedure> Returns {{#t}} if the set of associations of each mapping {{mapping}} other than the last is a subset of the following {{mapping}}, and {{#f}} otherwise. <procedure>(mapping>=? comparator mapping1 mapping2 ...)</procedure> Returns {{#t}} if the set of associations of each mapping {{mapping}} other than the last is a superset of the following {{mapping}}, and {{#f}} otherwise. ==== Set theory operations <procedure>(mapping-union mapping1 mapping2 ...)</procedure> <procedure>(mapping-intersection mapping1 mapping2 ...)</procedure> <procedure>(mapping-difference mapping1 mapping2 ...)</procedure> <procedure>(mapping-xor mapping1 mapping2)</procedure> Return a newly allocated mapping whose set of associations is the union, intersection, asymmetric difference, or symmetric difference of the sets of associations of the mappings {{mapping}}s. Asymmetric difference is extended to more than two mappings by taking the difference between the first mapping and the union of the others. Symmetric difference is not extended beyond two mappings. When comparing associations, only the keys are compared. In case of duplicate keys (in the sense of the {{mapping}}s comparators), associations in the result mapping are drawn from the first mapping in which they appear. <procedure>(mapping-union! mapping1 mapping2 ...)</procedure> <procedure>(mapping-intersection! mapping1 mapping2 ...)</procedure> <procedure>(mapping-difference! mapping1 mapping2 ...)</procedure> <procedure>(mapping-xor! mapping1 mapping2)</procedure> These procedures are the linear update analogs of the corresponding pure functional procedures above. ==== Additional procedures for mappings with ordered keys The following procedures are only exported by the {{(srfi 146)}} library and not by {{(srfi 146 hash)}}: <procedure>(mapping/ordered comparator arg ...)</procedure> <procedure>(mapping-unfold/ordered stop? mapper successor seed comparator)</procedure> These are the same as {{mapping}} and {{mapping-unfold}}, except that it is an error if the keys are not in order, and they may be more efficient. <procedure>(alist->mapping/ordered comparator alist)</procedure> <procedure>(alist->mapping/ordered! mapping alist)</procedure> These are the same as {{alist->mapping}} and {{alist->mapping!}}, except that it is an error if the keys are not in order, and they may be more efficient. <procedure>(mapping-min-key mapping)</procedure> <procedure>(mapping-max-key mapping)</procedure> Returns the least/greatest key contained in the mapping {{mapping}}. It is an error for {{mapping}} to be empty. <procedure>(mapping-min-value mapping)</procedure> <procedure>(mapping-max-value mapping)</procedure> Returns the value associated with the least/greatest key contained in the mapping {{mapping}}. It is an error for {{mapping}} to be empty. ''Note: It does not make sense to ask for the least/greatest value contained in {{mapping}} because the values have no specified order.'' <procedure>(mapping-min-entry mapping)</procedure> <procedure>(mapping-max-entry mapping)</procedure> Returns the entry associated with the least/greatest key contained in the mapping {{mapping}} as two values, the key and its associated value. It is an error for {{mapping}} to be empty. <procedure>(mapping-key-predecessor mapping obj failure)</procedure> <procedure>(mapping-key-successor mapping obj failure)</procedure> Returns the key contained in the mapping {{mapping}} that immediately precedes/succeeds {{obj}} in the mapping's order of keys. If no such key is contained in {{mapping}} (because {{obj}} is the minimum/maximum key, or because {{mapping}} is empty), returns the result of tail-calling the thunk {{failure}}. <procedure>(mapping-range= mapping obj)</procedure> <procedure>(mapping-range< mapping obj)</procedure> <procedure>(mapping-range> mapping obj)</procedure> <procedure>(mapping-range<= mapping obj)</procedure> <procedure>(mapping-range>= mapping obj)</procedure> Returns a mapping containing only the associations of the {{mapping}} whose keys are equal to, less than, greater than, less than or equal to, or greater than or equal to {{obj}}. ''Note: Note that since keys in mappings are unique, {{mapping-range=}} returns a mapping with at most one association.'' <procedure>(mapping-range=! mapping obj)</procedure> <procedure>(mapping-range<! mapping obj)</procedure> <procedure>(mapping-range>! mapping obj)</procedure> <procedure>(mapping-range<=! mapping obj)</procedure> <procedure>(mapping-range>=! mapping obj)</procedure> Linear update procedures returning a mapping containing only the associations of the {{mapping}} whose keys are equal to, less than, greater than, less than or equal to, or greater than or equal to {{obj}}. <procedure>(mapping-split mapping obj)</procedure> Returns five values, equivalent to the results of invoking {{(mapping-range< mapping obj)}}, {{(mapping-range<= mapping obj)}}, {{(mapping-range= mapping obj)}}, {{(mapping-range>= mapping obj)}}, and {{(mapping-range> mapping obj)}}, but may be more efficient. <procedure>(mapping-split! mapping obj)</procedure> The {{mapping-split!}} procedure is the same as {{mapping-split}}, except that it is permitted to mutate and return the {{mapping}} rather than allocating a new mapping. <procedure>(mapping-catenate comparator mapping1 key value mapping2)</procedure> Returns a newly allocated mapping using the comparator {{comparator}} whose set of associations is the union of the sets of associations of the mapping {{mapping}}, the association mapping {{key}} to {{value}}, and the associations of {{mapping2}}. It is an error if the keys contained in {{mapping1}} in their natural order, the key {{key}}, and the keys contained in {{mapping2}} in their natural order (in that order) do not form a strictly monotone sequence with respect to the ordering of {{comparator}}. <procedure>(mapping-catenate! mapping1 key value mapping2)</procedure> The {{mapping-catenate!}} procedure is the same as {{mapping-catenate}}, except that it is permitted to mutate and return one of the {{mapping}}s rather than allocating a new mapping. <procedure>(mapping-map/monotone proc comparator mapping)</procedure> Equivalent to {{(mapping-map proc comparator mapping)}}, but it is an error if {{proc}} does not induce a strictly monotone mapping between the keys with respect to the ordering of the comparator of {{mapping}} and the ordering of {{comparator}}. Maybe be implemented more efficiently than {{mapping-map}}. <procedure>(mapping-map/monotone! proc comparator mapping)</procedure> The {{mapping-map/monotone!}} procedure is the same as {{mapping-map/monotone}}, except that it is permitted to mutate and return the {{mapping}} argument rather than allocating a new mapping. <procedure>(mapping-fold/reverse proc nil mapping)</procedure> Equivalent to {{(mapping-fold proc nil mapping)}} except that the associations are processed in reverse order with respect to the natural ordering of the keys. ==== Comparators <procedure>(comparator? obj)</procedure> Type predicate for comparators as exported by {{(srfi 128)}}. ''Rationale:'' The reason why {{comparator?}} is reexported from {{(srfi 128)}} is that it helps to detect if an implementation of the R7RS module system is broken in the sense that it does not allow interdependent libraries. If a program's imports are {{(import (srfi 128) (srfi 146))}}, it would be an error (principally detectable at expansion time) if the Scheme system loaded {{(srfi 128)}} twice, once for importing into the program, and once for importing into {{(srfi 146)}}. Namely, in that case the main program would import {{comparator?}} with two different bindings, and it would be impossible to invoke any procedure of {{(srfi 146)}} with a comparator created in the top-level program. If {{(srfi 146)}} didn't export {{comparator?}}, multiple loadings of {{(srfi 128)}} would not be detected early; only when a {{(srfi 146)}} procedure is invoked with a comparator created in the top-level program. One may view exporting {{comparator?}} as a hack only necessary because the R7RS library system fails to say anything about interdependent libraries (although it is usually assumed that interdependent libraries are possible); one can, however, also make independent sense out of it: By exporting {{comparator?}}, this specification declares or announces the actual type of comparators, on which its procedures depend. <procedure>(make-mapping-comparator comparator)</procedure> Returns a comparator for mappings that is compatible with the equality predicate {{(mapping=? comparator mapping1 mapping2)}}. If {{make-mapping-comparator}} is imported from {{(srfi 146)}}, it provides a (partial) ordering predicate that is applicable to pairs of mappings with the same (key) comparator. If {{(make-hashmap-comparator)}} is imported from {{(srfi 146 hash)}}, it provides an implementation-dependent hash function. If {{make-mapping-comparator}} is imported from {{(srfi 146)}}, the lexicographic ordering with respect to the keys (and, in case a tiebreak is necessary, with respect to the ordering of the values) is used for mappings sharing a comparator. The existence of comparators returned by {{make-mapping-comparator}} allows mappings whose keys are mappings themselves, and it allows to compare mappings whose values are mappings. The following comparator is used to compare mappings when {{(make-default-comparator)}} from SRFI 128 is invoked: {{mapping-comparator}} {{mapping-comparator}} is constructed by invoking {{make-mapping-comparator}} on {{(make-default-comparator)}}. === Examples <enscript highlight="scheme"> (import scheme) (import (srfi 128)) (import (srfi 146)) (import (srfi 146 hash)) (define comparator (make-default-comparator)) (define m (mapping comparator 'c 3 'e 5)) (set! m (mapping-set m 'b 2)) (set! m (mapping-set m 'd 4)) (set! m (mapping-set m 'a 1)) (mapping-for-each (lambda (k v) (print (list k v))) m) ;; (a 1) ;; (b 2) ;; (c 3) ;; (d 4) ;; (e 5) (define ht (hashmap comparator 'c 3 'e 5)) (set! ht (hashmap-set ht 'b 2)) (set! ht (hashmap-set ht 'd 4)) (set! ht (hashmap-set ht 'a 1)) (hashmap-for-each (lambda (k v) (print (list k v))) ht) ;; (e 5) ;; (d 4) ;; (c 3) ;; (b 2) ;; (a 1) </enscript> === License Copyright (c) 2020, Vasilij Schneidermann Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. === Version history ==== 0.1 * Initial release Description of your changes:

I would like to authenticate

Spam control

What do you get when you add 1 to 0?