diff options
| author |  Arvydas Silanskas
| 2022-02-14 19:04:23 +0200 |
|---|---|---|
| committer | Arvydas Silanskas
| 2022-02-14 19:04:23 +0200 |
| commit | a51ddd23d14382185d97f7d6ff3128c7884e237e (patch) | |
| tree | 96025c3918a0333c2f5dea4f841dc51552addc4f /srfi-225.html | |
| parent | change generator implementation to use continuation based approach (diff) | |
| parent | Update srfi-225.html (diff) | |
Merge branch 'master' of https://github.com/johnwcowan/srfi-225
Diffstat (limited to 'srfi-225.html')
| -rw-r--r-- | srfi-225.html | 299 |
1 files changed, 199 insertions, 100 deletions
diff --git a/srfi-225.html b/srfi-225.html index 5a6799c..48fed8b 100644 --- a/srfi-225.html +++ b/srfi-225.html @@ -29,40 +29,86 @@ <h2 id="abstract">Abstract</h2> -<p>The procedures of this SRFI allow callers to manipulate an object that maps keys to values without the caller needing to know exactly what the type of the object is. However, what procedures can be called on the object is partly determined by whether it is pure or not. Such an object is called a <em>dict(ionary)</em> in this SRFI. +<p>The procedures of this SRFI allow callers to manipulate an object that maps keys to values + without the caller needing to know exactly what the type of the object is. + However, what procedures can be called on the object is partly determined by whether it is pure or not. + Such an object is called a <em>dict(ionary)</em> in this SRFI. <h2 id="issues">Issues</h2> None at present. <h2 id="rationale">Rationale</h2> -<p>Until recently there was only one universally available mechanism for managing key-value pairs: alists. Most Schemes also support hash tables, but until R6RS there was no standard interface to them, and many implementations do not provide that interface.</p> -<p>Now, however, the number of such mechanisms is growing. In addition to both R6RS and R7RS hash tables, there are R7RS persistent inherently ordered and hashed mappings from SRFI 146, inherently ordered mappings with fixnum keys from SRFI 224, and inherently ordered bytevector key-value stores (often on a disk or a remote machine) from SRFI 167.</p> -<p>It’s inconvenient for users if SRFIs or other libraries have to insist on accepting only a specific type of dictionary. This SRFI exposes a number of accessors, updaters, and other procedures that can be called on any dictionary, provided that a <em>dictionary type object</em> (DTO) is available for it: either exported from this SRFI, or from other SRFIs or libraries, or created by the user. DTOs are of an unspecified type.</p> -<p>This in turn requires that the DTO provides a predicate that can recognize its dictionaries, plus several primitive generic procedures.</p> -<p>By using the procedures of this SRFI, a procedure can take a DTO and a dictionary as an argument and make flexible use of the dictionary without knowing its exact type. For the purposes of this SRFI, such a procedure is called a <em>generic procedure</em>. However, it is still necessary to distinguish between pure and impure dictionary types. A pure dictionary type either exposes pure functional update operations or no update operations at all, whereas an impure dictionary type exposes mutation operations. Note that if an instance of an impure dictionary type like SRFI 126 is in fact immutable, it still counts as impure. -<p>The <code>dict-pure?</code> procedure depends only on the <em>dto</em> argument and ignores the <i>dict</i> argument except for possibly checking that the arguments taken together satisfy <code>dictionary?</code>. This is done to maintain uniformity between <i>dict-pure?</i> and the other generic procedures, both at the point of call and when <i>make-dto</i> is invoked.</p> -<p>In addition, dictionaries need to be constructed using type-specific constructors, as the required and optional arguments differ in each case. In addition, the dictionary type provided by the caller of a generic procedure doesn't necessarily have the right performance characteristics needed by the generic procedure itself. Consequently there are no <code>make-dict</code>, <code>dict</code>, <code>dict-unfold</code>, <code>dict-copy</code>, or similar procedures provided by this SRFI.</p> +<p>Until recently there was only one universally available mechanism for managing key-value pairs: alists. + Most Schemes also support hash tables, but until R6RS there was no standard interface to them, and many implementations + do not provide that interface.</p> +<p>Now, however, the number of such mechanisms is growing. In addition to both R6RS and R7RS hash tables, + there are R7RS persistent inherently ordered and hashed mappings from SRFI 146, + inherently ordered mappings with fixnum keys from SRFI 224, + and inherently ordered bytevector key-value stores (often on a disk or a remote machine) from SRFI 167.</p> +<p>It’s inconvenient for users if SRFIs or other libraries have to insist on accepting only a specific type of dictionary. + This SRFI exposes a number of accessors, updaters, and other procedures that can be called on any dictionary, + provided that a <em>dictionary type object</em> (DTO) is available for it: + either exported from this SRFI, or from other SRFIs or libraries, or created by the user. + DTOs are of an unspecified type.</p> +<p>This in turn requires that the DTO provides a predicate that can recognize its dictionaries, + plus several primitive generic procedures.</p> +<p>By using the procedures of this SRFI, a procedure can take a DTO and a dictionary as an argument + and make flexible use of the dictionary without knowing its exact type. + For the purposes of this SRFI, such a procedure is called a <em>generic procedure</em>. + However, it is still necessary to distinguish between pure and impure dictionary types. + A pure dictionary type either exposes pure functional update operations or no update operations at all, + whereas an impure dictionary type exposes mutation operations. + Note that if an instance of an impure dictionary type like SRFI 126 is in fact immutable, it still counts as impure. +<p>The <code>dict-pure?</code> procedure depends only on the <em>dto</em> argument + and ignores the <i>dict</i> argument except for possibly checking that the arguments taken together + satisfy <code>dictionary?</code>. + This is done to maintain uniformity between <code>dict-pure?</code> and the other generic procedures, + both at the point of call and when <code>make-dto</code> is invoked.</p> +<p>In addition, dictionaries need to be constructed using type-specific constructors, + as the required and optional arguments differ in each case. + In addition, the dictionary type provided by the caller of a generic procedure + doesn't necessarily have the right performance characteristics needed by the generic procedure itself. + Consequently there are no <code>make-dict</code>, <code>dict</code>, <code>dict-unfold</code>, + <code>dict-copy</code>, or similar procedures provided by this SRFI.</p> <h2 id="specification">Specification</h2> -<p>We call a specific key-value combination an <em>association</em>. This is why an alist, or association list, is called that; it is a list of associations represented as pairs.</p> -<p>A <em>dictionary</em> or <em>dict</em> is a collection of associations which may be inherently ordered by their keys or not. In principle an <em>equality predicate</em> is enough, given a key, to determine whether an association with that key exists in the dictionary. However, for efficiency most dictionaries require an <em>ordering predicate</em> or a <em>hash function</em> as well. -<p>When a key argument is said to be the <em>same</em> 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. -Two dictionaries are <em>similar</em> if they are of the same type and have the same equality predicate and the same ordering predicate and/or hash function.</p> -<p>When an association is deleted from a dictionary other than by <code>dict-remove</code>, or is updated, any other associations with the same key remain in the dictionary. Whether such duplicate keys are possible depends on the dictionary type. Alists do allow them:</p> +<p>We call a specific key-value combination an <em>association</em>. + This is why an alist, or association list, is called that; it is a list of associations represented as pairs.</p> +<p>A <em>dictionary</em> or <em>dict</em> is a collection of associations which may be inherently ordered by their keys or not. + In principle an <em>equality predicate</em> is enough, given a key, + to determine whether an association with that key exists in the dictionary. + However, for efficiency most dictionaries require an <em>ordering predicate</em> or a <em>hash function</em> as well. +<p>When a key argument is said to be the <em>same</em> 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. + Two dictionaries are <em>similar</em> if they have the same DTO + and have the same equality predicate and the same ordering predicate and/or hash function.</p> +<p>When an association is deleted from a dictionary other than by <code>dict-remove</code>, + or is updated, any other associations with the same key remain in the dictionary. + Whether such duplicate keys are possible depends on the dictionary type. Alists do allow them:</p> <blockquote><pre>(dict-delete '((1 . 2) (1 . 3) (2 . 4)) 1) => ((1 . 3) (2 . 4))</code>. </pre></blockquote> <h3 id="alists">Alists</h3> -<p>Alists are supported as dictionaries, but are given special treatment. New values are added to the beginning of the alist and the new alist is returned. If an association has been updated, then both the new and the old association may be processed by the whole-dictionary procedures. The examples in this SRFI use alists.</p> -<p>An alist (unlike a hashtable or mapping) does not know which equality predicate its users intend to use on it. Therefore, rather than exporting a single DTO for all alists, this SRFI provides a procedure <code>make-alist-dto</code> that takes an equality predicate and returns a DTO specialized for manipulation of alists using that predicate. For convenience, DTOs for <code>eqv?</code> and <code>equal?</code> are exported.</p> +<p>Alists are supported as dictionaries, but are given special treatment. + New values are added to the beginning of the alist and the new alist is returned. + If an association has been updated, then both the new and the old association + may be processed by the whole-dictionary procedures. The examples in this SRFI use alists.</p> +<p>An alist (unlike a hashtable or mapping) does not know which equality predicate its users intend to use on it. + Therefore, rather than exporting a single DTO for all alists, + this SRFI provides a procedure <code>make-alist-dto</code> that takes an equality predicate + and returns a DTO specialized for manipulation of alists using that predicate. + For convenience, DTOs for <code>eqv?</code> and <code>equal?</code> are exported.</p> <p>Each of the following examples is assumed to be prefixed by the following definitions:</p> <blockquote><pre>(define dict (list '(1 . 2) '(3 . 4) '(5 . 6))) (define aed alist-eqv-dto) </pre></blockquote> Consequently, previous examples don't affect later ones. -<p>The <em>dto</em> argument is not discussed in the individual procedure descriptions below, but it is an error if invoking <code>dictionary?</code> on <em>dto</em> and <em>dict</em> would return <code>#f</code>. The <code>dictionary?</code> procedure itself is an exception to this.</p> +<p>The <em>dto</em> argument is not discussed in the individual procedure descriptions below, + but it is an error if invoking <code>dictionary?</code> on <em>dto</em> and <em>dict</em> would return <code>#f</code>. + The <code>dictionary?</code> procedure itself is an exception to this.</p> <h3 id="predicates">Predicates</h3> <p><code>(dictionary?</code> <em>dto obj</em><code>)</code></p> -<p>Returns <code>#t</code> if <em>obj</em> answers <code>#t</code> to the type predicate stored in <em>dto</em> and <code>#f</code> otherwise.</p> +<p>Returns <code>#t</code> if <em>obj</em> answers <code>#t</code> to the type predicate + stored in <em>dto</em> and <code>#f</code> otherwise.</p> <blockquote><pre>(dictionary? aed dict) => #t (dictionary? aed 35) => #t</pre></blockquote> <p><code>(dict-empty?</code> <em>dto dict</em><code>)</code></p> @@ -74,7 +120,8 @@ Consequently, previous examples don't affect later ones. (dict-contains? aed dict 2) => #f</pre></blockquote> <p>Returns <code>#t</code> if one of the keys of <em>dict</em> is the same as <em>key</em>, and <code>#f</code> otherwise.</p> <p><code>(dict=?</code> <em>dto = dict1 dict2</em><code>)</code></p> -<p>Returns <code>#t</code> if the keys of <em>dto dict1</em> and <em>dict2</em> are the same, and the corresponding values are the same in the sense of the <em>=</em> argument.</p> +<p>Returns <code>#t</code> if the keys of <em>dto dict1</em> and <em>dict2</em> are the same, + and the corresponding values are the same in the sense of the <em>=</em> argument.</p> <blockquote><pre> (define dicta '((5 . 6) (3 . 4) (1 . 2)) (define dictb '((1 . 2) (3 . 4)) @@ -88,20 +135,33 @@ Consequently, previous examples don't affect later ones. </pre></blockquote> <h3 id="lookup">Lookup</h3> <p><code>(dict-ref</code> <em>dto dict key</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p> -<p>If <em>key</em> is the same as some key of <em>dict</em>, then invokes <em>success</em> on the corresponding value and returns its result. If <em>key</em> is not a key of <em>dict</em>, then invokes the thunk <em>failure</em> and returns its result. The default value of <em>failure</em> signals an error; the default value of <em>success</em> is the identity procedure.</p> +<p>If <em>key</em> is the same as some key of <em>dict</em>, then invokes <em>success</em> + on the corresponding value and returns its result. If <em>key</em> is not a key of <em>dict</em>, + then invokes the thunk <em>failure</em> and returns its result. + The default value of <em>failure</em> signals an error; the default value of <em>success</em> is the identity procedure.</p> <blockquote><pre>(dict-ref aed dict 1 (lambda () '()) list) => (1) ; Success wraps value in a list (dict-ref aed dict 2 (lambda () '()) list) => () ; Failure returns empty list</pre></blockquote> <p><code>(dict-ref/default</code> <em>dto dict key default</em><code>)</code></p> -<p>If <em>key</em> is the same as some key of <em>dict</em>, returns the corresponding value. If not, returns <em>default</em>.</p> +<p>If <em>key</em> is the same as some key of <em>dict</em>, returns the corresponding value. + If not, returns <em>default</em>.</p> <blockquote><pre>(dict-ref/default aed dict 1 #f) => 1 (dict-ref/default aed dict 1 #f) => #f</pre></blockquote> <h3 id="update-procedures">Update procedures</h3> -<p>All update procedures exist in pairs, with and without a final <code>!</code>. The descriptions apply to the procedures without <code>!</code>; the procedures with <code>!</code> mutate their dictionary argument and do not return a dictionary value. Only one set of procedures is supported by any dictionary type: for example, SRFI 125 hash tables are impure and support only mutation, whereas SRFI 146 mappings are pure and support only functional update. The <code>dict-pure?</code> procedure can be used to determine which set is usable.</p> +<p>All update procedures exist in pairs, with and without a final <code>!</code>. + The descriptions apply to the procedures without <code>!</code>; + the procedures with <code>!</code> mutate their dictionary argument and do not return a dictionary value. + Only one set of procedures is supported by any dictionary type: + for example, SRFI 125 hash tables are impure and support only mutation, + whereas SRFI 146 mappings are pure and support only functional update. + The <code>dict-pure?</code> procedure can be used to determine which set is usable.</p> +<p>Updates are not permitted while any generic procedure is running that takes a procedure argument.</p> <p><code>(dict-set</code> <em>dto dict obj</em> …<code>)</code><br> <code>(dict-set!</code> <em>dto dict obj</em> …<code>)</code></p> -<p>Returns a dictionary that contains all the associations of <em>dict</em> plus those specified by <em>objs</em>, which find-updatenate between keys and values. If a key to be added already exists in <em>dict</em>, the new value prevails.</p> +<p>Returns a dictionary that contains all the associations of <em>dict</em> + plus those specified by <em>objs</em>, which altetnate between keysF and values. + If a key to be added already exists in <em>dict</em>, the new value prevails.</p> <blockquote><pre>; new values are prepended (dict-set aed dict 7 8) => ((7 . 8) (1 . 2) (3 . 4) (5 . 6)) @@ -109,7 +169,9 @@ Consequently, previous examples don't affect later ones. ((3 . 5) (1 . 2) (3 . 4) (5 . 6))</pre></blockquote> <p><code>(dict-adjoin</code> <em>dto dict objs</em><code>)</code><br> <code>(dict-adjoin!</code> <em>dto dict objs</em><code>)</code></p> -<p>Returns a dictionary that contains all the associations of <em>dict</em> plus those specified by <em>objs</em>, which find-updatenate between keys and values. If a key to be added already exists in <em>dict</em>, the old value prevails.</p> +<p>Returns a dictionary that contains all the associations of <em>dict</em> + plus those specified by <em>objs</em>, which alternate between keys and values. + If a key to be added already exists in <em>dict</em>, the old value prevails.</p> <blockquote><pre>; new values are prepended to alists (dict-adjoin aed dict 7 8) => ((7 . 8) (1 . 2) (3 . 4) (5 . 6)) @@ -117,7 +179,8 @@ Consequently, previous examples don't affect later ones. ((1 . 2) (3 . 4) (5 . 6))</pre></blockquote> <p><code>(dict-delete</code> <em>dto dict key</em> …<code>)</code><br> <code>(dict-delete!</code> <em>dto dict key</em> …<code>)</code></p> -<p>Returns a dictionary that contains all the associations of <em>dict</em> except those whose keys are the same as one of the <em>keys</em>. +<p>Returns a dictionary that contains all the associations of <em>dict</em> + except those whose keys are the same as one of the <em>keys</em>. <blockquote><pre>; new values are prepended (dict-delete aed dict 1 3) => ((5. 6)) ; may share @@ -130,14 +193,19 @@ Consequently, previous examples don't affect later ones. <p><code>(dict-replace</code> <em>dto dict key value</em><code>)</code><br> <code>(dict-replace!</code> <em>dto dict key value</em><code>)</code></p> <p>Returns a dictionary that contains all the associations of <em>dict</em> except as follows: -If <em>key</em> is the same as a key of <em>dict</em>, then the association for that key is omitted and replaced by the association defined by the pair <em>key</em> and <em>value</em>. +If <em>key</em> is the same as a key of <em>dict</em>, + then the association for that key is omitted and replaced by the association + defined by the pair <em>key</em> and <em>value</em>. If there is no such key in <em>dict</em>, then dictionary is returned unchanged.</p> <blockquote><pre>(dict-replace aed dict 1 3) => ((1 . 3) (1 . 2) (3 . 4) (5 . 6)) </pre></blockquote> <p><code>(dict-intern</code> <em>dto dict key failure</em>)<br> <code>(dict-intern!</code> <em>dto dict key failure</em>)</p> -<p>If there is a key in <em>dict</em> that is the same as <em>key</em>, returns two values, <em>dict</em> and the value associated with <em>key</em>. -Otherwise, returns two values, a dictionary that contains all the associations of <em>dict</em> and in addition a new association that maps <em>key</em> to the result of invoking <em>failure</em>, and the result of invoking <em>failure</em>.<br> +<p>If there is a key in <em>dict</em> that is the same as <em>key</em>, returns two values, + <em>dict</em> and the value associated with <em>key</em>. +Otherwise, returns two values, a dictionary that contains + all the associations of <em>dict</em> and in addition a new association that maps <em>key</em> + to the result of invoking <em>failure</em>, and the result of invoking <em>failure</em>.<br> <blockquote><pre>(dict-intern aed dict 1 (lambda () #f)) => ; 2 values ((1 . 2) (3 . 4) (5 . 6)) 2 @@ -155,7 +223,9 @@ Otherwise, returns two values, a dictionary that contains all the associations o </pre></blockquote> <p><code>(dict-update/default</code> <em>dto dict key updater default</em><code>)</code><br> <code>(dict-update/default!</code> <em>dto dict key updater default</em><code>)</code></p> -<p>Retrieves the value of <em>key</em> as if by <code>dict-ref/default</code>, invokes <em>updater</em> on it, and sets the value of <em>key</em> to be the result of calling <em>updater</em> as if by <code>dict-set</code>, but may do so more efficiently. Returns the updated dictionary.</p> +<p>Retrieves the value of <em>key</em> as if by <code>dict-ref/default</code>, invokes <em>updater</em> on it, + and sets the value of <em>key</em> to be the result of calling <em>updater</em> as if by <code>dict-set</code>, + but may do so more efficiently. Returns the updated dictionary.</p> <blockquote><pre> (dict-update/default aed dict 1 (lambda (x) (+ 1 x)) 0) => @@ -166,7 +236,11 @@ Otherwise, returns two values, a dictionary that contains all the associations o </pre></blockquote> <p><code>(dict-pop</code> <em>dto dict</em><code>)</code><br> <code>(dict-pop!</code> <em>dto dict</em><code>)</code></p> -<p>Chooses an association from <em>dict</em> and returns three values: a dictionary that contains all associations of <em>dict</em> except the chosen one, and the key and the value of the association chosen. If the dictionary is inherently ordered, the first association is chosen; otherwise the chosen association is arbitrary.</p> +<p>Chooses an association from <em>dict</em> and returns three values: + a dictionary that contains all associations of <em>dict</em> except the chosen one, + and the key and the value of the association chosen. + If the dictionary is inherently ordered, the first association is chosen; + otherwise the chosen association is arbitrary.</p> <p>If dictionary contains no associations, it is an error.</p> <blockquote><pre>(dict-pop aed dict) => ; 3 values ((3 . 4) (5 . 6)) @@ -174,25 +248,33 @@ Otherwise, returns two values, a dictionary that contains all the associations o 2</pre></blockquote> <p><code>(dict-map</code> <em>dto proc dict</em><code>)</code><br> <code>(dict-map!</code> <em>dto proc dict</em><code>)</code></p> -<p>Returns a dictionary similar to <em>dict</em> that maps each key of <em>dict</em> to the <em>proc</em> on the key and corresponding value of <em>dict</em>.</p> +<p>Returns a dictionary similar to <em>dict</em> that maps each of <em>dict</em> + to the result of applying <em>proc</em> to the key and corresponding value of <em>dict</em>.</p> <blockquote><pre>(dict-map (lambda (k v) (cons v k)) aed dict) => ((2 . 1) (4 . 3) (6 . 5))</pre></blockquote> <p><code>(dict-filter</code> <em>dto pred dict</em><code>)</code><br> <code>(dict-filter!</code> <em>dto pred dict</em><code>)</code><br> <code>(dict-remove</code> <em>dto pred dict</em><code>)</code><br> <code>(dict-remove!</code> <em>dto pred dict</em><code>)</code></p> -<p>Returns a dictionary similar to <em>dict</em> that contains just the associations of <em>dict</em> that satisfy / do not satisfy <em>pred</em> when it is invoked on the key and value of the association.</p> +<p>Returns a dictionary similar to <em>dict</em> that contains + just the associations of <em>dict</em> that satisfy / do not satisfy <em>pred</em> + when it is invoked on the key and value of the association.</p> <blockquote><pre>(dict-filter (lambda (k v) (= k 1)) aed dict) => ((1 . 2)) (dict-remove (lambda (k) (= k 1)) aed dict) => ((3 . 4) (5 . 6))</pre></blockquote> <p><code>(dict-find-update</code> <em>dto dict key failure success</em><code>)</code><br> <code>(dict-find-update!</code> <em>dto dict key failure success</em><code>)</code></p> -<p>This procedure is a workhorse for dictionary lookup, insert, and delete. The dictionary <em>dict</em> is searched for an association whose key is the same as <em>key</em>. If one is not found, then the <em>failure</em> procedure is tail-called with two procedure arguments, <em>insert</em> and <em>ignore</em>.</p> -<p>If such an association is found, then the <em>success</em> procedure is tail-called with the matching key of <em>dict</em>, the associated value, and two procedure arguments, <em>update</em> and <em>delete</em>.</p> +<p>This procedure is a workhorse for dictionary lookup, insert, and delete. + The dictionary <em>dict</em> is searched for an association whose key is the same as <em>key</em>. + If one is not found, then the <em>failure</em> procedure is tail-called with two procedure arguments, + <em>insert</em> and <em>ignore</em>.</p> +<p>If such an association is found, then the <em>success</em> procedure is tail-called + with the matching key of <em>dict</em>, the associated value, and two procedure arguments, <em>update</em> and <em>delete</em>.</p> <p>In either case, the values returned by <em>failure</em> or <em>success</em> are returned.</p> <ul> -<li><p>Invoking <code>(</code><em>insert value</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, and in addition a new association that maps <em>key</em> to <em>value</em>.</p></li> +<li><p>Invoking <code>(</code><em>insert value</em><code>)</code> returns a dictionary + that contains all the associations of <em>dict</em>, and in addition a new association that maps <em>key</em> to <em>value</em>.</p></li> <li><p>Invoking <code>(</code><em>ignore</em><code>)</code> has no effects and returns <em>dict</em> unchanged.</p></li> <li><p>Invoking <code>(</code><em>update new-key new-value</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, except for the association whose key is the same as <em>key</em>, which is replaced or hidden by a new association that maps <em>new-key</em> to <em>new-value</em>. It is an error if <em>key</em> and <em>new-key</em> are not the same in the sense of the dictionary’s equality predicate.</p></li> <li><p>Invoking <code>(</code><em>delete</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, except for the association with @@ -247,34 +329,53 @@ one for each of the four procedures: <p>Returns an exact integer representing the number of associations in <em>dict</em>.</p> <blockquote><pre>(dict-size aed dict) => 3</pre></blockquote> <p><code>(dict-count</code> <em>dto pred dict</em><code>)</code></p> -<p>Passes each association of dictionary as two arguments to <em>pred</em> and returns the number of times that <em>pred</em> returned true as an an exact integer.</p> +<p>Passes each association of dictionary as two arguments to <em>pred</em> + and returns the number of times that <em>pred</em> returned true as an an exact integer.</p> <blockquote><pre>(dict-count aed dict (lambda (k v) (even? k))) => 0</pre></blockquote> <p><code>(dict-any</code> <em>dto pred dict</em><code>)</code></p> -<p>Passes each association of <em>dict</em> as two arguments to <em>pred</em> and returns the value of the first call to <em>pred</em> that returns true, after which no further calls are made. If the dictionary type is inherently ordered, associations are processed in that order; otherwise in an arbitrary order. If all calls return false, <code>dict-any</code> returns false.</p> +<p>Passes each association of <em>dict</em> as two arguments to <em>pred</em> + and returns the value of the first call to <em>pred</em> that returns true, + after which no further calls are made. If the dictionary type is inherently ordered, + associations are processed in that order; otherwise in an arbitrary order. + If all calls return false, <code>dict-any</code> returns false.</p> <blockquote><pre>(define (both-even? k v) (and (even? k) (even? v))) (dict-any aed both-even? '((2 . 4) (3 . 5))) => #t (dict-any aed both-even? '((1 . 2) (3 . 4))) => #f</pre></blockquote> <p><code>(dict-every</code> <em>dto pred dict</em><code>)</code></p> -<p>Passes each association of <em>dict</em> as two arguments to <em>pred</em> and returns <code>#f</code> after the first call to <em>pred</em> that returns false, after which no further calls are made. If the dictionary type is inherently ordered, associations are processed in that order; otherwise in an arbitrary order. If all calls return true, <code>dict-any</code> returns the value of the last call, or <code>#t</code> if no calls are made.</p> +<p>Passes each association of <em>dict</em> as two arguments to <em>pred</em> + and returns <code>#f</code> after the first call to <em>pred</em> that returns false, + after which no further calls are made. If the dictionary type is inherently ordered, + associations are processed in that order; otherwise in an arbitrary order. + If all calls return true, <code>dict-any</code> returns the value of the last call, + or <code>#t</code> if no calls are made.</p> <blockquote><pre>(define (some-even? k v) (or (even? k) (even? v))) (dict-every aed some-even? '((2 . 3) (3 . 4))) => #t (dict-every aed some-even? '((1 . 3) (3 . 4))) => #f</pre></blockquote> <p><code>(dict-keys</code> <em>dto dict</em><code>)</code></p> -<p>Returns a list of the keys of <em>dict</em>. If the dictionary type is inherently ordered, associations appear in that order; otherwise in an arbitrary order. The order may change when new elements are added to <em>dict</em>.</p> +<p>Returns a list of the keys of <em>dict</em>. If the dictionary type is inherently ordered, + associations appear in that order; otherwise in an arbitrary order. + The order may change when new elements are added to <em>dict</em>.</p> <blockquote><pre>(dict-keys aed dict) => (1 3 5)</pre></blockquote> <p><code>(dict-values</code> <em>dto dict</em><code>)</code></p> -<p>Returns a list of the values of <em>dict</em>. The results returned by <code>dict-keys</code> and <code>dict-values</code> are not necessarily ordered consistently.</p> +<p>Returns a list of the values of <em>dict</em>. + The results returned by <code>dict-keys</code> and <code>dict-values</code> are not necessarily ordered consistently.</p> <blockquote><pre>(dict-values aed dict) => (2 4 6)</pre></blockquote> <p><code>(dict-entries</code> <em>dto dict</em><code>)</code></p> -<p>Returns two values, the results of calling <code>dict-keys</code> and the result of calling <code>dict-values</code> on <em>dict</em>.</p> +<p>Returns two list values, the result of calling <code>dict-keys</code> + and the result of mapping <code>proc</code> over the first list.</p> <blockquote><pre>(dict-entries aed dict) => ; 2 values (1 3 5) (2 4 6)</pre></blockquote> <p><code>(dict-fold</code> <em>dto proc knil dict</em><code>)</code></p> -<p>Invokes <em>proc</em> on each association of <em>dict</em> with three arguments: the key of the association, the value of the association, and an accumulated result of the previous invocation. For the first invocation, <em>knil</em> is used as the third argument. Returns the result of the last invocation, or <em>knil</em> if there was no invocation. Note that there is no guarantee of a consistent result if the dictionary does not have an inherent order.</p> +<p>Invokes <em>proc</em> on each association of <em>dict</em> with three arguments: + the key of the association, the value of the association, and an accumulated result of the previous invocation. + For the first invocation, <em>knil</em> is used as the third argument. + Returns the result of the last invocation, or <em>knil</em> if there was no invocation. + Note that there is no guarantee of a consistent result if the dictionary does not have an inherent order.</p> <blockquote><pre>(dict-fold + 0 '((1 . 2) (3 . 4))) => 10</pre></blockquote> <p><code>(dict-map->list</code> <em>dto proc dict</em><code>)</code></p> -<p>Returns a list of values that result from invoking <em>proc</em> on the keys and corresponding values of <em>dict</em>.</p> +<p>Returns a list of values that result from invoking <em>proc</em> on the keys + and corresponding values of <em>dict</em>.</p> <blockquote><pre> (dict-map->list (lambda (k v) v) dict) => (2 4 6), @@ -283,46 +384,62 @@ one for each of the four procedures: </pre></blockquote> <p><code>(dict->alist</code> <em>dto dict</em><code>)</code></p> <p>Returns an alist whose keys and values are the keys and values of <em>dict</em>.</p> -<p>Add <code>dict-map</code>, <code>dict-filter</code>, <code>dict-remove</code>, and <code>dict-find-update</code>. </p> <p><code>(dict-comparator</code> <em>dto dict</em><code>)</code></p> -<p>Return a comparator representing the type predicate, equality predicate, ordering predicate, and hash function of <em>dict</em>. The last two may be <code>#f</code> if the dictionary does not make use of these functions.</p> +<p>Return a comparator representing the type predicate, equality predicate, + ordering predicate, and hash function of <em>dict</em>. + The last two may be <code>#f</code> if the dictionary does not make use of these functions.</p> <p>If no comparator is relevant to the dictionary type, returns <code>#f</code>.</p> <h3 id="iteration">Iteration</h3> -<p><code>(dict-for-each</code> <em>dto proc dict</em><code>)</code></p> -<p>Invokes <em>proc</em> on each key of <em>dict</em> and its corresponding value in that order. This procedure is used for doing operations on the whole dictionary. If the dictionary type is inherently ordered, associations are processed in that order; otherwise in an arbitrary order. Returns an unspecified value.</p> + <p><code>(dict-for-each</code> <em>dto proc dict</em> [ <em>start</em> [ <em>end</em> ] ] <code>)</code></p> +<p>Invokes <em>proc</em> on each key of <em>dict</em> and its corresponding value in that order. + This procedure is used for doing operations on the whole dictionary. + If the dictionary type is inherently ordered, associations are processed in the order specified + by the dictionary's comparator; otherwise they are processed in an arbitrary order. + The <em>start</em> and <em>end</em> arguments specify the inclusive lower bound and exclusive upper bound + of the keys (in the sense of the dictionary's comparator). + They can can provide additional efficiency when iterating over part of the dictionary + if the dictionary is ordered. The procedure returns an unspecified value.</p> <blockquote><pre>(define (write-key key value) (write key)) (dict-for-each write-key aed dict) => unspecified ; writes "135" to current output</pre></blockquote> -<p><code>(dict-for-each<</code> <em>dto proc dict key</em><code>)</code><br> -<code>(dict-for-each<=</code> <em>dto proc dict key</em><code>)</code><br> -<code>(dict-for-each></code> <em>dto proc dict key</em><code>)</code><br> -<code>(dict-for-each>=</code> <em>dto proc dict key</em><code>)</code></p> -<p>Invokes <em>proc</em> on each key of <em>dict</em> that is less than / less than or equal to / greater than / greater than or equal to <em>key</em> and its corresponding value. This procedure is used for doing operations on part of the dictionary. If the dictionary type is inherently ordered, associations are processed in that order; otherwise in an arbitrary order. Returns an unspecified value.</p> -<p><code>(dict-for-each-in-open-interval</code> <em>dto proc dict key1 key2</em><code>)</code><br> -<code>(dict-for-each-in-closed-interval</code> <em>dto proc dict key1 key2</em><code>)</code><br> -<code>(dict-for-each-in-open-closed-interval</code> <em>dto proc dict key1 key2</em><code>)</code><br> -<code>(dict-for-each-in-closed-open-interval</code> <em>dto proc dict key1 key2</em><code>)</code></p> -<p>Invokes <em>proc</em> on each key of <em>dict</em> that is that is within the specified interval between <em>key1</em> and <em>key2</em>, and its corresponding value. This procedure is used for doing operations on part of the dictionary. If the dictionary type is inherently ordered, associations are processed in that order; otherwise in an arbitrary order. Returns an unspecified value.</p> -<h3 id="generator-procedures">Generator procedures</h3> -<p><code>(make-dict-generator</code> <em>dto dict</em><code>)</code></p> -<p>Returns a <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">generator</a> that when invoked returns the associations of <em>dict</em> as pairs. When no associations are left, returns an end-of-file object. If the dictionary type is inherently ordered, associations are processed in that order; otherwise in an arbitrary order. It is an error to mutate <em>dict</em> until the generator is exhausted.</p> -<p><code>(dict-set-accumulator</code> <em>dto dict</em><code>)</code></p> -<p>Returns a SRFI 158 accumulator procedure that when invoked on a pair adds the <code>car</code> and <code>cdr</code> of the pair as a key and value, returning the new value of the dictionary. If invoked on an end-of-file object, no action is taken and <em>dict</em> is returned. If a key to be added already exists in dictionary, the new value prevails.</p> -<p><code>(dict-adjoin-accumulator</code> <em>dto dict</em><code>)</code></p> -<p>The same as <code>dict-set-accumulator</code>, except that if a key to be added already exists in dictionary, the old value prevails.</p> +<p><code>(dict->generator</code> <em>dto dict</em> [ <em>start</em> [ <em>end</em> ] ] <code>)</code></p> +<p>Returns a <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158 generator</a> + that when invoked returns the associations of <em>dict</em> as pairs. + This procedure is used for doing operations on the whole dictionary. + If the dictionary type is inherently ordered, associations are processed in the order specified + by the dictionary's comparator; otherwise they are processed in an arbitrary order. + <p>The <em>start</em> and <em>end</em> arguments specify the inclusive lower bound and exclusive upper bound + of the keys to be processed (in the sense of the dictionary's comparator). + They can can provide additional efficiency when iterating over part of the dictionary + if the dictionary is ordered. The procedure returns an unspecified value.</p> + <p>It is an error to mutate <em>dict</em> until after the generator is exhausted. + When all the associations have been processed, returns an end-of-file object.</> + <p><code>(dict-set-accumulator</code> <em>dto dict</em><code>)</code><br> +<code>(dict-set!-accumulator</code> <em>dto dict accum</em><code>)</code></p> +<p>Returns a SRFI 158 accumulator procedure that when invoked on a pair adds the <code>car</code> and <code>cdr</code> of the pair + as a key and value of <em>dict</em> as if by <em>dict-set</em>, eventually returning the new value of <em>dict</em>. + If invoked on an end-of-file object, no action is taken and <em>dict</em> is returned.</p> +<p>The <code>!</code> variant uses <code>dict-set!</code> instead. +<p><code>(dict-adjoin-accumulator</code> <em>dto dict</em><code>)</code><br> +<code>(dict-adjoin!-accumulator!</code> <em>dto dict</em><code>)</code></p> +<p>The same as <code>dict-set!-accumulator</code>, except using <code>dict-adjoin(!)</code>. </p> <h3 id="dictionary-type-object-procedures">Dictionary type object procedures</h3> <p><code>(dto?</code> <em>obj</em><code>)</code></p> <p>Returns <code>#t</code> if <em>obj</em> is a DTO, and <code>#f</code> otherwise.</p> <p><code>(make-dto</code> <em>arg</em> …<code>)</code><br> <code>(dto (</code><em>proc-id procname</em><code>)</code> …<code>)</code> [syntax]</p> -<p>Returns a new DTO providing procedures that allow manipulation of dictionaries of that type. The <em>args</em> are find-updatenately <em>proc-ids</em> and corresponding <em>procs</em>.</p> -<p>A <em>proc-id</em> argument is the value of a variable whose name is the same as a procedure (except those in this section and the Exceptions section) suffixed with <code>-id</code>, and a <em>proc</em> argument is the specific procedure implementing it for this type. -Note that there is only one proc-id variable for each pair of pure and impure procedures: -the proc-id variable for <code>dict-map-id</code> and <code>dict-map!</code> is <code>dict-map-id</code>.</p> -<p>The following proc-id variables (and corresponding primitive procedures) need to be provided in order for the DTO to support the full set of dictionary procedures:</p> +<p>Returns a new DTO providing procedures that allow manipulation of dictionaries of a new type. + The <em>args</em> are alternately <em>proc-ids</em> and corresponding <em>procs</em>.</p> +<p>A <em>proc-id</em> argument is the value of a variable whose name is the same as a procedure + (except those in this section and the Exceptions section) suffixed with <code>-id</code>, + and a <em>proc</em> argument is the specific procedure implementing it for this type. + Note that there is only one proc-id variable for each pair of pure and impure procedures: + the proc-id variable for <code>dict-map-id</code> and <code>dict-map!</code> is <code>dict-map-id</code>.</p> +<p>The following proc-id variables (and corresponding primitive procedures) need to be provided + in order for the DTO to support the full set of dictionary procedures:</p> <ul> <li><code>dictionary?-id</code></li> <li><code>dict-find-update-id</code></li> @@ -332,8 +449,15 @@ the proc-id variable for <code>dict-map-id</code> and <code>dict-map!</code> is <li><code>dict-remove-id</code></li> <li><code>dict-size-id</code></li> </ul> -<p>Note that it is not an error to omit any of these, but some dictionary procedures may be unavailable.</p> -<p>There are additional proc-id variables that may be provided with corresponding procedures in order to increase efficiency. For example, it is not necessary to provide a <code>dict-ref</code> procedure, because the default version is built on top of <code>dict-find-update</code> or <code>dict-find-update!</code>. But if the underlying dictionary provides its own <code>-ref</code> procedure, it may be more efficient to specify it to <code>make-dto</code> using <code>dict-ref-id</code>. Here is the list of additional proc-id variables:</p> +<p>Note that if any of these are not provided, an implementation-defined set + of generic procedures will generate errors if invoked.</p> +<p>There are additional proc-id variables that may be provided with corresponding procedures + in order to increase efficiency. + For example, it is not necessary to provide a <code>dict-ref</code> procedure, + because the default version is built on top of <code>dict-find-update</code> or <code>dict-find-update!</code>. + But if the underlying dictionary provides its own <code>-ref</code> procedure, + it may be more efficient to specify it to <code>make-dto</code> using <code>dict-ref-id</code>. + Here is the list of additional proc-id variables:</p> <ul> <li><code>dict->alist-id</code></li> <li><code>dict-adjoin-accumulator-id</code></li> @@ -348,15 +472,7 @@ the proc-id variable for <code>dict-map-id</code> and <code>dict-map!</code> is <li><code>dict-every-id</code></li> <li><code>dict-filter-id</code></li> <li><code>dict-fold-id</code></li> -<li><code>dict-for-each<-id</code></li> -<li><code>dict-for-each<=-id</code></li> <li><code>dict-for-each-id</code></li> -<li><code>dict-for-each-in-closed-interval-id</code></li> -<li><code>dict-for-each-in-closed-open-interval-id</code></li> -<li><code>dict-for-each-in-open-closed-interval-id</code></li> -<li><code>dict-for-each-in-open-interval-id</code></li> -<li><code>dict-for-each>-id</code></li> -<li><code>dict-for-each>=-id</code></li> <li><code>dict-intern-id</code></li> <li><code>dict-keys-id</code></li> <li><code>dict-map->list-id</code></li> @@ -372,9 +488,11 @@ the proc-id variable for <code>dict-map-id</code> and <code>dict-map!</code> is <li><code>dict-update/default-id</code></li> <li><code>dict-values-id</code></li> <li><code>dict=?-id</code></li> -<li><code>make-dict-generator-id</code></li> +<li><code>dict->generator-id</code></li> </ul> -<p>The <code>dto</code> macro behaves like a wrapper around <code>make-dto</code> with parentheses around each <em>procid-procname</em> pair. The macro may also verify that the <em>proc-ids</em> are valid, that there are no duplicates, etc.</p> +<p>The <code>dto</code> macro behaves like a wrapper around <code>make-dto</code> + with parentheses around each <em>procid-procname</em> pair. + The macro may also verify that the <em>proc-ids</em> are valid, that there are no duplicates, etc.</p> <p><code>(make-alist-dto</code> <em>equal</em><code>)</code></p> <p>Returns a DTO for manipulating an alist using the equality predicate <em>equal</em>.</p> <blockquote><code>(make-alist-dto =) => a DTO for alists using numeric equality</code></blockquote> @@ -492,34 +610,15 @@ new dictionary types that may not have complete dictionary APIs:</p> <dt>dict-map->list</dt> <dd>dict-fold</dd> - <dt>dict->alist</dt> <dd>dict-map->list</dd> - <dt>dict-for-each<</dt> - <dd>dict-for-each</dd> - - <dt>dict-for-each<=</dt> - <dd>dict-for-each</dd> - <dt>dict-for-each></dt> <dd>dict-for-each</dd> <dt>dict-for-each>=</dt> <dd>dict-for-each</dd> - <dt>dict-for-each-in-open-interval</dt> - <dd>dict-for-each</dd> - - <dt>dict-for-each-in-closed-interval</dt> - <dd>dict-for-each</dd> - - <dt>dict-for-each-in-open-closed-interval</dt> - <dd>dict-for-each</dd> - - <dt>dict-for-each-in-closed-open-interval</dt> - <dd>dict-for-each</dd> - - <dt>make-dict-generator</dt> + <dt>dict->generator</dt> <dd>dict-entries</dd> <dt>dict-set-accumulator</dt> |