This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home.
Source for wiki ImmutableDataStructuresWortman version 24
author
cowan
comment
ipnr
127.11.51.1
name
ImmutableDataStructuresWortman
readonly
0
text
== Introduction ==
This proposal defines ''immutable data structures'' for queues, sets, bags, and maps. A structure is immutable when all its operations leave the structure unchanged. Note that none of the procedures specified here ends with a `!`.
Immutable structures are sometimes called ''persistent'' and are closely related to ''pure-functional'' (a.k.a. ''pure'') structures. The availability of immutable data structures facilitates writing efficient programs in the pure-functional style.
== Efficiency bounds ==
We specify required time efficiency upper bounds using big-O notation. We note when, in some cases, there is "slack" between the required bound and the theoretically optimal bound for an operation. Implementations may use data structures with amortized time bounds, but should document which bounds hold in only an amortized sense. The use of randomized data structures with expected time bounds is discouraged.
== Disjoint types ==
Deques, sets, bags, and maps are disjoint from all other Scheme types, and deques are disjoint from the other types.
== Deques ==
A deque (conventionally pronounced "deck") is a queue data structure that supports efficient manipulation of either of its ends. It may be used in place of a (LIFO) stack or (FIFO) queue.
The ''unlabeled finger tree'' data structure can meet all these requirements rather conveniently. A pair of lists is also a suitable implementation.
=== Construction ===
`(ideque `[ ''element'' ...]`)`
Returns a deque containing the ''elements''. The leftmost element (if any) will be at the front of the deque and the rightmost element (if any) will be at the back. Takes O(n) time, where ''n'' is the number of elements.
`(ideque-tabulate `''n proc''`)`
Invokes ''proc'' successively on the integers 0 through ''n'' - 1 inclusive, and returns a deque containing the results in the given order. Takes O(n) time.
`(ideque-unfold `''stop? mapper successor seed''`)`
Invokes the predicate ''stop?'' on ''seed''. If it returns false, generate the next result by applying ''mapper'' to ''seed'', generate the next seed by applying ''successor'' to ''seed'', and repeat this algorithm with the new seed. If ''stop?'' returns true, return a deque containing the results in order of accumulation. Takes O(n) time.
`(ideque-unfold-right `''stop? mapper successor seed''`)`
Invokes the predicate ''stop?'' on ''seed''. If it returns false, generate the next result by applying ''mapper'' to ''seed'', generate the next seed by applying ''successor'' to ''seed'', and repeat the algorithm with the new seed. If ''stop?'' returns true, return a deque containing the results in reverse order of accumulation. Takes O(n) time.
=== Predicates ===
`(ideque? `''x''`)`
Returns `#t` if ''x'' is a deque, and `#f` otherwise. Takes O(1) time.
`(ideque-empty? `''deque''`)`
Returns `#t` if ''deque'' contains zero elements, and `#f` otherwise. Takes O(1) time.
=== Queue operations ===
`(ideque-front `''deque''`)`
`(ideque-back `''deque''`)`
Returns the front/back element of ''deque''. It is an error for ''deque'' to be empty. Each takes O(1) time.
`(ideque-remove-front `''deque''`)`
`(ideque-remove-back `''deque''`)`
Returns a deque with the front/back element of ''deque'' removed. It is an error for ''deque'' to be empty. Each takes O(1) time.
`(ideque-add-front `''deque obj''`)`
`(ideque-add-back `''deque obj''`)`
Returns a deque with ''obj'' pushed to the front/back of ''deque''. Each takes O(1) time.
=== Other accessors ===
`(ideque-take `''deque n''`)`
`(ideque-take-right `''deque n''`)`
Returns a deque containing the first/last ''n'' elements of ''deque''. Takes O(n) time.
`(ideque-drop `''deque n''`)`
`(ideque-drop-right `''deque n''`)`
Returns a deque containing all but the first/last ''n'' elements of ''deque''. Takes O(n) time.
`(ideque-split-at `''deque n''`)`
Returns two values, the results of `(ideque-take `''deque n''`)` and `(ideque-drop `''deque n''`)` respectively, but may be more efficient. Takes O(n) time.
=== The whole deque ===
`(ideque-length `''deque''`)`
Returns the length of ''deque'' as an exact integer. May take O(n) time, though O(1) is optimal.
`(ideque-append `''deque'' ...`)`
Returns a deque with the contents of the first argument deque followed by the others. Takes O(kn) time, where k is the number of deques and n is the number of elements involved, though O(k log n) is possible.
`(ideque-concatenate `''list-of-deques''`)`
Returns a deque with the contents of the first deque in ''list-of-deques'' followed by the others. This is provided for Schemes in which the number of arguments which can be passed to `apply` is limited. Takes O(kn) time, where k is the number of deques and n is the number of elements involved, though O(k log n) is possible.
`(ideque-reverse `''deque''`)`
Returns a deque containing the elements of ''deque'' in reverse order. Takes O(n) time.
`(ideque-count `''pred deque''`)`
Returns the number of elements of ''deque'' which satisfy ''pred'' as an exact integer. Takes O(n) time.
`(ideque-zip `''deque'' ...`)`
Returns a deque of lists (not deques) each of which contains the corresponding elements of the argument deques in the order specified. Processing stops when all the elements of any deque have been seen. Takes O(kn) time, where ''k'' is the number of deques and ''n'' is the number of elements involved.
=== Mapping ===
`(ideque-map `''proc deque'' ...`)`
Applies ''proc'' to the corresponding elements of ''deques'' and returns a deque containing the results in order. Terminates when any deque is finished. Takes O(n) time.
`(ideque-for-each `''proc deque'' ...`)`
Applies ''proc'' to the corresponding elements of ''deques'' in order and returns an unspecified result. Terminates when any deque is finished. Takes O(n) time.
`(ideque-fold `''proc nil deque'' ...`)`
`(ideque-fold-right `''proc nil deque'' ...`)`
Invokes ''proc'' on the corresponding elements of ''deques'' in forward/reverse order, passing the result of the previous invocation as a second argument. For the first invocation, ''nil'' is used as the second argument. Returns the result of the last invocation, or ''nil'' if there was no invocation. Terminates when any deque is finished. Takes O(n) time.
`(ideque-append-map `''proc deque'' ...`)`
Applies ''proc'' to the corresponding elements of ''deques''. It is an error if the result is not a list. Returns a deque containing the elements of the lists in order. Terminates when any deque is finished. Takes O(n) time.
=== Filtering ===
`(ideque-filter `''pred deque''`)`
`(ideque-remove `''pred deque''`)`
Returns a deque which contains the elements of ''deque'' that do/do not satisfy ''pred''. Takes O(n) time.
`(ideque-partition `''proc deque''`)`
Returns two values, the results of `(ideque-filter `''pred deque''`)` and `(ideque-remove `''pred deque''`)` respectively, but may be more efficient. Takes O(n) time.
=== Searching ===
`(ideque-find `''pred deque failure''`)`
`(ideque-find-right `''pred deque failure''`)`
Returns the first/last element of ''deque'' that satisfies ''pred''. If there is no such element, returns the result of invoking the thunk ''failure'' . Takes O(n) time.
`(ideque-take-while `''pred deque''`)`
`(ideque-take-while-right `''pred deque''`)`
Returns a deque containing the longest initial/final prefix of elements in ''deque'' all of which satisfy ''pred''. Takes O(n) time.
`(ideque-drop-while `''pred deque''`)`
`(ideque-drop-while-right `''proc deque''`)`
Returns a deque which omits the longest initial/final prefix of elements in ''deque'' all of which satisfy ''pred'', but includes all other elements of ''deque''. Takes O(n) time.
`(ideque-span `''pred deque''`)`
`(ideque-break `''pred deque''`)`
Returns two values, the initial prefix of the elements of ''deque'' which do/do not satisfy ''pred'', and the remaining elements. Takes O(n) time.
`(ideque-any `''pred deque''`)`
`(ideque-every `''pred deque''`)`
Invokes ''pred'' on the elements of ''deque'' in order until one of them returns a true/false value, which is then returned. If there are no such elements, returns `#f`/`#t`. Takes O(n) time.
=== Conversion ===
`(list->ideque `''list''`)`
`(ideque->list `''deque''`)`
Conversion between deque and list structures. FIFO order is preserved, so the front of a list corresponds to the front of a deque. Each operation takes O(n) time.
`(generator->ideque `''generator''`)
`(ideque->generator `''ideque''`)`
Converts a [http://srfi.schemers.org/srfi-121/srfi-121.html SRFI 121] generator to and from a deque.
=== Comparator ===
`ideque-comparator`
A comparator suitable for comparing ideques listwise (that is, if one ideque is a prefix of the other, it precedes it). Elements are compared with `default-comparator`.
`(make-ideque-comparator `''comparator''`)`
Returns a comparator with the same behavior as `ideque-comparator`, except that elements are compared with ''comparator''.
== Sets ==
A sorted set data structure stores a finite collection of unique elements with a defined [http://ccil.org/~cowan/temp/srfi-114.html comparator]. It is an error if the comparator does not provide a comparison procedure.
These requirements can be satisfied by many flavors of ''self-balancing binary trees.'' Red-black trees, 1-2 brother trees, and labeled 2-3 finger trees are particularly convenient in an immutable context.
=== Construction ===
If two elements are inserted into a set that are equal in the sense of the set's comparator but are not `eqv?`, the first to be specified or generated prevails.
`(iset `''comparator'' [ ''element'' ...]`)`
Returns a set containing ''elements'', where ''comparator'' provides the criterion of identity and ordering. Takes O(n log n) time.
`(iset-tabulate `''n proc''`)`
Invokes ''proc'' successively on the integers 0 through ''n'' - 1 inclusive, and returns a set containing the results. Takes O(n log n) time.
`(iset-unfold `''stop? mapper successor seed''`)`
Invokes the predicate ''stop?'' on ''seed''. If it returns false, generate the next result by applying ''mapper'' to ''seed'', generate the next seed by applying ''successor'' to ''seed'', and repeat this algorithm with the new seed. If ''stop?'' returns true, return a set containing the results. Takes O(n log n) time.
=== Predicates ===
`(iset? `''obj''`)`
Returns `#t` if ''obj'' is a set, and `#f` otherwise. Takes O(1) time.
`(iset-empty? `''set''`)`
Returns `#t` if ''set'' contains zero elements, and `#f` otherwise. Takes O(1) time.
`(iset-member? `''set obj''`)`
Returns `#t` if ''set'' contains ''obj'', and `#f` otherwise. Takes O(log n) time.
=== Accessors ===
`(iset-min `''set''`)`
`(iset-max `''set''`)`
Returns the least/greatest element of ''set''. It is an error for ''set'' to be empty. Takes O(log n) time; O(1) is optimal.
`(iset-comparator `''set''`)`
Returns the comparator of ''set''. Takes O(1) time.
`(iset-predecessor `''set obj failure''`)`
`(iset-successor `''set obj failure''`)`
Returns the element that immediately precedes/succeeds ''obj'' in ''set's'' ordering. If no such element exists because ''obj'' is the minimum/maximum element, or because ''set'' is empty, returns the result of invoking the thunk ''failure''. Takes O(log n) time.
=== Functional update ===
`(iset-adjoin `''set obj''`)`
Returns a set which contains the elements of ''set'' and ''obj'' as well. If there is already an element of ''set'' that is equal (in the sense of the comparator) to ''obj'', the existing element of ''set'' prevails. Takes O(log n) time.
`(iset-adjoin-all `''set list''`)`
Returns a set which contains the elements of ''set'' and the elements of ''list'' as well. It is an error if the elements of ''list'' are not distinct and increasing in the sense of the comparator of ''set''. If there is already an element of ''set'' which is equal (in the sense of the comparator) to an element of ''list'', the element of ''set'' prevails. Takes O(k log n) time, where ''k'' is the length of ''list''.
`(iset-replace `''set obj''`)`
Returns a set which contains the elements of ''set'' and ''obj'' as well. If there is already an element of ''set'' that is equal (in the sense of the comparator) to ''obj'', ''obj'' prevails. Takes O(log n) time.
`(iset-delete `''set obj''`)`
Returns a set which contains the elements of ''set'' with the exception of ''obj'', if present. If there is already an element of ''set'' that is equal (in the sense of the comparator) to ''obj'', the element of ''set'' prevails. Takes O(log n) time.
`(iset-delete-all `''set list''`)`
Returns a set which contains the elements of ''set'', excluding the elements of ''list''. It is an error if the elements of ''list'' are not distinct and increasing in the sense of the comparator of ''set''. Takes O(k log n) time, where ''k'' is the length of ''list''.
=== The whole set ===
`(iset-size `''set''`)`
Returns the size of ''set'' as an exact integer. May take O(n) time, though O(1) is optimal.
`(iset-find `''set obj failure''`)`
Returns the element equal (in the sense of the comparator of ''set'') to ''obj'' in ''set'', or the result of invoking the thunk ''failure'' if no such element exists. Takes O(log n) time.
`(iset-count `''pred set''`)`
Returns the number of elements in ''set'' which satisfy ''pred'' as an exact integer. Takes O(n) time.
`(iset-any `''pred set''`)`
`(iset-every `''pred set''`)`
Invokes ''pred'' on the elements of ''set'' until one of them returns a true/false value, which is then returned. If there are no such elements, returns `#f`/`#t`. Takes O(n) time.
=== Filtering ===
`(iset-range= `''set obj''`)`
`(iset-range< `''set obj''`)`
`(iset-range> `''set obj''`)`
`(iset-range<= `''set obj''`)`
`(iset-range>= `''set obj''`)`
Returns a set containing only the elements of `set` that are equal to / less than / greater than / less than or equal to / greater than or equal to ''obj''. Takes O(log n) time, where n is the number of elements in the set.
Note that since set elements are unique, `iset-range=` returns a set of at most one element.
`(iset-filter `''pred set''`)`
`(iset-remove `''pred set''`)`
Returns a set containing only those elements on which ''pred'' returns true/false. Takes O(n log n) time; O(n) is optimal.
`(iset-partition`''pred set''`)`
Returns two values, `(iset-filter `''pred set''`)` and `(iset-remove `''pred set''`)` respectively, but may be more efficient.
=== Folding and mapping ===
`(iset-fold `''proc nil set''`)`
The fundamental set iterator. Equivalent to, but may be more efficient than, `(fold `''proc base'' ` (iset->increasing-list `''set''`))`. Takes O(n) time.
`(iset-fold-right `''proc nil set''`)`
The fundamental set iterator. Equivalent to, but may be more efficient than, `(fold-right `''proc base'' ` (iset->increasing-list `''set''`))`. Takes O(n) time.
`(iset-map/monotone `''proc set'' [ ''comparator'' ]`)`
Returns a set containing the result of invoking ''proc'' on every element in ''set''. It is an error unless ''proc'' is a ''monotone'' unary procedure that preserves the order of set elements. Observe that mapping a set of unique elements with a monotone function yields a set of unique elements, so element uniqueness follows from the monotonicity assumption. If ''comparator'' is given, it is the comparator of the result; otherwise the result uses the same comparator as ''set''. Takes O(n) time.
`(iset-map`''proc set'' [ ''comparator'' [ ''merger'' ] ]`)`
Like `iset-map/monotone`, except that ''proc'' is not required to be monotone. The `merger` procedure is used to select among any duplicate elements (in the sense of the comparator of ''set'') that might be created; it returns the value to be used; if absent, the element chosen is implementation-specific. Takes O(n log n) time.
`(iset-for-each `''proc set''`)`
Invokes ''proc'' on every ''element'' in ''set''. The result is unspecified. Takes O(n) time.
=== Subsets ===
Note: The following three predicates do not obey the trichotomy law and therefore do not constitute a total order on sets.
`(iset=? `''set1 set2'' ...`)`
Returns `#t` if each ''set'' contains the same elements, and `#f` otherwise.
`(iset<? `''set1 set2'' ...`)`
Returns `#t` if each ''set'' other than the last is a proper subset of the following set, and `#f` otherwise.
`(iset>? `''set1 set2'' ...`)`
Returns `#t` if each ''set'' other than the last is a proper superset of the following set, and `#f` otherwise.
`(iset<=? `''set1 set2'' ...`)`
Returns `#t` if each ''set'' other than the last is a subset of the following set, and `#f` otherwise.
`(iset>=? `''set1 set2'' ...`)`
Returns `#t` if each ''set'' other than the last is a superset of the following set, and `#f` otherwise.
=== Conversion ===
`(iset->list `''set''`)`
Returns a list containing the elements of `set` in increasing order. Takes O(n) time.
`(increasing-list->iset comparator list)`
Returns a set containing the elements of ''list'' and using ''comparator''. It is an error for ''list'' to be anything other than a proper list of elements in increasing order. Takes O(n log n) time; O(n) is optimal.
`(list->iset `''comparator list [ ''merger'' ]`)`
Returns a set containing the elements of ''list'' and using ''comparator''. It is an error if `list` is not a proper list, but it may contain duplicates and need not be in order. The `merger` procedure is used to select among any duplicate elements (in the sense of the comparator of ''set'') that might be created; it accepts the existing and new elements and returns the value to be used. Takes O(n log n) time.
`(generator->iset `''generator''`)
`(iset->generator `''iset''`)`
Converts a [http://srfi.schemers.org/srfi-121/srfi-121.html SRFI 121] generator to and from a set.
=== Set-theoretic operations ===
`(iset-union `''set'' ... `)`
`(iset-intersection `''set'' ... `)`
`(iset-difference `''set'' ... `)`
`(iset-xor `''set,,1,, set,,2,,''`)`
Returns a set containing the union/intersection/difference/symmetric difference of the arguments. All the arguments must be sets sharing an equivalent comparator. The set operator is applied in a left-associative order. If an element is found in more than one set, the first set in the argument list prevails. May take O(kn log n) time, where k is the number of sets and n is the number of elements involved, though O(kn) time is optimal.
== Bags ==
{{{
#!html
Bags are like sets, but can contain the same object more than once. However, if two elements that are the same in the sense of the comparator, but not in the sense of <code>eqv?</code>, are both included, it is not guaranteed that they will remain distinct when retrieved from the bag. It is an error for a single procedure to be invoked on bags with different comparators.
</p><p>
The procedures for creating and manipulating bags are the same as those for sets, except that <code>iset</code> is replaced by <code>ibag</code> in their names, and that adjoining an element to a bag is effective even if the bag already contains the element. If two elements in a bag are the same in the sense of the bag's comparator, the implementation may in fact store just one of them.
</p>
<p>The <code>ibag-union</code>, <code>ibag-intersection</code>, <code>ibag-difference</code>, and <code>ibag-xor</code> procedures behave as follows when both bags contain elements that are equal in the sense of the bags' comparator:</p>
<ul>
<li><p>For <code>bag-union</code>, the number of equal elements in the result is the largest number of equal elements in any of the original bags.</p></li>
<li><p>For <code>bag-intersection</code>, the number of equal elements in the result is the smallest number of equal elements in any of the original bags.</p></li>
<li><p>For <code>bag-difference</code>, the number of equal elements in the result is the number of equal elements in the first bag, minus the number of elements in the other bags (but not less than zero).</p></li>
<li><p>For <code>bag-xor</code>, the number of equal elements in the result is the absolute value of the difference between the number of equal elements in the first and second bags.</p></li></ul>
<h3 id="Additionalbagprocedures">Additional bag procedures</h3>
<p><code>(ibag-sum </code><em>set<sub>1</sub> set<sub>2</sub></em> ... <code>)</code></p>
<p>The <code>ibag-sum</code> procedure returns a bag containing all the unique elements in all the <em>bags</em>, such that the count of each unique element in the result is equal to the sum of the counts of that element in the arguments. It differs from <code>ibag-union</code> by treating identical elements as potentially distinct rather than attempting to match them up.</p>
<p><code>(ibag-product </code><em>n bag</em><code>)</code></p>
The <code>bag-product</code> procedure returns a bag containing all the unique elements in <em>bag</em>, where the count of each unique element in the bag is equal to the count of that element in <code>bag</code> multiplied by <em>n</em>.
</p><p><code>(ibag-unique-size </code><em>bag</em><code>)</code></p><p>
Returns the number of unique elements of <em>bag</em> as an exact integer.
</p><p><code>(ibag-element-count </code><em>bag element</em><code>)</code></p><p>
Returns an exact integer representing the number of times that <em>element</em> appears in <em>bag</em>.
</p><p><code>(ibag-for-each-unique </code><em>proc bag</em><code>)</code></p><p>
Applies <em>proc</em> to each unique element of <em>bag</em> in arbitrary order, passing the element and the number of times it occurs in <em>bag</em>, and discarding the returned values. Returns an unspecified result.
</p><p><code>(ibag-fold-unique </code><em>proc nil bag</em><code>)</code></p><p>
Invokes <em>proc</em> on each unique element of <em>bag</em> in arbitrary order, passing the number of occurrences as a second argument and the result of the previous invocation as a third argument. For the first invocation, <em>nil</em> is used as the third argument. Returns the result of the last invocation, or <em>nil</em> if there is none.
</p><p><code>(ibag-increment </code><em>bag<code> </code>element<code> </code>count</em><code>)</code></p><p><code>(ibag-decrement </code><em>bag<code> </code>element<code> </code>count</em><code>)</code></p><p>
Procedures that return a bag with the same elements as <em>bag</em>, but with the element count of <em>element</em> in <em>bag</em> increased or decreased by the exact integer <em>count</em> (but not less than zero).
</p><p><code>(ibag->iset </code><em>bag</em><code>)</code></p><p><code>(iset->ibag </code><em>set</em><code>)</code></p><p>
The <code>ibag->iset</code> procedure returns a set containing the unique elements (in the sense of the equality predicate) of <em>bag</em>. The <code>iset->ibag</code> procedure returns a bag containing the elements of <em>set</em>. In all cases, the comparator of the result is the same as the comparator of the argument or arguments.
</p><p><code>(ibag->alist </code><em>bag</em><code>)</code></p><p><code>(alist->ibag </code><em>comparator alist</em><code>)</code></p><p>
The <code>ibag->alist</code> procedure returns a newly allocated alist whose keys are the unique elements of <em>bag</em> and whose values are the number of occurrences of each element. The <code>alist->ibag</code> returning a bag based on <em>comparator</em>, where the keys of <em>alist</em> specify the elements and the corresponding values of <em>alist</em> specify how many times they occur.</p>
}}}
== Maps ==
A map data structure stores key-value associations from a map of keys with a comparator to arbitrary value objects. It is an alternative to an association list or hash table, which also store key-value associations, but with different key constraints and efficiency guarantees.
In the same way that a list of key-value dotted pairs can implement an association list, a set of key-value dotted pairs can implement a map. Implementations may use this approach, or may implement a distinct data structure specific to maps.
=== Construction ===
If two associations are to be inserted into a map that are equal in the sense of the map's comparator but are not `eqv?`, the first to be specified or generated prevails.
`(imap `''comparator'' ( ''key value'' ...]`)`
Returns a map using ''comparator''. For each pair of arguments, an association is added to the map with ''key'' as its key and ''value'' as its value. Takes O(n log n) time.
`(imap-tabulate `''n proc''`)`
Invokes ''proc'' successively on the integers 0 through ''n'' - 1 inclusive, and returns a map containing the results. Takes O(n log n) time.
`(imap-unfold `''stop? mapper successor seed''`)`
Invokes the predicate ''stop?'' on ''seed''. If it returns false, generate the next result by applying ''mapper'' to ''seed'', generate the next seed by applying ''successor'' to ''seed'', and repeat this algorithm with the new seed. If ''stop?'' returns true, return a map containing the results. Takes O(n log n) time.
=== Predicates ===
`(imap? `''obj''`)`
Returns `#t` if ''obj'' is a map, and `#f` otherwise. Takes O(1) time.
`(imap-empty? `''map''`)`
Returns `#t` if ''map'' contains zero associations, and `#f` otherwise. Takes O(1) time.
`(imap-contains? `''map obj''`)`
Returns `#t` if ''map'' contains ''obj'' as a key, and `#f` otherwise. Takes O(log n) time.
`(imap-key-not-found? `''obj''`)`
Returns '#t' if
=== Accessors ===
`(imap-ref `''map key'' [ ''failure'' [ ''success'' ] ]`)`
Extracts the value associated to ''key'' in ''map'', invokes the procedure ''success'' on it, and returns its result; if ''success'' is not provided, then the value itself is returned. Otherwise, `imap-ref` invokes the procedure ''failure'' on no arguments and returns its result; if ''failure'' is not provided, then an error that satisfies `imap-key-not-found?` is signaled. Takes O(log n) time.
`(imap-ref/default `''imap key default''`)`
Semantically equivalent to, but may be more efficient than, `(imap-ref `''map key'' `(lambda () `''default''`))`.
`(imap-min-key `''map''`)`
`(imap-max-key `''map''`)`
Returns the least/greatest key of ''map''. It is an error for ''map'' to be empty. Takes O(log n) time; O(1) is optimal.
`(imap-min-value `''map''`)`
`(imap-max-value`''map''`)`
Returns the value associated with the least/greatest key of ''map'' (''not'' the least/greatest value). It is an error for ''map'' to be empty. Takes O(log n) time; O(1) is optimal.
`(imap-comparator `''map''`)`
Returns the comparator of ''map''. Takes O(1) time.
`(imap-key-predecessor `''map obj failure''`)`
`(imap-key-successor `''map obj failure''`)`
Returns the key that immediately precedes/succeeds `obj` in `map`'s ordering. If no such association exists because ''obj'' is the minimum/maximum key, or because ''map'' is empty, returns the result of invoking the thunk ''failure''. Takes O(log n) time.
=== Functional update ===
`(imap-add `''map key value''`)`
Returns a map which contains the associations of ''map'' and an association with ''key'' and ''value'' as well. If there is already an association of ''map'' whose key is equal (in the sense of the comparator) to ''key'', the existing key prevails. Takes O(log n) time.
`(imap-add-all `''map key-list value-list''`)`
Returns a map which contains the associations of ''map'' and associations constructed from the corresponding associations of ''key-list'' and ''value-list'' as well. It is an error if the associations of ''key-list'' are not distinct and increasing in the sense of the comparator of ''map''. If there is already an association of ''map'' which is equal (in the sense of the comparator) to an association of ''list'', the key of ''map'' prevails. Takes O(k log n) time, where ''k'' is the length of ''list''.
`(imap-replace `''map key value''`)`
Returns a map which contains the associations of ''map'' and an association with ''key'' and ''value'' as well. If there is already an association of ''map'' whose key is equal (in the sense of the comparator) to ''key'', ''key'' prevails. Takes O(log n) time.
`(imap-delete `''map key''`)`
Returns a map which contains the associations of ''map'' with the exception of any association whose key is ''key''. If there is already an association of ''map'' whose key is equal (in the sense of the comparator) to ''key'', the existing key prevails. Takes O(log n) time.
`(imap-delete-keys `''map key-list''`)`
Returns a map which contains the associations of ''map'', excluding any associations whose keys appear in ''key-list''. It is an error if the associations of ''list'' are not distinct and increasing in the sense of the comparator of ''map''. Takes O(k log n) time, where ''k'' is the length of ''key-list''.
`(imap-push `''map key value''`)`
If an association with ''key'' is found in ''map'', then return a map with the value of ''key'' updated to the result of invoking `cons` on ''value'' and the original value. If the value is not found, an error satisfied by `imap-key-not-found?` is signaled. It is an error if the value is not a pair. Takes O(log n) time.
`(imap-pop `''map key''`)`
If an association with ''key'' is found in ''map'', then return two values, ''map'' with the value of ''key'' updated to the cdr of the original value, and the car of the original value. If the value is not found, an error satisfied by `imap-key-not-found?` is signaled. It is an error if the value is not a pair. Takes O(log n) time.
`(imap-search `''map obj failure success''`)`
A continuation-based universal update procedure. Attempts to find an association in ''map'' whose key is equal (in the sense of the comparator) to ''obj''. When such an association is found, `imap-search` calls ''(success key update remove)''. The ''success'' procedure either tail-calls '' (update new-value ret)'' to return a map that associates the matched key with ''new-value'', or else tail-calls ''(remove ret)'' to remove the matched association from ''map''.
When no such association is found, `imap-search` calls ''(failure insert ignore)'', which either tail-calls ''(insert new-value ret)'' to insert an association whose key is ''obj'' and whose value is ''new-value'' into ''map'', or else tail-calls ''(ignore ret)'' .`
In all cases, `imap-search` returns two values, a map reflecting the indicated modification (if any) and the value ''ret'' produced by one of the continuations. It runs in O(log n) time.
(This procedure is based on an analogous procedure for hash tables suggested by Alexey Radul and attributed to Taylor Campbell.)
=== The whole map ===
`(imap-size `''map''`)`
Returns the size of ''map'' as an exact integer. May take O(n) time, though O(1) is optimal.
`(imap-find `''map pred failure''`)`
For each association of ''map'', invoke ''proc'' on its key and value. If ''proc'' returns true on a value, then return that value. If all the calls to ''proc'' return `#f`, return the result of invoking the thunk ''failure''. Takes O(log n) time.
`(imap-count `''pred map''`)`
Returns the number of associations in ''map'' which satisfy ''pred'' as an exact integer. Takes O(n) time.
`(imap-any `''pred map''`)`
`(imap-every `''pred map''`)`
Invokes ''pred'' in order on the keys and values of ''map'', passing a key and a value to each invocation, until one of them returns a true/false value, which is then returned. If there are no such associations, returns `#f`/`#t`. Takes O(n) time.
=== Filtering ===
`(imap-range= `''map obj''`)`
`(imap-range< `''map obj''`)`
`(imap-range> `''map obj''`)`
`(imap-range<= `''map obj''`)`
`(imap-range>= `''map obj''`)`
Returns a map containing only the associations of `map` whose keys are equal to / less than / greater than / less than or equal to / greater than or equal to ''obj''. Takes O(log n) time, where ''n'' is the number of associations in the map .
Note that since map keys are unique, `imap-range=` returns a map of at most one association.
`(imap-filter `''pred map''`)`
`(imap-remove `''pred map''`)`
Returns a map containing only those associations on whose keys ''pred'' returns true/false. Takes O(n log n) time; O(n) is optimal.
`(imap-partition`''pred map''`)`
Returns two values, `(imap-filter `''pred map''`)` and `(imap-remove `''pred map''`)` respectively, but may be more efficient.
=== Mapping and folding ===
`(imap-map/monotone `''proc map'' [ ''comparator'' ]`)`
Returns a map containing the result of invoking ''proc'' on every association in ''map''. It is an error unless ''proc'' is a ''monotone'' unary procedure that preserves the order of map associations. Observe that mapping a map of unique associations with a monotone function yields a map of unique associations, so association uniqueness follows from the monotonicity assumption. If ''comparator'' is given, it is the comparator of the result; otherwise the result uses the same comparator as ''map''. Takes O(n) time.
`(imap-map`''proc map'' [ ''comparator'' [ ''merger'' ] ]`)`
Like `imap-map/monotone`, except that ''proc'' is not required to be monotone. The `merger` procedure is used to select among any duplicate associations (in the sense of the comparator of ''map'') that might be created; it returns the value to be used; if absent, the association chosen is implementation-specific. Takes O(n log n) time.
`(imap-map-values `''proc map''`)`
Invokes '''proc'' on the key and value of every ''association'' in ''map''. The result is a map which associates each key with the result of the corresponding invocation. Takes O(n) time.
`(imap-for-each `''proc map''`)`
Invokes ''proc'' on the key and value of every ''association'' in ''map''. The result is unspecified. Takes O(n) time.
`(imap-collect `''proc map''`)`
Invokes ''proc'' on the key and value of every ''association'' in ''map''. The results are collected into a list in order, which is returned. Takes O(n) time.
`(imap-fold `''proc nil map''`)`
The fundamental map iterator. Equivalent to, but may be more efficient than, `(fold `''proc base'' ` (imap->increasing-list `''map''`))`. Takes O(n) time.
`(imap-fold `''proc nil map''`)`
The fundamental map iterator. Equivalent to, but may be more efficient than, `(fold-right `''proc base'' ` (imap->increasing-list `''map''`))`. Takes O(n) time.
=== Subsets ===
Note: The following three predicates do not obey the trichotomy law and therefore do not constitute a total order on sets.
`(imap=? `''set1 set2'' ...`)`
Returns `#t` if each ''map'' contains the same associations, and `#f` otherwise.
`(imap<? ''set1 set2'' ...`)`
Returns `#t` if each ''map'' other than the last is a proper subset of the following map, and `#f` otherwise.
`(imap>? ''set1 set2'' ...`)`
Returns `#t` if each ''map'' other than the last is a proper superset of the following map, and `#f` otherwise.
`(imap<=? ''set1 set2'' ...`)`
Returns `#t` if each ''map'' other than the last is a subset of the following map, and `#f` otherwise.
`(imap>=? ''set1 set2'' ...`)`
Returns `#t` if each ''map'' other than the last is a superset of the following map, and `#f` otherwise.
=== Conversion ===
`(imap-keys `''imap''`)`
`(imap-values `''imap''`)`
Returns a list of the keys/values of ''imap'' in increasing order. Takes O(n) time.
`(imap-entries `''imap''`)`
Returns two values, lists of the keys and values of ''imap'' in increasing order, but may be more efficient. Takes O(n) time.
`(imap->alist `''map''`)`
Returns an association list containing the associations of `map` in increasing order. Takes O(n) time.
`(ordered-alist->imap comparator list)`
Returns a map containing the associations of ''list'' and using ''comparator''. It is an error for ''alist'' to be anything other than an alist in increasing order. Takes O(n log n) time; O(n) is optimal.
`(alist->imap `''comparator list [ ''merger'' ]`)`
Returns a map containing the associations of ''alist'' and using ''comparator''.It is an error unless ''alist'' is a proper association list, but it may contain duplicates and need not be in order. The ''merger'' procedure is used to select among any duplicate keys (in the sense of the comparator of ''map'') that might be created; it accepts the existing and new keys and returns the key to be used. Takes O(n log n) time.
`(generator->imap `''generator''`)
`(imap->generator `''imap''`)`
Converts a [http://srfi.schemers.org/srfi-121/srfi-121.html SRFI 121] generator to and from a map. The generator produces pairs containing
the keys in the cars and the values in the cdrs.
=== Maps as functions ===
The following procedures provide functions based on maps. In this way, for example, lists can be processed by `map` using the procedure returned from a map by `imap-accessor`.
`(imap-accessor `''map'' [ ''failure'' [ ''success'' ] ]`)`
Curried version of `imap-ref`. Returns a procedure of one argument, a key, which returns what `imap-ref` returns when invoked with the the passed arguments.
`(imap-accessor/default `''map default''`)`
Curried version of `imap-ref/default`. Returns a procedure of one argument, a key, which returns what `imap-ref/default` returns when invoked with the passed arguments.
=== Maps as sets ===
`(imap-union `''map'' ... `)`
`(imap-intersection `''map'' ... `)`
`(imap-difference `''map'' ... `)`
`(imap-xor `''map,,1,, map,,2,,''`)`
Returns a map containing the union/intersection/difference/symmetric difference of the arguments. All the arguments must be sets sharing an equivalent comparator. The map operator is applied in a left-associative order. If an association is found in more than one set, the first map in the argument list prevails. May take O(kn log n) time, where k is the number of sets and n is the number of associations involved, though O(kn) time is optimal.
== Exceptions ==
=== Exceptions ===
`(imap-key-not-found? `''obj''`)`
Returns `#t` if ''obj'' is an object raised by the `imap-ref` procedure or any other procedure that accesses maps when the key is not found and there is no failure procedure, and `#f` otherwise.
time
2015-06-21 10:48:19
version
24