<p><code>(dictionary?</code>&nbsp;<em>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 dict &#39;((1 . 2) (3 . 4) (5 . 6)))

<p><code>(dict-empty?</code>&nbsp;<em>dictionary</em><code>)</code></p>

<p>Returns <code>#t</code> if <em>dictionary</em> contains no associations and <code>#f</code> if it does contain associations.</p>

<blockquote><pre>(dict-empty? &#39;()) =&gt; #t

<p><code>(dict-contains?</code>&nbsp;<em>dictionary key</em><code>)</code></p>

<blockquote><pre>(dict-contains? dict 1) =&gt; #t

<p>Returns <code>#t</code> if one of the keys of <em>dictionary</em> is the same as <em>key</em>, and <code>#f</code> otherwise.</p>

<h3 id="lookup">Lookup</h3>

<p><code>(dict-ref</code>&nbsp;<em>dictionary key</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>

<p>If <em>key</em> is the same as some key of <em>dictionary</em>, then invokes <em>success</em> on the corresponding value and returns its result. If <em>key</em> is not a key of <em>dictionary</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 dict 1 (lambda () &#39;()) list) =&gt; (1) ; Success wraps value in a list

<p><code>(dict-ref/default</code>&nbsp;<em>dictionary key default</em><code>)</code></p>

<p>If <em>key</em> is the same as some key of <em>dictionary</em> then returns the corresponding value. If not, then returns <em>default</em>.</p>

<blockquote><pre>(dict-ref/default dict 1 #f) =&gt; 1

<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>&nbsp;<em>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 old value prevails.</p>

<blockquote><pre>; new values are prepended

(dict-adjoin! dict 7 8) =&gt; ((7 . 8) (1 . 2) (3 . 4) (5 . 6))

<p><code>(dict-delete!</code>&nbsp;<em>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! dict 1 3) =&gt; ((5. 6)) ; may share

<p><code>(dict-delete-all!</code>&nbsp;<em>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>

<p><code>(dict-replace!</code>&nbsp;<em>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>

<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! dict 1 (lambda () #f)) =&gt; ; 2 values

3

(dict-intern! dict 2 (lambda () #f)) =&gt; ; 2 values

((2 . #f) (1 . 2) (3 . 4) (5 . 6))

<p><code>(dict-update!</code>&nbsp;<em>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>&nbsp;<em>dictionary key updater default</em><code>)</code></p>

<blockquote><pre>(dict-pop! dict) =&gt; # 3 values

((3 . 4) (5 . 6))

1

<p><code>(dict-map!</code>&nbsp;<em>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>

<p><code>(dict-filter!</code>&nbsp;<em>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>

<p><code>(dict-remove!</code>&nbsp;<em>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>

<p><code>(dict-search!</code>&nbsp;<em>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>’s comparator. If one is not found, then the <em>failure</em> procedure is tail-called with two continuation 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 continuation arguments, <em>update</em> and <em>remove</em>, and is expected to tail-call one of them.</p>

<h3 id="the-whole-dictionary">The whole dictionary</h3>

<p><code>(dict-size</code>&nbsp;<em>dictionary</em><code>)</code></p>

<p>Returns an exact integer representing the number of associations in <em>dictionary</em>.</p>

<p><code>(dict-for-each</code>&nbsp;<em>proc dictionary</em><code>)</code></p>

<p>Invokes <em>proc</em> on each key of <em>dictionary</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>(dict-for-each write dict) =&gt; unspecified

<p><code>(dict-count</code>&nbsp;<em>pred dictionary</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><code>(dict-any</code>&nbsp;<em>pred dictionary</em><code>)</code></p>

<p>Passes each association of <em>dictionary</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 the inherent 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 both-even? &#39;((2 . 4) (3 . 5))) =&gt; #t

<p><code>(dict-every</code>&nbsp;<em>pred dictionary</em><code>)</code></p>

<p>Passes each association of <em>dictionary</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 the inherent 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 some-even? &#39;((2 . 3) (3 . 4))) =&gt; #t

<p><code>(dict-keys</code>&nbsp;<em>dictionary</em><code>)</code></p>

<p>Returns a list of the keys of <em>dictionary</em>. If the dictionary type is inherently ordered, associations are processed in the inherent order; otherwise in an arbitrary order. The order may change when new elements are added to <em>dictionary</em>.</p>

<p><code>(dict-values</code>&nbsp;<em>dictionary</em><code>)</code></p>

<p>Returns a list of the values of <em>dictionary</em>. The results returned by <code>dict-keys</code> and <code>dict-values</code> are ordered consistently.</p>

<p><code>(dict-entries</code>&nbsp;<em>dictionary</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>dictionary</em>.</p>

<blockquote><pre>(dict-entries dict) =&gt; ; 2 values

(1 3 5)

<p><code>(dict-fold</code>&nbsp;<em>proc knil dictionary</em><code>)</code></p>

<p>Invokes <em>proc</em> on each association of <em>dictionary</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.</p>

<p><code>(dict-map-&gt;list</code>&nbsp;<em>proc dictionary</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>dictionary</em>.</p>

<p><code>(dict-&gt;alist</code>&nbsp;<em>dictionary</em><code>)</code></p>

<p>Returns an alist whose keys and values are the keys and values of <em>dictionary</em>.</p>

<blockquote><pre>; plist to alist

<h3 id="registering-dictionary-types">Registering dictionary types</h3>

<p>The following procedure registers new dictionary types. It is an error to register a dictionary type whose instances return <code>#t</code> to any predicate already registered.</p>

<p><code>(register-dictionary-type!</code>&nbsp;<em>arg</em> …<code>)</code></p>

'dict-size alist-size

'dict-for-each alist-foreach

'dict->alist alist->alist))

<h2 id="implementation">Implementation</h2>

<p>The sample implementation is found in the GitHub repository.</p>