summaryrefslogtreecommitdiffstats
path: root/srfi-225.html
diff options
context:
space:
mode:
authorGravatar John Cowan 2021-10-04 18:37:17 -0400
committerGravatar John Cowan 2021-10-04 18:37:17 -0400
commitb587db3508c77ba7625a01d7ba5d2ce1e0b58987 (patch)
tree3e560aac621d865f6d0e362999717d11a221ea53 /srfi-225.html
parentresolved against upstream (diff)
cleanup
Diffstat (limited to 'srfi-225.html')
-rw-r--r--srfi-225.html59
1 files changed, 22 insertions, 37 deletions
diff --git a/srfi-225.html b/srfi-225.html
index 86aa538..b715ec5 100644
--- a/srfi-225.html
+++ b/srfi-225.html
@@ -52,20 +52,16 @@ that does not provide it, or either procedure on top of an unordered dictionary.
<p>A <em>dict</em> is a collection of associations which may be ordered or unordered. In principle an <em>equality predicate</em> is enough, given a key, to 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 <em>similar</em>g 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. Unlike the mutation operations provided by Common Lisp, plists are functionally updated. The equality predicate of this type of dictionary is <code>eq?</code>.</p>
-<p>If a list is empty or its car is a pair, then the list can be treated as an alist. 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>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. Unlike the mutation operations provided by Common Lisp, plists in this SRFI are functionally updated. The equality predicate of this type of dictionary is <code>eq?</code>. If a key to be added already exists in dictionary, the new value prevails.</p>
+<p>If a list is empty or its car is a pair, then the list is assumed to be an alist. 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>However, an alist (unlike a hashtable or mapping) does not know which equality predicate its users intend to use on it. Therefore, rather than exporting a single DTD for all alists, this SRFI provides a procedure <code>make-alist-dtd</code> that takes an equality predicate and returns a DTD specialized for manipulation of alists using that predicate. For convenience, DTDs for <code>eqv?</code> and <code>equal?</code> are exported.</p>
-<p>In all other cases, lists cannot be treated as dictionaries unless a DTD has been written to handle them.</p>
-<h3>Procedures</h3>
<p>Each of the following examples is assumed to be prefixed by the following definitions:</p>
<blockquote><pre>(define dict (list '(1 . 2) '(3 . 4) '(5 . 6)))
(define aed alist-eqv-dtd)
</pre></blockquote>
Consequently, previous examples don't affect later ones.
-<p>The <em>dtd</em> argument is not discussed in the individual procedure descriptions below, but it is an error if invoking <code>dictionary?</code> on <em>dtd</em> and <em>dict</em> returns <code>#f</code>.</p>
-<h4 id="predicates">Predicates</h4>
+<p>The <em>dtd</em> argument is not discussed in the individual procedure descriptions below, but it is an error if invoking <code>dictionary?</code> on <em>dtd</em> and <em>dict</em> would return <code>#f</code>.</p>
+<h3 id="predicates">Predicates</h3>
<p><code>(dictionary?</code>&nbsp;<em>dtd obj</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>obj</em> answers <code>#t</code> to the type predicate stored in the DTD, and <code>#f</code> otherwise.</p>
<blockquote><pre>(dictionary? aed dict) =&gt; #t</pre></blockquote>
@@ -90,7 +86,7 @@ Consequently, previous examples don't affect later ones.
(dict-mutable? hash-table-dtd (make-hash-table)) => #t
(dict-mutable? aed dict) =>#f
</pre></blockquote>
-<h4 id="lookup">Lookup</h4>
+<h3 id="lookup">Lookup</h3>
<p><code>(dict-ref</code>&nbsp;<em>dtd dict key</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>
<p>If <em>key</em> is the same as some key of <em>dict</em>, then invokes <em>success</em> on the corresponding value and returns its result. If <em>key</em> is not a key of <em>dict</em>, then invokes the thunk <em>failure</em> and returns its result. The default value of <em>failure</em> signals an error; the default value of <em>success</em> is the identity procedure.</p>
<blockquote><pre>(dict-ref aed dict 1 (lambda () &#39;()) list) =&gt; (1) ; Success wraps value in a list
@@ -106,7 +102,7 @@ Consequently, previous examples don't affect later ones.
(dict-min-key aed dict) => 1
(dict-max-key aed dict) => 5
</pre></blockquote>
-<h4 id="mutation">Functional update and mutation</h4>
+<h3 id="mutation">Functional update and mutation</h3>
<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 the result may share structure with the <em>dict</em> argument. The ones with <code>!</code> are mutations: they they change the <em>dict</em> argument. However, only one set of procedures is supported in any dictionary: for example, SRFI 125 hash tables support only mutation, whereas SRFI 146 mappings support only functional update. The <code>dict-mutable?</code> procedure can be used to determine which set is usable.</p>
<p><code>(dict-set</code>&nbsp;<em>dtd dict obj</em> …<code>)</code><br>
<code>(dict-set!</code>&nbsp;<em>dtd dict obj</em> …<code>)</code></p>
@@ -162,7 +158,6 @@ Otherwise, returns two values, a dictionary that contains all the associations o
<code>(dict-map!</code>&nbsp;<em>dtd proc dict</em><code>)</code></p>
<p>Returns a dictionary similar to <em>dict</em> that maps each key of <em>dict</em> to the value that results from invoking <em>proc</em> on the corresponding key and value of <em>dict</em>.</p>
<blockquote><pre>(dict-map (lambda (k v) (cons v k)) aed dict) =&gt; ((2 . 1) (4 . 3) (6 . 5))</pre></blockquote>
-<blockquote><pre>(dict-map! (lambda (k v) (cons v k)) aed dict) =&gt; ((2 . 1) (4 . 3) (6 . 5))</pre></blockquote>
<p><code>(dict-filter</code>&nbsp;<em>dtd pred dict</em><code>)</code><br>
<code>(dict-filter!</code>&nbsp;<em>dtd pred dict</em><code>)</code><br>
<code>(dict-remove</code>&nbsp;<em>dtd pred dict</em><code>)</code><br>
@@ -175,16 +170,6 @@ Otherwise, returns two values, a dictionary that contains all the associations o
<p>This procedure is a workhorse for dictionary lookup, insert, and delete. The dictionary <em>dict</em> is searched for an association whose key is the same as <em>key</em>. If one is not found, then the <em>failure</em> procedure is tail-called with two procedure arguments, <em>insert</em> and <em>ignore</em>.</p>
<p>If such an association is found, then the <em>success</em> procedure is tail-called with the matching key of <em>dict</em>, the associated value, and two procedure arguments, <em>update</em> and <em>remove</em>.</p>
<p>In either case, the values returned by <em>failure</em> or <em>success</em> are returned.</p>
-<code>(dict-remove!</code>&nbsp;<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 / 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) =&gt; ((1 . 2))
-(dict-remove (lambda (k) (= k 1)) aed dict) =&gt; ((3 . 4) (5 . 6))</pre></blockquote>
-<p><code>(dict-search</code>&nbsp;<em>dtd dictionary key failure success</em><code>)</code><br>
-<code>(dict-search!</code>&nbsp;<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>
-<p>The behaviors of the procedures are as follows (where <em>obj</em> is any Scheme object):</p>
<ul>
<li><p>Invoking <code>(</code><em>insert value</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, and in addition a new association that maps <em>key</em> to <em>value</em>.</p></li>
<li><p>Invoking <code>(</code><em>ignore</em><code>)</code> has no effects and returns <em>dict</em> unchanged.</p></li>
@@ -235,7 +220,7 @@ one for each of the four procedures:
(delete))))
(dict->alist aed dict)) => ((c . d))
</pre></blockquote>
-<h4 id="the-whole-dictionary">The whole dictionary</h4>
+<h3 id="the-whole-dictionary">The whole dictionary</h3>
<p><code>(dict-size</code>&nbsp;<em>dtd dict</em><code>)</code></p>
<p>Returns an exact integer representing the number of associations in <em>dict</em>.</p>
<blockquote><pre>(dict-size aed dict) =&gt; 3</pre></blockquote>
@@ -283,30 +268,30 @@ and <code>dict-alter</code>.
<p><code>(dict-comparator</code>&nbsp;<em>dtd dict</em><code>)</code></p>
<p>Return a comparator representing the type predicate, equality predicate, ordering predicate, and hash function of <em>dict</em>. The last two may be <code>#f</code> if the dictionary does not make use of these functions.</p>
<p>If no comparator is relevant to the dictionary type, returns <code>#f</code>.</p>
-<h4 id="iteration">Iteration</h4>
+<h3 id="iteration">Iteration</h3>
<p><code>(dict-for-each</code>&nbsp;<em>dtd proc dict</em><code>)</code></p>
<p>Invokes <em>proc</em> on each key of <em>dict</em> and its corresponding value in that order. This procedure is used for doing operations on the whole dictionary. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. Returns an unspecified value.</p>
<blockquote><pre>(define (write-key key value) (write key))
(dict-for-each write-key aed dict) =&gt; unspecified
; writes &quot;135&quot; to current output</pre></blockquote>
-<p><code>(dict-for-each&lt;</code>&nbsp;<em>dtd proc dictionary key</em><code>)</code><br>
-<code>(dict-for-each&lt;=</code>&nbsp;<em>dtd proc dictionary key</em><code>)</code><br>
-<code>(dict-for-each&gt;</code>&nbsp;<em>dtd proc dictionary key</em><code>)</code><br>
-<code>(dict-for-each&gt;=</code>&nbsp;<em>dtd proc dictionary key</em><code>)</code></p>
+<p><code>(dict-for-each&lt;</code>&nbsp;<em>dtd proc dict key</em><code>)</code><br>
+<code>(dict-for-each&lt;=</code>&nbsp;<em>dtd proc dict key</em><code>)</code><br>
+<code>(dict-for-each&gt;</code>&nbsp;<em>dtd proc dict key</em><code>)</code><br>
+<code>(dict-for-each&gt;=</code>&nbsp;<em>dtd proc dict key</em><code>)</code></p>
<p>Invokes <em>proc</em> on each key of <em>dict</em> that is less than / less than or equal to / greater than / greater than or equal to <em>key</em> and its corresponding value. This procedure is used for doing operations on part of the dictionary. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. Returns an unspecified value.</p>
-<p><code>(dict-for-each-in-open-interval</code>&nbsp;<em>dtd proc dictionary key1 key2</em><code>)</code><br>
-<code>(dict-for-each-in-closed-interval</code>&nbsp;<em>dtd proc dictionary key1 key2</em><code>)</code><br>
-<code>(dict-for-each-in-open-closed-interval</code>&nbsp;<em>dtd proc dictionary key1 key2</em><code>)</code><br>
-<code>(dict-for-each-in-closed-open-interval</code>&nbsp;<em>dtd proc dictionary key1 key2</em><code>)</code></p>
+<p><code>(dict-for-each-in-open-interval</code>&nbsp;<em>dtd proc dict key1 key2</em><code>)</code><br>
+<code>(dict-for-each-in-closed-interval</code>&nbsp;<em>dtd proc dict key1 key2</em><code>)</code><br>
+<code>(dict-for-each-in-open-closed-interval</code>&nbsp;<em>dtd proc dict key1 key2</em><code>)</code><br>
+<code>(dict-for-each-in-closed-open-interval</code>&nbsp;<em>dtd proc dict key1 key2</em><code>)</code></p>
<p>Invokes <em>proc</em> on each key of <em>dict</em> that is that is within the specified interval between <em>key1</em> and <em>key2</em>, and its corresponding value. This procedure is used for doing operations on part of the dictionary. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. Returns an unspecified value.</p>
-<h4 id="generator procedures">Generator procedures</h4>
+<h3 id="generator procedures">Generator procedures</h3>
<p><code>(make-dict-generator</code>&nbsp;<em>dtd dict</em><code>)</code></p>
<p>Returns a <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">generator</a> that when invoked returns the associations of <em>dict</em> as pairs. When no associations are left, returns an end-of-file object. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order.</p>
<p><code>(dict-set-accumulator</code>&nbsp;<em>dtd dict</em><code>)</code></p>
-<p>Returns a procedure that when invoked with a pair adds the car and cdr of the pair as a key and value. If a key to be added already exists in dictionary, the new value prevails.</p>
+<p>Returns a procedure that when invoked on a pair adds the car and cdr of the pair as a key and value. If a key to be added already exists in dictionary, the new value prevails.</p>
<p><code>(dict-adjoin-accumulator</code>&nbsp;<em>dtd dict</em><code>)</code></p>
-<p>Returns a procedure that when invoked with a pair adds the car and cdr of the pair as a key and value. If a key to be added already exists in dictionary, the old value prevails.</p>
-<h4 id="dictionary-type-descriptor-procedures">Dictionary type descriptor procedures</h4>
+<p>Returns a procedure that when invoked on a pair adds the car and cdr of the pair as a key and value. If a key to be added already exists in dictionary, the old value prevails.</p>
+<h3 id="dictionary-type-descriptor-procedures">Dictionary type descriptor procedures</h3>
<p><code>(dtd?</code>&nbsp;<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>&nbsp;<em>arg</em> …<code>)</code><br>
@@ -372,7 +357,7 @@ Note that it is not an error to omit any of these, but some dictionary procedure
<p><code>(dtd-ref</code>&nbsp;<em>dtd proc-id</em><code>)</code></p>
<p>Returns the procedure designated by <em>proc-id</em> from <em>dtd</em>.
This allows the ability to call a particular DTD procedure multiple times more efficiently.</p>
-<h4 id="exceptions">Exceptions</h4>
+<h3 id="exceptions">Exceptions</h3>
<p><code>(dictionary-error</code>&nbsp;<em>message irritant</em> ... <code>)</code></p>
<p>Returns a dictionary error with the given <em>message</em> (a string) and
<em>irritants</em> (any objects).
@@ -385,7 +370,7 @@ and <code>#f</code> otherwise.
<p>Returns the message associated with <em>dictionary-error.</em></p>
<p><code>(dictionary-irritants</code>&nbsp;<em>dictionary-error</em><code>)</code></p>
<p>Returns a list of the irritants associated with <em>dictionary-error</em>.</p>
-<h4 id="exported-dtds">Exported DTDs</h4>
+<h3 id="exported-dtds">Exported DTDs</h3>
<p>The following DTDs are exported from this SRFI:
<code>srfi-69-dtd</code>, <code>hash-table-dtd</code>, <code>srfi-126-dtd</code>,
<code>mapping-dtd</code>, <code>hash-mapping-dtd</code>, <code>plist-dtd</code>,