diff options
| author |  John Cowan
| 2021-07-26 18:46:38 -0400 |
|---|---|---|
| committer | John Cowan
| 2021-07-26 18:46:38 -0400 |
| commit | 5c8bfbcf5a93c444d54eb19b07d2affcd9805cce (patch) | |
| tree | 0c3c08e3d7c1970b7d60fe2f0ff2d6d555c0ead7 /srfi-225.html | |
| parent | exceptions (diff) | |
paired mutators
Diffstat (limited to 'srfi-225.html')
| -rw-r--r-- | srfi-225.html | 111 |
1 files changed, 68 insertions, 43 deletions
diff --git a/srfi-225.html b/srfi-225.html index 26df762..1a0ffff 100644 --- a/srfi-225.html +++ b/srfi-225.html @@ -32,24 +32,21 @@ of the object is. Such an object is called a <em>dictionary</em> in this SRFI.< <h2 id="issues">Issues</h2> -<p>1) Consider adding <code>dict-map</code>, -<code>dict-filter</code>, <code>dict-remove</code>, -and <code>dict-search</code>. -Currently they do not exist -because SRFI 125 doesn't have them, as there is no way to create a hash table -similar to an existing hash table.</p> +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 persistent ordered and hashed mappings from SRFI 146 and ordered 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 . DTDs are of an unspecified type.</p> -<p>This in turn requires that the DTD provides a predicate that can recognize its dictionaries, plus at least these primitive operations: determine a dictionary’s current size; reference, update, or insert an element of the dictionary depending on its current contents; map over all the elements with a function mapping each old value to a new one; filter the elements based on their keys or values; and process all the elements using a procedure invoked for its side effects.</p> +<p>This in turn requires that the DTD provides a predicate that can recognize its dictionaries, plus at least these primitive operations: create an empty dictionary from a comparator; determine a dictionary’s current size; reference, update, or insert an element of the dictionary depending on its current contents; map over all the elements with a function mapping each old value to a new one; filter the elements based on their keys or values; and process all the elements using a procedure invoked for its side effects.</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.</p> <p>Note that dictionaries must still be constructed using type-specific constructors, as the required and optional arguments differ in each case.</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>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.</p> +<p>A <em>dictionary</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 find if 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 <i>similar</i> 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="lists-as-dictionaries">Lists as dictionaries</h3> <p>Lists are supported as dictionaries using the specification in this section. If two keys are the same (in the sense of the specified equality predicate), then all but the first are treated as if they did not exist.</p> <p>If <code>plist-dtd</code> (see below) is used with a list, then the list is assumed to be a property list, alternating symbol keys with values. Mutation operations actually mutate the property list whenever possible. The equality predicate of this type of dictionary is <code>eq?</code>.</p> @@ -62,7 +59,12 @@ similar to an existing hash table.</p> (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 the <code>dictionary?</code> procedure that was used to make the DTD on <em>dictionary</em> returns <code>#f</code>.</p> <h3 id="predicates">Predicates</h3> +<p>The <em>dtd</em> argument is not discussed in the individual procedure descriptions below, but it is an error if invoking the <code>dictionary?</code> procedure that was used to make the DTD on <em>dictionary</em> returns <code>#f</code>.</p> +<h3 id="constructor">Constructor</h3> +<p><code>(make-dict</code> <em>dtd comparator obj</em> ...<code>)</code></p> +<p>Returns an empty dictionary of the type described by the DTD using <em>comparator</em> to specify to specify the dictionary's equality predicate and its ordering predicate and/or hash function.</p> +<p>The meaning of the other arguments depends on the type of dictionary being created. However, implementations which support the ability to specify the initial capacity of a hash table should interpret a non-negative exact integer as the specification of that capacity. In addition, if the symbols <code>thread-safe</code>, <code>weak-keys</code>, <code>ephemeral-keys</code>, <code>weak-values</code>, or <code>ephemeral-values</code> are present, implementations should create thread-safe hash tables, hash tables with weak keys or ephemeral keys, or hash tables with weak or ephemeral values respectively. Implementations are free to use ephemeral keys or values when weak keys or values respectively have been requested.</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 some registered predicate, and <code>#f</code> otherwise.</p> <blockquote><pre>(define aed dict (list '(1 . 2) '(3 . 4) '(5 . 6))) @@ -85,58 +87,72 @@ Consequently, previous examples don't affect later ones. <blockquote><pre>(dict-ref/default aed dict 1 #f) => 1 (dict-ref/default aed dict 1 #f) => #f</pre></blockquote> <h3 id="mutation">Mutation</h3> -<p>All these procedures are linear-update: they may return either a new dictionary object (which may or may not share storage with the <em>dictionary</em> argument), or the same dictionary object, mutated. In either case, it is an error to access the dictionary later through any other reference to it, as that reference may have been invalidated.</p> -<p><code>(dict-set!</code> <em>dtd dictionary obj</em> …<code>)</code></p> +<p>All these procedures exist in pairs, with and without a final <code>!</code>. The ones without <code>!</code> are functional: they never side-effect their arguments, but may copy them. The ones with <code>!</code> are linear-update: they may return either a new dictionary object (which may or may not share storage with the <em>dictionary</em> argument), or the same dictionary object, mutated; in either case it is an error to access the dictionary later through any other reference to it, as that reference may have been invalidated.</p> +<p><code>(dict-set</code> <em>dtd dictionary obj</em> …<code>)</code><br> +<code>(dict-set!</code> <em>dtd dictionary obj</em> …<code>)</code></p> <p>Returns a dictionary that contains all the associations of <em>dictionary</em> plus those specified by <em>objs</em>, which alternate between keys and values. If a key to be added already exists in <em>dictionary</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 dictionary objs</em><code>)</code></p> +(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 dictionary objs</em><code>)</code><br> +<code>(dict-adjoin!</code> <em>dtd dictionary objs</em><code>)</code></p> <p>Returns a dictionary that contains all the associations of <em>dictionary</em> plus those specified by <em>objs</em>, which alternate between keys and values. If a key to be added already exists in <em>dictionary</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 dictionary key</em> …<code>)</code></p> +(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 dictionary key</em> …<code>)</code><br> +<code>(dict-delete!</code> <em>dtd dictionary key</em> …<code>)</code></p> <p>Returns a dictionary that contains all the associations of <em>dictionary</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 dictionary keylist</em><code>)</code></p> +(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 dictionary keylist</em><code>)</code><br> +<code>(dict-delete-all!</code> <em>dtd dictionary keylist</em><code>)</code></p> <p>Returns a dictionary with all the associations of <em>dictionary</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 dictionary key value</em><code>)</code></p> +<blockquote><pre>(dict-delete-all aed dict '(1 3)) => ((5 . 6))</pre></blockquote> +<p><code>(dict-replace</code> <em>dtd dictionary key value</em><code>)</code><br> +<code>(dict-replace!</code> <em>dtd dictionary key value</em><code>)</code></p> <p>Returns a dictionary that contains all the associations of <em>dictionary</em> except as follows: If <em>key</em> is the same as a key of <em>dictionary</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>dictionary</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 dictionary key failure</em>)</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 dictionary key failure</em>)<br> +<code>(dict-intern!</code> <em>dtd dictionary key failure</em>)</p> <p>If there is a key in <em>dictionary</em> that is the same as <em>key</em>, returns two values, <em>dictionary</em> and the value associated with <em>key</em>. -Otherwise, returns two values, a dictionary that contains all the associations of <em>dictionary</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>.</p> -<blockquote><pre>(dict-intern! aed dict 1 (lambda () #f)) => ; 2 values +Otherwise, returns two values, a dictionary that contains all the associations of <em>dictionary</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)) 3 -(dict-intern! aed dict 2 (lambda () #f)) => ; 2 values +(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 dictionary key updater</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p> <p><code>(dict-update!</code> <em>dtd dictionary 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> +<p><code>(dict-update/default</code> <em>dtd dictionary key updater default</em><code>)</code></p> <p><code>(dict-update/default!</code> <em>dtd dictionary 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> -<p><code>(dict-pop!</code> <em>dtd dictionary</em><code>)</code></p> +<p><code>(dict-pop</code> <em>dtd dictionary</em><code>)</code><br> +<code>(dict-pop!</code> <em>dtd dictionary</em><code>)</code></p> <p>Chooses an association from <em>dictionary</em> and returns three values: a dictionary that contains all associations of <em>dictionary</em> except the chosen one, and the key and the value of the chosen association. 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 +<blockquote><pre>(dict-pop aed dict) => # 3 values ((3 . 4) (5 . 6)) 1 2</pre></blockquote> -<p><code>(dict-map!</code> <em>dtd proc dictionary</em><code>)</code></p> +<p><code>(dict-map</code> <em>dtd proc dictionary</em><code>)</code><br> +<code>(dict-map!</code> <em>dtd proc dictionary</em><code>)</code></p> <p>Returns a dictionary similar to <em>dictionary</em> that maps each key of <em>dictionary</em> to the value that results from invoking <em>proc</em> on the corresponding key and value of <em>dictionary</em>.</p> +<blockquote><pre>(dict-map (lambda (k v) (cons v k)) aed dict) => ((2 . 1) (4 . 3) (6 . 5))</pre></blockquote> <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 dictionary</em><code>)</code></p> +<p><code>(dict-filter</code> <em>dtd pred dictionary</em><code>)</code><br> +<code>(dict-filter!</code> <em>dtd pred dictionary</em><code>)</code></p> <p>Returns a dictionary similar to <em>dictionary</em> that contains just the associations of <em>dictionary</em> that 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))</pre></blockquote> -<p><code>(dict-remove!</code> <em>dtd pred dictionary</em><code>)</code></p> +<blockquote><pre>(dict-filter (lambda (k v) (= k 1)) aed dict) => ((1 . 2))</pre></blockquote> +<p><code>(dict-remove</code> <em>dtd pred dictionary</em><code>)</code><br> +<code>(dict-remove!</code> <em>dtd pred dictionary</em><code>)</code></p> <p>Returns a dictionary that contains all the associations of <em>dictionary</em> except those that satisfy <em>pred</em> when called on the key and value.</p> -<blockquote><pre>(dict-remove! (lambda (k) (= k 1)) aed dict) => ((3 . 4) (5 . 6))</pre></blockquote> -<p><code>(dict-search!</code> <em>dtd dictionary key failure success</em><code>)</code></p> +<blockquote><pre>(dict-remove (lambda (k) (= k 1)) aed dict) => ((3 . 4) (5 . 6))</pre></blockquote> +<p><code>(dict-search</code> <em>dtd dictionary key failure success</em><code>)</code><br> +<code>(dict-search!</code> <em>dtd dictionary key failure success</em><code>)</code></p> <p>This procedure is a workhorse for dictionary lookup, insert, and delete. The dictionary <em>dictionary</em> is searched for an association whose key is the same as <em>key</em> in the sense of <em>dictionary</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>, and is expected to tail-call one of them.</p> <p>However, if such an association is found, then the <em>success</em> procedure is tail-called with the matching key of <em>dictionary</em>, the associated value, and two procedure arguments, <em>update</em> and <em>remove</em>, and is expected to tail-call one of them.</p> <p>It is an error if the procedure arguments are invoked other than in tail position in the <em>failure</em> and <em>success</em> procedures. It is also an error if the <em>failure</em> and <em>success</em> procedures return to their implicit continuation without invoking one of their arguments.</p> @@ -148,13 +164,13 @@ Otherwise, returns two values, a dictionary that contains all the associations o <li><p>Invoking <code>(</code><em>remove obj</em><code>)</code> returns a dictionary that contains all the associations of <em>dictionary</em>, except for the association with key key.</p></li> </ul> <p>In all cases, <em>obj</em> is returned as a second value.</p> -<p>Here are four examples of <code>dict-search!</code>, +<p>Here are four examples of <code>dict-search</code>, one for each of the four procedures: <blockquote><pre> ;; ignore (define-values (dict value) - (dict-search! (alist->dict '((a . b))) 'c + (dict-search (alist->dict '((a . b))) 'c (lambda (insert ignore) (ignore 'foo)) (lambda args @@ -165,11 +181,11 @@ one for each of the four procedures: ;; insert (define-values (dict value) - (dict-search! (alist->dict '((a . b))) 'c + (dict-search (alist->dict '((a . b))) 'c (lambda (insert ignore) (insert 'd 'foo)) (lambda args - (`rror)))) + (error)))) (dict-ref aed dict 'a)) => b (dict-ref aed dict 'c)) => 'd` value => foo @@ -177,7 +193,7 @@ one for each of the four procedures: ;; update (define-values (dict value) - (dict-search! (alist->dict '((a . b))) 'a + (dict-search (alist->dict '((a . b))) 'a (lambda args (error)) (lambda (key value update delete) @@ -188,7 +204,7 @@ one for each of the four procedures: ;; delete (define-values (dict value) - (dict-search! (alist->dict '((a . b) (c . d))) 'a + (dict-search (alist->dict '((a . b) (c . d))) 'a (lambda args (error)) (lambda (key value update delete) @@ -197,6 +213,8 @@ one for each of the four procedures: value => foo </pre></blockquote> <h3 id="the-whole-dictionary">The whole dictionary</h3> +<p><code>(dict-copy</code> <em>dtd dictionary</em><code>)</code><p> +Returns a dictionary that is similar to <em>dictionary</em> and contains the same associations. Mutating the result of <code>dict-copy</code> does not affect <em>dictionary</em> or vice versa.</p> <p><code>(dict-size</code> <em>dtd dictionary</em><code>)</code></p> <p>Returns an exact integer representing the number of associations in <em>dictionary</em>.</p> <blockquote><pre>(dict-size aed dict) => 3</pre></blockquote> @@ -242,19 +260,26 @@ one for each of the four procedures: <p>Returns an alist whose keys and values are the keys and values of <em>dictionary</em>.</p> <blockquote><pre>; plist to alist (dict->alist '(1 2 3 4 5 6)) => ((1 . 2) (3 . 4) (5 . 6))</pre></blockquote> +<p>Add <code>dict-map</code>, +<code>dict-filter</code>, <code>dict-remove</code>, +and <code>dict-search</code>. +</p> +<p><code>(dict-comparator</code> <em>dtd dictionary</em><code>)</code></p> <h3 id="dictionary-type-descriptors">Dictionary type descriptors</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></p> <p>Returns a new dictionary type providing procedures that allow manipulation of dictionaries of that type. The <em>args</em> are alternately <em>procnames</em> and corresponding <em>procs</em>.</p> <p>A <em>procname</em> argument is a symbol which is the same as one of the procedures defined in this SRFI (other than those in this section), and a <em>proc</em> argument is the specific procedure implementing it for this type. These procedures only need to handle a full-length argument list (except when defining <code>dict-ref</code> and <code>dict-update!</code>), as the other defaults have already been supplied by the framework.</p> -<p>Arguments for the six procedures <code>dictionary?</code>, <code>dict-size</code>, <code>dict-search!</code>, <code>dict-map!</code>, <code>dict-filter!</code>, and <code>dict-for-each</code> are required. The others are optional, but if provided can be more efficient than the versions automatically provided by the implementation of this SRFI.</p> +<p> +<i>Shrink this list if possible:</i> +Arguments for the seven procedures <code>make-dict</code>, <code>dictionary?</code>, <code>dict-size</code>, <code>dict-search!</code>, <code>dict-map!</code>, <code>dict-filter!</code>, and <code>dict-for-each</code> are required. The others are optional, but if provided can be more efficient than the versions automatically provided by the implementation of this SRFI.</p> <p>The following example is from the file <code>plist-impl.scm</code> in the sample implementation; the procedures referred to are also in that file.<p> <blockquote><pre> - (make-dictionary-type + (make-dtd 'dictionary? plist? 'dict-map! plist-map! 'dict-filter! plist-filter! |