by Wolfgang Corcoran-Mathe

This SRFI is currently in *draft* status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to `srfi-224@nospamsrfi.schemers.org`

. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

- Received: 2021-03-24
- 60-day deadline: 2021-05-23
- Draft #1 published: 2021-03-24
- Draft #2 published: 2021-03-29
- Draft #3 published: 2021-04-01
- Wolfgang's personal
Git repo for this SRFI for reference while the SRFI is in
*draft*status (preview)

Integer maps, or *imappings*, are finite sets, where each element is
an association between an exact-integer key and an arbitrary Scheme
object. They are similar to the general mappings of
SRFI
146, but the restricted key-type allows implementations of
imappings to benefit from optimized structures and algorithms. This
library provides a rich set of operations on imappings, including
analogues of most of the forms provided by SRFI 146. Imappings have
no intrinsic order, but may be treated as ordered sets, using the
natural ordering on keys; a substantial sublibrary for working with
imappings in this fashion is included.

Maybe and Either are somewhat controversial in the Scheme community; should procedures using them be moved to an optional sublibrary?

“Finite maps are the workhorse data structure in every compiler.” —Okasaki & Gill

Mappings provide operations that are critical to a host of functional algorithms. They describe finite sets of key-value associations (pairs) which can be extended, queried, and transformed. Critically, all of these operations can be efficiently implemented as “pure” functions. While hash-tables (see SRFI 125) provide similar operations, they generally provide a strictly imperative language for insertion and mutation of association sets.

Mappings are already familiar to Scheme programmers; SRFI 146 provides general mappings and was added to the Tangerine Edition of R7RS-large. But the generality of SRFI 146 is costly. Any comparable type of Scheme object can be used as a key in a SRFI 146 mapping, so comparisons between keys must use the generic methods of SRFI 128. This is overkill for many use-cases; in particular, if we wish to use exact integers as keys, we expect comparisons to be very fast and to require no mediation from a comparison dictionary. In addition, some efficient and simple mapping representations, for example the Okasaki-Gill radix tree model used in this SRFI’s sample implementation, are unsuitable for representing general mappings.

The integer mappings we describe restrict the type of keys to exact integers. This is a ubiquitous type in computing, and broadly useful as a key-type for mappings; its use opens up a range of implementation options.

This library provides an interface similar to that used by
SRFI 146, although it diverges in some areas. In addition,
`imapping-adjust`

, `imapping-alter`

, and
several other forms derive from Haskell’s
IntMap
library.

Many forms make
instrumental use of SRFI 189’s
Maybe type; I believe that this choice results in simpler,
more compositional definitions. (Compare, for instance, the
conventional `imapping-ref`

form with
`imapping-lookup`

.) Where the
use of Maybe values would clarify nothing, I have preferred the
traditional “value or `#f`

” Lisp protocol.

This library provides “with-key” variants for
many staple higher-order procedures (e.g. `map`

, `fold`

, etc.).
These variants, indicated by the suffix `-/key`

, call their auxiliary
functions on both the keys and values of an imapping (possibly along
with other parameters). A smaller
library proposal might eschew variant forms of a procedure; consider,
for example, the single index-and-value form of `vector-map`

from
SRFI 133. However, this creates
unnecessary inflexibility and incompatibility between SRFIs. In practice,
the added complexity of providing variant higher-order forms is minimal,
and their availability can be a boon to both the programmer and the
standardizer.

The specification of this SRFI depends on the Maybe and Either types specified in SRFI 189 and on the comparator type (used to determine the equality of values, not keys) described in SRFI 128. A few forms also make use of SRFI 217 integer sets, and conversions from imappings to SRFI 158 generators are provided. The sample implementation has further dependencies; see the appropriate section for more details.

Imappings form a new type, as if created by `define-record-type`

(see R7RS § 5.5). The effects of using record-type inspection or inheritance
for the imapping type are unspecified.

It is an error to add or remove an association of an imapping while iterating over it.

Scheme implementations that provide arbitrarily large exact integers
usually divide these numbers into two classes: *fixnums* and
*bignums*. (See the R⁶RS § 3.3 and
SRFI 143.) The former
are integers "within a certain implementation-dependent subrange",
typically those that fit in a single word of memory.

Implementations of this SRFI must support fixnum keys, and may restrict the set of valid keys to the fixnums.

Implementations may support bignum keys.

The words “must”, “may”, etc., though not capitalized in this SRFI, are to be interpreted as described in RFC 2119.

The naming conventions of this document are consistent with those used in the R7RS Scheme standard.

The following names are used for the parameters of procedures:

obj | Any Scheme object. |

boolean | A boolean. |

imap | An integer map (imapping). |

k | An exact integer. |

list | A proper list. |

alist | An association list. |

proc | A procedure. |

mproc | A procedure returning a Maybe object. |

pred | A predicate. |

comp | A SRFI 128 comparator object. |

It is an error (unless otherwise noted) if the procedures are passed arguments that do not have the type implied by the argument names.

The pair notation (*k*,*v*) is often used to describe
an association of an imapping. Here, *k* is the key and
*v* its associated value. If an imapping *imap* is said
to "contain the association (*k*,*v*)", then this is to
be understood in the sense that looking up *k* in *imap*
(via `(imapping-ref`

*imap k*`)`

, for
example) will produce the value *v*.

Each procedure is written in the form

`(`

*proc arg₁ arg₂* …`)`

→ [*type*₁, *type*₂, …]

where *proc* is the name of the procedure, the *args* are its
parameters, and the *types* are the types of the objects it returns.
If the procedure returns a single value, the brackets on the right-hand side
may be omitted.
The *types* refer (informally) to Scheme types; e.g. `boolean`

denotes a Scheme boolean, `list[integer]`

denotes a list of integers,
etc. The special notation ‘*’ indicates that the type
of the value may be anything, depending on the context of the procedure call.
For example, Scheme’s `list-ref`

procedure would be written

`(`

list-ref *list k*`) → *`

since the type of the return value depends on *list*. Multiple
`*`

values appearing in the same type signature do not necessarily
denote the same type. For example, the signature `* * → boolean`

might
denote the type of a procedure taking two values of the same type to a boolean,
or two values of differing types. The accompanying description may clarify
the semantics of procedures defined on `*`

values, but Scheme's
type system makes it difficult to explain all of the possible interactions of
these procedures.

A procedure which returns a value of type *τ*`-or-false`

(where *τ* denotes a type) returns a *τ* on success, and
`#f`

otherwise. Thus the `memv`

procedure of R7RS
would have the type signature `* list[*] → list[*]-or-false`

.

The procedures of this SRFI, by default, are "pure functional" — they
do not alter their parameters. However, this SRFI also defines
"linear-update" procedures, all of whose names end in `!`

.
They have hybrid pure/side-effecting semantics: they are allowed,
but not required, to side-effect one of their parameters in
order to construct their result. An implementation may legally
implement these procedures as pure, side-effect-free functions, or it
may implement them using side effects, depending upon the details of
what is the most efficient or simple to implement in terms of the
underlying representation.

It is an error to rely upon these procedures working by side effect. For example, this is not guaranteed to work:

(let* ((imap1 (imapping 1 'b 2 'c)) (imap2 (imapping-adjoin! imap1 3 'd))) imap1) ; Could be either {(1, b), (2, c)} or {(1, b), (2, c) (3, d)}.

However, this is well-defined:

(let ((imap1 (imapping 1 'b 2 'c))) (imapping-adjoin! imap1 3 'd))

So clients of these procedures write in a functional style, but must additionally be sure that, when the procedure is called, there are no other live references to the potentially-modified imapping (hence the term "linear update").

There are two benefits to this convention:

Implementations are free to provide the most efficient possible implementation, either functional or side-effecting.

Programmers may nonetheless continue to assume that imappings are purely functional data structures: they may be reliably shared without needing to be copied, uniquified, and so forth.

In practice, these procedures are most useful for efficiently constructing imappings in a side-effecting manner, in some limited local context, before passing the imapping outside the local construction scope to be used in a functional manner.

Scheme provides no assistance in checking the linearity of the potentially side-effected parameters passed to these functions — there's no linear type checker or run-time mechanism for detecting violations.

Note that if an implementation uses no side effects at all, it is allowed to return existing imappings rather than newly allocated ones, even where this SRFI explicitly says otherwise.

Constructors:

`imapping, imapping-unfold, imapping-unfold-maybe, alist->imapping, iset->imapping`

Predicates:

`imapping?, imapping-contains?, imapping-empty?, imapping-disjoint?`

Accessors:

`imapping-ref, imapping-ref/default, imapping-lookup, imapping-min, imapping-max`

Updaters:

`imapping-adjoin, imapping-adjoin/combinator, imapping-adjoin!, imapping-adjoin/combinator!, imapping-adjust, imapping-adjust/key, imapping-adjust!, imapping-adjust/key!, imapping-delete, imapping-delete!, imapping-delete-all, imapping-delete-all!, imapping-alter, imapping-alter!, imapping-update, imapping-update/key, imapping-update!, imapping-update/key!, imapping-delete-min, imapping-delete-max, imapping-delete-min!, imapping-delete-max!, imapping-update-min, imapping-update-max, imapping-update-min/key, imapping-update-max/key, imapping-update-min!, imapping-update-max!, imapping-update-min/key!, imapping-update-max/key!, imapping-pop-min, imapping-pop-max, imapping-pop-min!, imapping-pop-max!`

The whole imapping:

`imapping-size, imapping-count, imapping-count/key, imapping-any?, imapping-every?`

Traversal:

`imapping-fold, imapping-fold-right, imapping-fold/key, imapping-fold-right/key, imapping-map, imapping-map/key, imapping-map!, imapping-map/key!, imapping-map->list, imapping-map/key->list, imapping-for-each, imapping-for-each/key, imapping-filter-map, imapping-filter-map/key, imapping-filter-map!, imapping-filter-map/key!, imapping-map-either, imapping-map-either/key, imapping-map-either!, imapping-map-either/key!, imapping-relation-map`

Filter:

`imapping-filter, imapping-filter/key, imapping-filter!, imapping-filter/key!, imapping-remove, imapping-remove/key, imapping-remove!, imapping-remove/key!, imapping-partition, imapping-partition/key, imapping-partition!, imapping-partition/key!`

Copying and conversion:

`imapping-copy, imapping->alist, imapping->decreasing-alist, imapping-keys, imapping-values, imapping-keys-set, imapping->generator, imapping->decreasing-generator`

Comparison:

`imapping=?, imapping<?, imapping>?, imapping<=?, imapping>=?`

Set theory operations:

`imapping-union, imapping-intersection, imapping-difference, imapping-xor, imapping-union!, imapping-intersection!, imapping-difference!, imapping-xor!, imapping-union/combinator, imapping-intersection/combinator, imapping-union/combinator!, imapping-intersection/combinator!`

Submappings:

`imapping-open-interval, imapping-closed-interval, imapping-open-closed-interval, imapping-closed-open-interval, imapping-open-interval!, imapping-closed-interval!, imapping-open-closed-interval!, imapping-closed-open-interval!, isubmapping=, isubmapping<, isubmapping<=, isubmapping>=, isubmapping>, isubmapping=!, isubmapping<!, isubmapping<=!, isubmapping>=!, isubmapping>!, imapping-split`

`(imapping`

*k*₁ *obj*₁ *k*₂ `…) → imapping`

Returns a new imapping. The arguments alternate between keys (which
must be exact integers) and values (which are arbitrary Scheme objects); the
resulting imapping contains these (*k*, *obj*) associations.
The number of arguments must be even. If duplicate keys occur in
the arguments, earlier associations take priority.

Examples:

```
(imapping->alist (imapping 0 'a 1 'b 2 'c)) ⇒ ((0 . a) (1 . b) (2 . c))
(imapping->alist (imapping -10 "worf" -10 "yar")) ⇒ ((-10 . "worf"))
```

`(imapping-unfold`

*stop? mapper successor seed*`) → imapping`

*stop?*:`* → *-or-#f`

*mapper*:`* → [exact-integer, *]`

*successor*:`* → *`

*seed*:`*`

Unfold a new imapping from the initial seed value *seed*.
*mapper* is applied to each seed and returns two values, a key
and an associated value, which are adjoined to the new imapping.
*successor* maps each seed to a new seed.
Unfolding terminates when the predicate *stop?* returns a true
value when applied to the current seed.

Example:

```
(imapping->alist
(imapping-unfold (lambda (i) (= i 4))
(lambda (i) (values i (make-string i #\a)))
(lambda (i) (+ i 1))
0))
⇒ ((0 . "") (1 . "a") (2 . "aa") (3 . "aaa"))
```

`(imapping-unfold-maybe`

*mproc seed*`) → imapping`

*mproc*:`* → maybe[exact-integer, *, *]`

*seed*:`*`

Unfold a new imapping. *mproc* is applied to *seed* and returns
a Maybe value. If this value is Nothing, then unfolding terminates.
If it is Just *k v seed′*, then a new association
*(k, v)* is added to the resulting imapping and unfolding continues
with *seed′*.

Example:

```
(imapping->alist
(imapping-unfold-maybe (lambda (i)
(if (< i -3)
(nothing)
(just i (square i) (- i 1))))
-1))
⇒ ((-3 . 9) (-2 . 4) (-1 . 1))
```

**Rationale:** As well as sometimes leading to more compact
expressions than the
traditional "three procedure" unfold, `imapping-unfold-maybe`

is also more efficient when the programmer wants the value of each new seed
to depend on the computed key and value. For example,
assume that we apply some procedure *f* to a seed *s* to get a
key *k* and a value *v*, and that we also want to compute a new
seed from *k* and *v*. Using *imapping-unfold*, we'd
have no choice other than to compute *k* and *v* twice:

```
(imapping-unfold stop?
f
(lambda (s)
(let-values (((k v) (f s)))
(let ((s* …))
s*)))
seed)
```

Using `imapping-unfold-maybe`

, however, it's easy to write an
equivalent unfold which computes *k* and *v* only once for
each step:

```
(imapping-unfold-maybe (lambda (s)
(if (stop? s)
(nothing)
(let-values (((k v) (f s)))
(let ((s* …))
(just k v s*)))))
seed)
```

This may be preferable when *f* is expensive to apply or entails
side-effects.

`(alist->imapping`

*alist*`) → imapping`

Returns a new imapping containing the associations of *alist*.
It is an error if the car of any pair in *alist* is not an
exact integer.

Example:

```
(imapping->alist (alist->imapping '((1 . b) (0 . a) (2 . c))))
⇒ ((0 . a) (1 . b) (2 . c))
```

`(iset->imapping`

*proc iset*`) → imapping`

*proc* is of type `exact-integer → *`

.

Returns a new imapping constructed from the elements of the integer
set *iset* (see
SRFI 217).
For each integer *k* in *iset*, the association
(*k*, (*proc* *k*)) is added to the imapping.
*iset* is traversed in an unspecified order.

Example:

```
(imapping->alist (iset->imapping square (iset 2 4 6 8)))
⇒ ((2 . 4) (4 . 16) (6 . 36) (8 . 64))
```

`(imapping?`

*obj*`) → boolean`

Returns `#t`

if and only if *obj* is an imapping.

`(imapping-contains?`

*imap k*`) → boolean`

Returns `#t`

if and only if *imap* contains an association for key *k*.

Examples:

```
(imapping-contains? (imapping 1 'b) 1) ⇒ #t
(imapping-contains? (imapping 1 'b) 0) ⇒ #f
```

`(imapping-empty?`

*imap*`) → boolean`

Returns `#t`

if and only if *imap* contains no associations.

Examples:

```
(imapping-empty? (alist->imapping '())) ⇒ #t
(imapping-empty? (alist->imapping '((0 . a)))) ⇒ #f
```

`(imapping-disjoint?`

*imap*₁ *imap*₂`) → boolean`

Returns `#t`

if and only if *imap*₁ and *imap*₂ have no keys in common.

Examples:

```
(imapping-disjoint? (imapping 0 'a) (imapping 1 'b)) ⇒ #t
(imapping-disjoint? (imapping 1 '(b)) (imapping 1 'b)) ⇒ #f
```

`(imapping-ref`

*imap k*` [ `

*failure*` [ `

*success*` ] ]) → *`

If the optional *failure* parameter is supplied, then it must
be a procedure of no arguments returning zero or more values of arbitrary
type. The optional *success* parameter is a procedure of type
`* → *`

. *failure* defaults to a procedure which
signals an error; *success* defaults to `values`

.

If an association *(k, v)* occurs in *imap*,
tail-calls *success* on *v*. Otherwise, *failure*
is tail-called on no arguments.

Examples:

```
(imapping-ref (imapping 36864 'zap) 36864) ⇒ zap
(imapping-ref (imapping 0 'a) 36864) ⇒ ; error
(imapping-ref (imapping 0 "worf") 0 (lambda () #f) string-length) ⇒ 4
```

`(imapping-ref/default`

*imap k obj*`) → *`

If an association *(k, v)* occurs in *imap*, returns *v*.
Otherwise, returns *obj*.

Examples:

```
(imapping-ref/default (imapping 36864 'zap) 36864 #f) ⇒ zap
(imapping-ref/default (imapping 0 'a) 36864 #f) ⇒ #f
```

`(imapping-lookup`

*imap k*`) → maybe[*]`

If an association *(k, v)* occurs in *imap*, returns Just *v*.
Otherwise, returns Nothing.

Examples:

```
(imapping-lookup (imapping 36864 'zap) 36864) ⇒ just[zap]
(imapping-lookup (imapping 0 'a) 36864) ⇒ nothing
```

`(imapping-min`

*imap*`) → maybe[exact-integer, *]`

Returns Just *k* *v*, where *k* is the least key of *imap*.
If *imap* is empty in the sense of `imapping-empty?`

, returns
Nothing.

Examples:

```
(imapping-min (imapping 0 'a 1 'b 2 'c)) ⇒ just[0, a]
(imapping-min (imapping)) ⇒ nothing
```

`(imapping-max`

*imap*`) → maybe[exact-integer, *]`

Returns Just *k* *v*, where *k* is the greatest key of *imap*.
If *imap* is empty in the sense of `imapping-empty?`

, returns
Nothing.

Examples:

```
(imapping-max (imapping 0 'a 1 'b 2 'c)) ⇒ just[2, c]
(imapping-max (imapping)) ⇒ nothing
```

`(imapping-adjoin`

*imap k*₁ *obj*₁ *k*₂ `…) → imapping`

Returns a new imapping containing all of the associations of
*imap* as well as the associations (*k*₁, *v*₁), (*k*₂, *k*₂), …
The number of key/value arguments must be even.

If any of the keys already have associations in *imap*, the old
associations are replaced.

Examples:

```
(imapping->alist (imapping-adjoin (imapping 1 'b) 0 'a)) ⇒ ((0 . a) (1 . b))
```

`(imapping-adjoin!`

*imap k*₁ *obj*₁ *k*₂ `…) → imapping`

`imapping-adjoin!`

is the same as `imapping-adjoin`

,
except that it may mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-adjoin/combinator`

*imap proc k*₁ *obj*₁ *k*₂ `…)`

Similar to `imapping-adjoin`

, except that duplicate associations
are combined with *proc*, which is a procedure of type `* * → *`

.
*proc* is called on the new and old values (in that order) associated
with a duplicated key and is expected to return a value for the key.

Example:

```
(imapping->alist
(imapping-adjoin/combinator (imapping 0 "geordi" 1 "reginald")
(lambda (last first)
(string-append first " " last))
0 "laforge"
1 "barclay"))
⇒ ((0 . "geordi laforge") (1 . "reginald barclay"))
```

`(imapping-adjoin/combinator!`

*imap proc k*₁ *obj*₁ *k*₂ `…)`

`imapping-adjoin/combinator!`

is the same as
`imapping-adjoin/combinator`

, except that it may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-adjust imap k proc) → imapping`

`(imapping-adjust/key imap k proc) → imapping`

The *proc* parameter of `imapping-adjust`

is a
procedure of type `* → *`

; that of
`imapping-adjust/key`

is of type
`exact-integer * → *`

.

Returns a new imapping in which the association (*k*, *v*) in *imap*
is replaced by (*k*, (*proc v*)), or by (*k*, (*proc k v*)) in the
case of `imapping-adjust/key`

. If *k* has no association in *imap*,
then a copy of *imap* is returned.

Examples:

```
(imapping->alist (imapping-adjust (imapping 0 -200 1 -100) 0 abs))
⇒ '((0 . 200) (1 -100))
(imapping->alist
(imapping-adjust/key (imapping 64 "var")
64
(lambda (k s) (string-append s (number->string k)))))
⇒ ((64 . "var64"))
```

`(imapping-adjust! imap k proc) → imapping`

`(imapping-adjust/key! imap k proc) → imapping`

`imapping-adjust!`

and `imapping-adjust/key!`

are the same as `imapping-adjust`

and
`imapping-adjust/key`

, respectively, except that they may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-delete imap`

*k*₁ *k*₂ `…) → imapping`

Returns a new imapping with the same associations as *imap*, except
those for keys equal to *k*₁, *k*₂, …. If a key does not have an
association in *imap*, it is ignored.

Example:

```
(imapping->alist (imapping-delete (imapping 0 -200 1 -100) 0)) ⇒ ((1 . -100))
```

`(imapping-delete! imap`

*k*₁ *k*₂ `…) → imapping`

`imapping-delete!`

is the same as
`imapping-delete`

, except that it may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-delete-all`

*imap list*`) → imapping`

Returns a new imapping with the same associations as *imap*, except
those for keys equal to an element of *list*.

Example:

```
(imapping->alist (imapping-delete-all (imapping 0 'a 1 'b 2 'c) '(1 2)))
⇒ ((0 . a))
```

`(imapping-delete-all!`

*imap list*`) → imapping`

`imapping-delete-all!`

is the same as
`imapping-delete-all`

, except that it may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-update`

*imap k mproc*`) → imapping`

`(imapping-update/key`

*imap k mproc*`) → imapping`

Returns a new imapping with the same associations as *imap*, except
that the association for *k* is updated as follows. *mproc* is
applied to the value associated with *k*.
If it returns Nothing, the association is deleted;
if it returns Just *v*, then *(k, v)* is added to the new imapping.
If *k* has no association in *imap*, then a copy of *imap*
is returned.

`imapping-update/key`

is the same as `imapping-update`

, except that
*mproc* is called on *n* and its associated value, in that order.

Simple versions of several other update operations may be defined
in terms of `imapping-update`

, e.g.:

```
(imapping-delete imap k)
≡
(imapping-update imap k (lambda (_) (nothing)))
(imapping-adjoin imap k v)
≡
(imapping-update imap k (lambda (_) (just v)))
```

Examples:

```
;; Delete the association for 1 if its value is a symbol.
(imapping->alist
(imapping-update (imapping 0 'a 1 'b 2 'c)
1
(lambda (v)
(if (symbol? v)
(nothing)
(just v)))))
⇒ ((0 . a) (2 . c))
;; Replace the value associated with 1.
(imapping->alist
(imapping-update/key (imapping 0 'a 1 'b 2 'c) 1 (lambda (k _v) (just k))))
⇒ ((0 . a) (1 . 1) (2 . c))
```

`(imapping-update!`

*imap k mproc*`) → imapping`

`(imapping-update/key!`

*imap k mproc*`) → imapping`

`imapping-update!`

and `imapping-update/key!`

are the same as `imapping-update`

and
`imapping-update/key`

, respectively, except that they may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-alter`

*imap k proc*`) → imapping`

*proc* is a procedure of type `maybe[*] → maybe[*]`

.

Returns a new imapping with the same associations as *imap*, except
that the association, or lack thereof, for *k* is updated as follows.
If the association *(k, v)* exists in *imap*, then *proc* is called on
Just *v*; if no such association exists, then *proc* is called on
Nothing. If the result of this application is Nothing, the
association is deleted (or no new association is added); if the result
is Just *v′*, a new association *(k, v′)* is added to the new
imapping, replacing any old association for *k*.

`imapping-alter`

is a very general operator on imappings, and most
of the other update operations may be defined in terms of it. For
example:

```
(imapping-update imap k f)
≡
(imapping-alter imap k (lambda (m)
(maybe-ref m nothing f))
```

Examples:

```
;; Insert an association for 4 if it's not present.
(imapping->alist
(imapping-alter (imapping 0 'a 1 'b)
4
(lambda (m)
(if (nothing? m) (just 'e) m))))
⇒ ((0 . a) (1 . b) (4 . e))
;; Delete an association for 1 if its value is a symbol.
(imapping->alist
(imapping-alter (imapping 0 'a 1 'b)
1
(lambda (m)
(maybe-bind m (lambda (v)
(if (symbol? v)
(nothing)
(just v)))))))
⇒ ((0 . a))
```

`(imapping-alter!`

*imap k proc*`) → imapping`

`imapping-alter!`

is the same as
`imapping-alter`

, except that it may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-delete-min`

*imap*`) → imapping`

`(imapping-delete-max`

*imap*`) → imapping`

Returns a new imapping with the same associations as *imap*, except
for the association with the least/greatest key. If *imap* is empty,
an error is signalled.

`(imapping-delete-min!`

*imap*`) → imapping`

`(imapping-delete-max!`

*imap*`) → imapping`

`imapping-delete-min!`

and `imapping-delete-max!`

are the same as `imapping-delete-min`

and
`imapping-delete-max`

, respectively, except that they may
mutate and return the *imap* argument instead of
allocating a new imapping.

Examples:

```
(imapping-delete-min (imapping 0 'a 1 'b 2 'c)) ⇒ ((1 . b) (2 . c))
(imapping-delete-max (imapping 0 'a 1 'b 2 'c)) ⇒ ((0 . a) (1 . b))
```

`(imapping-update-min`

*imap mproc*`) → imapping`

`(imapping-update-max`

*imap mproc*`) → imapping`

`(imapping-update-min/key`

*imap mproc*`) → imapping`

`(imapping-update-max/key`

*imap mproc*`) → imapping`

The *mproc* argument of `imapping-update-min`

and `-max`

is of
type `* → maybe[*]`

; that of `imapping-update-min/key`

and of
`-max/key`

is of type `exact-integer * → maybe[*]`

.

Returns a new imapping with the same associations as *imap*, except
that the association for the least/greatest key *k* is updated as
follows. *mproc* is applied to the value associated with *k* and is
expected to return a Maybe value. If it returns Nothing, the
association is deleted; if it returns Just *v*, then *(k, v)* is added
to the new imapping. If *imap* is empty, an error is signalled.

`imapping-update-min/key`

and `imapping-update-max/key`

are the same
as `imapping-update-min`

and `imapping-update-max`

, respectively,
except that *mproc* is called on *k* and its associated value, in that
order.

Examples:

```
(imapping->alist
(imapping-update-min (imapping -5 "phaser" -1 "tricorder")
(lambda (v)
(if (symbol? v)
(just v)
(nothing)))))
⇒ ((-1 . "tricorder"))
(imapping->alist
(imapping-update-max/key (imapping -5 "phaser" -1 "tricorder")
(lambda (k v)
(if (and (negative? k) (string? v))
(just (string-length v))
(nothing)))))
⇒ ((-5 . "phaser") (-1 . 9))
```

`(imapping-update-min!`

*imap mproc*`) → imapping`

`(imapping-update-max!`

*imap mproc*`) → imapping`

`(imapping-update-min/key!`

*imap mproc*`) → imapping`

`(imapping-update-max/key!`

*imap mproc*`) → imapping`

These are linear-update variants of
`imapping-update-min`

, etc.. They may
mutate and return the *imap* argument instead of allocating
a new imapping.

`(imapping-pop-min`

*imap*`) → maybe[exact-integer, *, imapping]`

`(imapping-pop-max`

*imap*`) → maybe[exact-integer, *, imapping]`

Returns Just *k v imap′*, where (*k*, *v*) is the association of
*imap* with the least/greatest key and *imap′* is a newly-allocated
imapping containing all of the associations of *imap* except for
(*k*, *v*). If *imap* is empty, returns Nothing.

Example:

```
(maybe-let*-values (((k v imap)
(imapping-pop-min (imapping 0 'a 1 'b 2 'c))))
(values k v (imapping->alist imap)))
⇒ (just 0 a ((1 . b) (2 . c)))
```

`(imapping-pop-min!`

*imap*`) → maybe[exact-integer, *, imapping]`

`(imapping-pop-max!`

*imap*`) → maybe[exact-integer, *, imapping]`

`imapping-pop-min!`

and `imapping-pop-max!`

are the same as `imapping-pop-min`

and
`imapping-pop-max`

, respectively, except that they may
mutate and return the *imap* argument instead
of allocating a new imapping.

`(imapping-size`

*imap*`) → exact-integer`

Returns the number of associations in *imap*.

`(imapping-count`

*pred imap*`) → exact-integer`

`(imapping-count/key`

*pred imap*`) → exact-integer`

Returns the number of associations in *imap* whose values satisfy
*pred*.

`imapping-count/key`

is the same, except that *pred* is called on
the key and value of each association.

Examples:

```
(imapping-count even? (imapping 0 1 1 2 2 4 3 8)) ⇒ 3
(imapping-count/key (lambda (k s) (= k (string-length s)))
(imapping 0 "x" 1 "y" 2 "z"))
⇒ 1
```

`(imapping-any?`

*pred imap*`) → boolean`

Returns `#t`

if and only if there exists an association in *imap* whose value
satisfies *pred*. *imap* is traversed in ascending numerical order
of keys.

Example:

```
(imapping-any? odd? (imapping 0 1 1 2 2 4 3 8)) ⇒ #t
```

`(imapping-every?`

*pred imap*`) → boolean`

Returns `#t`

if and only if the value of every association in *imap* satisfies
*pred*, or if *imap* is empty. *imap* is traversed in ascending
numerical order of keys.

Example:

```
(imapping-every? integer? (imapping 0 1 1 2 2 4 3 8)) ⇒ #t
```

`(imapping-map`

*proc imap*`) → imapping`

`(imapping-map/key`

*proc imap*`) → imapping`

The *proc* argument of `imapping-map`

is of type `* → *`

;
that of `imapping-map/key`

is of type `exact-integer * → *`

.

Returns a new imapping. For each association *(n, v)* in *imap*,
the association *(n, (proc v))* is added to the new imapping.
Associations are traversed in an arbitrary order. The dynamic order
of the applications of *proc* to the elements of *imap* is
unspecified.

`imapping-map/key`

is the same, except that *proc* is called on
the key and value of each association.

Examples:

```
(imapping->alist
(imapping-map string-length
(imapping 0 "picard" 1 "riker" 2 "troi")))
⇒ ((0 . 6) (1 . 5) (2 . 4))
(imapping->alist
(imapping-map/key (lambda (k s)
(string-append s (number->string k)))
(imapping 256 "x" 512 "y" 1024 "z")))
⇒ ((256 . "x256") (512 . "y512") (1024 . "z1024"))
```

Note that, in contrast to SRFI 146’s map procedures, these procedures
transform the values of *imap* only; that is, the set of keys of the
resulting imapping is the same as that of *imap*.

`(imapping-map!`

*proc imap*`) → imapping`

`(imapping-map/key!`

*proc imap*`) → imapping`

`imapping-map!`

and `imapping-map/key!`

are the same as `imapping-map`

and
`imapping-map/key`

, respectively, except that they may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-for-each`

*proc imap*`) → unspecified`

`(imapping-for-each/key`

*proc imap*`) → unspecified`

Calls *proc* on the value of each association in *imap* and returns
an unspecified value. *imap* is traversed in ascending numerical
order of keys.

`imapping-for-each/key`

is the same, except that *proc* is called on
the key and value of each association.

Example:

```
(let ((sum 0))
(imapping-for-each (lambda (v) (set! sum (+ sum v)))
(imapping 0 1 1 2 2 4 3 8))
sum)
⇒ 15
```

`(imapping-fold`

*kons knil imap*`) → *`

`(imapping-fold-right`

*kons knil imap*`) → *`

`(imapping-fold/key`

*kons knil imap*`) → *`

`(imapping-fold-right/key`

*kons knil imap*`) → *`

The *kons* argument of `imapping-fold`

and `imapping-fold-right`

is a
procedure of type `* * → *`

; that of `imapping-fold/key`

and of `imapping-fold-right/key`

is of type `exact-integer * * → *`

.
*knil* can be any object.

Folds *kons* over *imap*, using *knil* as the base value. At
each step, *kons* is applied to the value of an association and to
the result of the last application.
`imapping-fold`

folds in ascending numerical order of keys;
`imapping-fold-right`

folds in descending order.

`imapping-fold/key`

and `imapping-fold-right/key`

are the same
as `imapping-fold`

and `imapping-fold-right`

, respectively,
except that *kons* is also passed the key of each association as its first
argument.

Examples:

```
(imapping-fold-right cons '() (imapping 0 "worf" 1 "data" 2 "crusher"))
⇒ ("worf" "data" "crusher")
(imapping-fold/key (lambda (k _ ks) (cons k ks))
'()
(imapping 0 "worf" 1 "data" 2 "crusher"))
⇒ (2 1 0)
```

`(imapping-map->list`

*proc imap*`) → list`

`(imapping-map/key->list`

*proc imap*`) → list`

Efficient fusion of `(imapping-values (imapping-map`

*proc imap*`))`

.

`imapping-map/key->list`

is the same, except that *proc* is called on
the key and value of each association.

Example:

```
(imapping->alist
(imapping-map->list string-length
(imapping 0 "picard" 1 "riker" 2 "troi")))
⇒ (6 5 4)
```

`(imapping-filter-map`

*proc imap*`) → imapping`

`(imapping-filter-map/key`

*proc imap*`) → imapping`

The *proc* parameter of `imapping-filter-map`

is a
procedure of type `* → *-or-#f`

; that of
`imapping-filter-map/key`

is of type
`exact-integer * → *-or-#f`

.

`imapping-filter-map`

is similar to `imapping-map`

,
but only associations for which *proc* returns a true value are
added to the new imapping.

`imapping-filter-map/key`

is the same, except that *proc*
is called on the key and value of each association.

Example:

```
(imapping->alist
(imapping-filter-map (lambda (v)
(and (positive? v) (square v)))
(imapping 0 2 1 -4 2 8)))
⇒ ((0 . 4) (2 . 64))
```

`(imapping-filter-map!`

*proc imap*`) → imapping`

`(imapping-filter-map/key!`

*proc imap*`) → imapping`

`imapping-filter-map!`

and `imapping-filter-map/key!`

are the same as `imapping-filter-map`

and
`imapping-filter-map/key`

, respectively, except that they may
mutate and return the *imap* argument instead of
allocating a new imapping.

`(imapping-map-either`

*proc imap*`) → [imapping, imapping]`

`(imapping-map-either/key`

*proc imap*`) → [imapping, imapping]`

The *proc* of `imapping-map-either`

is a procedure
of type `* → either[*]`

, where `either[*]`

denotes
a SRFI 189 Either containing a single value. The *proc* parameter
of `imapping-map-either/key`

is of type
`exact-integer * → either[*]`

.

`imapping-map-either`

maps *proc* over the values
of *imap* and returns imappings of the Left and of the Right
results. For each association (*k*, *v*) in
*imap*, (*proc v*) is evaluated. If the result is a
Left of a value *v*₁, then the association (*k*,
*v*₁) is added to the first new imapping. If it is instead a
Right of *v*₂, then the association (*k*, *v*₂)
is added to the second new imapping.

`imapping-map-either/key`

is the same, except that *proc*
is called on the key and value of each association.

Example:

```
(let-values (((lefts rights)
(imapping-map-either
(lambda (v)
(if (>= v 0)
(right v)
(left v)))
(imapping 0 -50 4 -25 8 25 12 50))))
(values (imapping->alist lefts)
(imapping->alist rights)))
⇒ ((0 . -50) (4 . -25))
((8 . 25) (12 . 50))
```

`(imapping-map-either!`

*proc imap*`) → imapping imapping`

`(imapping-map-either/key!`

*proc imap*`) → imapping imapping`

`imapping-map-either!`

and `imapping-map-either/key!`

are the same as `imapping-map-either`

and
`imapping-map-either/key`

, respectively, except that they may
mutate the *imap* parameter to produce their results.

`(imapping-relation-map`

*proc imap*`) → imapping`

`proc`

must be a procedure of type
`exact-integer * → [exact-integer, *]`

.

Returns a new imapping whose associations are the results of
transforming both the keys and the values of *imap* with
*proc*. For each association (*k*,
*v*) in *imap*, (*proc k v*) is evaluated to
return a new key and a new value which are associated in the new
imapping. Duplicate keys are replaced, but the results in this case
are unpredictable; if *proc* is not injective, that is, if it
produces multiple associations with the same key, then it is unspecified
which one of these associations will be present in the resulting
imapping. The dynamic order of the applications of *proc* to the
elements of *imap* is unspecified.

**Rationale:** `imapping-relation-map`

corresponds to `mapping-map`

from SRFI 146 and is specified
primarily for compatibility with that SRFI. It generalizes
`imapping-map`

and `imapping-map/key`

, and can
be used to produce a wide range of transformations on imappings. This
generality comes at a price, however. Certain familiar laws that hold
of `imapping-map`

and other Scheme "map" functions do not
hold of `imapping-relation-map`

; in particular, the size of
the input imapping *imap* may not be preserved, and a key with an
association in *imap* may not have an association in the
transformed imapping.

As such, `imapping-map`

and `imapping-map/key`

likely conform better to the familiar pattern of Scheme "map" functions,
while being sufficiently general for most purposes.

`(imapping-filter`

*pred imap*`) → imapping`

`(imapping-filter/key`

*pred imap*`) → imapping`

Returns a new imapping containing all of the associations of *imap*
whose values satisfy *pred*.

`imapping-filter/key`

is the same, except that *pred* is applied to
the key and value of each association.

Example:

```
(imapping->alist (imapping-filter positive?
(imapping 0 2 1 -4 2 8 3 -16)))
⇒ ((0 . 2) (2 . 8))
```

`(imapping-filter!`

*pred imap*`) → imapping`

`(imapping-filter/key!`

*pred imap*`) → imapping`

`imapping-filter!`

and `imapping-filter/key!`

are the same as `imapping-filter`

and
`imapping-filter/key`

, respectively, except that they may
mutate and return the *imap* parameter instead of
allocating a new imapping.

`(imapping-remove`

*pred imap*`) → imapping`

`(imapping-remove/key`

*pred imap*`) → imapping`

Returns a new imapping containing all of the associations of *imap*
whose values do not satisfy *pred*.

`imapping-remove/key`

is the same, except that *pred* is applied to
the key and value of each association.

Example:

```
(imapping->alist (imapping-remove positive?
(imapping 0 2 1 -4 2 8 3 -16)))
⇒ ((1 . -4) (3 . -16))
```

`(imapping-remove!`

*pred imap*`) → imapping`

`(imapping-remove/key!`

*pred imap*`) → imapping`

`imapping-remove!`

and `imapping-remove/key!`

are the same as `imapping-remove`

and
`imapping-remove/key`

, respectively, except that they may
mutate and return the *imap* parameter instead of
allocating a new imapping.

`(imapping-partition`

*pred imap*`) → [imapping, imapping]`

`(imapping-partition/key`

*pred imap*`) → [imapping, imapping]`

Returns two new imappings: the first contains all associations of
*imap* whose values satisfy *pred*, and the second contains those
whose values do not.

`imapping-partition/key`

is the same, except that *pred* is applied to
the key and value of each association.

Example:

```
(let-values (((pos ~pos) (imapping-partition positive?
(imapping 0 2 1 -4 2 8 3 -16))))
(values (imapping->alist pos)
(imapping->alist ~pos)))
⇒ ((0 . 2) (2 . 8))
((1 . -4) (3 . -16))
```

`(imapping-partition!`

*pred imap*`) → imapping`

`(imapping-partition/key!`

*pred imap*`) → imapping`

`imapping-partition!`

and `imapping-partition/key!`

are the same as `imapping-partition`

and
`imapping-partition/key`

, respectively, except that they may
mutate the *imap* parameter to produce their results.

`(imapping-copy`

*imap*`) → imapping`

Returns a newly allocated imapping containing the associations of
`imap`

.

`(imapping->alist`

*imap*`) → alist[exact-integer, *]`

Returns a car/cdr alist containing the associations of *imap* in
ascending numerical order of keys.

Example:

```
(imapping->alist (imapping 1 'a 2 'b)) ⇒ ((1 . a) (2 . b))
```

`(imapping->decreasing-alist`

*imap*`) → alist[exact-integer, *]`

Returns a car/cdr alist containing the associations of *imap* in
decreasing numerical order of keys.

Example:

```
(imapping->alist (imapping 1 'a 2 'b)) ⇒ ((2 . b) (1 . a))
```

`(imapping-keys`

*imap*`) → list[exact-integer]`

Returns the keys of *imap* as a list in ascending numerical order.

Example:

```
(imapping-keys (imapping 137 'a -24 'b -5072 'c)) ⇒ (-5072 -24 137)
```

`(imapping-keys-set`

*imap*`) → iset`

Returns a SRFI 217 integer set containing the keys of *imap*.

Example:

```
(iset->list (imapping-keys-set (imapping 137 'a -24 'b -5072 'c)))
⇒ (-5072 -24 137)
```

`(imapping-values`

*imap*`) → list[*]`

Returns the elements of *imap* as a list in ascending numerical
order of key.

Example:

```
(imapping-values (imapping 0 "picard" 1 "riker" 2 "troi"))
⇒ ("picard" "riker" "troi")
```

`(imapping->generator`

*imapping*`) → generator[pair(exact-integer, *)]`

Returns a SRFI 158 generator which
produces the associations of *imapping* as key/value pairs in increasing
order of key.

Example:

```
(generator->list (imapping->generator (imapping 3 "yar" 2 "troi")))
⇒ ((2 . "troi") (3 . "yar"))
```

`(imapping->decreasing-generator`

*imapping*`) → generator[pair(exact-integer, *)]`

This is the same as `imapping->generator`

, except that the associations
of *imapping* are produced in decreasing order of key.

Example:

```
(generator->list (imapping->decreasing-generator (imapping 3 "yar" 2 "troi")))
⇒ ((3 . "yar") (2 . "troi"))
```

`(imapping=?`

*comp imap*₁ *imap*₂ *imap*₃ `…) → boolean`

Returns `#t`

if and only if all of the *imaps* contain equal
associations. Two associations are equal exactly when their keys are
equal (in the sense of `=`

) and if their values are equal in the sense
of the equality predicate of *comp* (see
SRFI 128).

Examples:

```
(imapping=? (make-default-comparator)
(imapping 1 'a 2 'b)
(imapping 2 'b 1 'a))
⇒ #t
(imapping=? (make-default-comparator)
(imapping 1 'a 2 'b 3 'c)
(imapping 2 'b 1 'a))
⇒ #f
```

`(imapping<?`

*comp* *imap*₁ *imap*₂ *imap*₃ `…) → boolean`

`(imapping<=?`

*comp* *imap*₁ *imap*₂ *imap*₃ `…) → boolean`

`(imapping>?`

*comp* *imap*₁ *imap*₂ *imap*₃ `…) → boolean`

`(imapping>=?`

*comp* *imap*₁ *imap*₂ *imap*₃ `…) → boolean`

Returns `#t`

if and only if each *imap* other than the last is a proper
subset/subset/proper superset/superset of the following *imap*. Values are
compared using the equality predicate of *comp*.

Examples:

```
(imapping<? (make-default-comparator)
(imapping 1 'a 2 'b)
(imapping 2 'b 1 'a 3 'c))
⇒ #t
(imapping>? (make-default-comparator)
(imapping 2 'b 1 "worf" 3 'c)
(imapping 1 'a 2 'b))
⇒ #f
(imapping>=? (make-default-comparator)
(imapping 2 'b 1 'a 3 'c)
(imapping 1 'a 2 'b)
(imapping 2 'b 1 'a)
(imapping 1 'a))
⇒ #t
```

`(imapping-union`

*imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-intersection`

*imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-difference`

*imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-xor`

*imap*₁ *imap*₂`) → imapping`

Return a newly allocated imapping whose set of associations is the
union, intersection, asymmetric difference, or symmetric difference of
the sets of associations of the *imaps*. Asymmetric difference is
extended to more than two imappings by taking the difference between
the first imapping and the union of the others. Symmetric difference
is not extended beyond two imappings. When comparing associations,
only the keys are compared. In case of duplicate keys, associations
in the result imapping are drawn from the first imapping in which they
appear.

Examples:

```
(imapping->alist (imapping-union (imapping 0 'a 2 'c)
(imapping 1 'b 3 'd)))
⇒ ((0 . a) (1 . b) (2 . c) (3 . d))
(imapping->alist
(imapping-intersection (imapping 0 'a 2 'c)
(imapping 1 'b 2 'c 3 'd)
(imapping 2 'c 4 'e)))
⇒ ((2 . c))
(imapping->alist (imapping-difference (imapping 0 'a 1 'b 2 'c)
(imapping 2 "worf")
(imapping 1 "data")))
⇒ ((0 . a))
```

`(imapping-union!`

*imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-intersection!`

*imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-difference!`

*imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-xor!`

*imap*₁ *imap*₂`) → imapping`

These are linear-update variants of
`imapping-union`

, etc.. They may
mutate **any** of the *imap* parameters to
produce their results.

`(imapping-union/combinator`

*proc imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-intersection/combinator`

*proc imap*₁ *imap*₂ *imap*₃ …`) → imapping`

*proc* is a procedure of type `* * → *`

.

Return a new imapping whose set of keys is the union/intersection of
the sets of keys of the *imaps*. The values associated with duplicate
keys are combined left-associatively with *proc*; that is, if an integer *k* is associated
with values *v*₁, *v*₂, …, *v*ₙ in *imap*₁, *imap*₂, …, *imap*ₙ,
respectively, then the resulting imapping will contain the association
(*k*, (*proc* … (*proc v*₁ *v*₂) … *v*ₙ)).

Examples:

```
;; Right-biased union.
(imapping->alist
(imapping-union/combinator (lambda (_l r) r)
(imapping 1 'b 2 'c)
(imapping 2 "data" 3 "picard")))
⇒ ((1 . b) (2 . "data") (3 . "picard"))
(imapping->alist
(imapping-intersection/combinator
(lambda (l r) (string-append l " " r))
(imapping 1 "q" 3 "jean-luc" 5 "miles" 7 "quark")
(imapping 3 "picard" 5 "o'brien")))
⇒ ((3 . "jean-luc picard") (5 . "miles o'brien"))
```

`(imapping-union/combinator!`

*proc imap*₁ *imap*₂ *imap*₃ …`) → imapping`

`(imapping-intersection/combinator!`

*proc imap*₁ *imap*₂ *imap*₃ …`) → imapping`

These are linear-update variants of `imapping-union/combinator`

and `imapping-intersection/combinator`

. They may
mutate **any** of the *imap* parameters to
produce their results.

`(imapping-open-interval`

*imap low high*`) → imapping`

`(imapping-closed-interval`

*imap low high*`) → imapping`

`(imapping-open-closed-interval`

*imap low high*`) → imapping`

`(imapping-closed-open-interval`

*imap low high*`) → imapping`

*low* and *high* are both exact integers.

Procedures that return a subset of *imap* containing the associations
whose keys are contained in the interval from *low* to *high*. The
interval is open/closed/open below and closed above/open
above and closed below.

Examples:

```
(imapping->alist
(imapping-open-interval (imapping 0 'a 1 'b 2 'c 3 'd) 1 3))
⇒ ((2 . c))
(imapping->alist
(imapping-closed-interval (imapping 0 'a 1 'b 2 'c 3 'd) 1 3))
⇒ ((1 . b) (2 . c) (3 . d))
(imapping->alist
(imapping-closed-open-interval (imapping 0 'a 1 'b 2 'c 3 'd) 1 3))
⇒ ((1 . b) (2 . c))
```

`(imapping-open-interval!`

*imap low high*`) → imapping`

`(imapping-closed-interval!`

*imap low high*`) → imapping`

`(imapping-open-closed-interval!`

*imap low high*`) → imapping`

`(imapping-closed-open-interval!`

*imap low high*`) → imapping`

These are linear-update variants of
`imapping-open-interval`

, etc.. They may
mutate and return the *imap* parameter instead of allocating
a new imapping.

`(isubmapping=`

*imap k*`) → imapping`

`(isubmapping<`

*imap k*`) → imapping`

`(isubmapping<=`

*imap k*`) → imapping`

`(isubmapping>`

*imap k*`) → imapping`

`(isubmapping>=`

*imap k*`) → imapping`

Procedures that return an imapping containing the associations of
*imap* whose keys are equal to/less than/less than or equal
to/greater than/greater than or equal to *k*. Note that the result of
`isubmapping=`

contains at most one element.

Examples:

```
(imapping->alist
(isubmapping= (imapping 0 'a 1 'b 2 'c 3 'd) 2))
⇒ ((2 . c))
(imapping->alist
(isubmapping< (imapping 0 'a 1 'b 2 'c 3 'd) 2))
⇒ ((0 . a) (1 . b))
(imapping->alist
(isubmapping>= (imapping 0 'a 1 'b 2 'c 3 'd) 2))
⇒ ((2 . c) (3 . d))
```

`(isubmapping=!`

*imap k*`) → imapping`

`(isubmapping<!`

*imap k*`) → imapping`

`(isubmapping<=!`

*imap k*`) → imapping`

`(isubmapping>!`

*imap k*`) → imapping`

`(isubmapping>=!`

*imap k*`) → imapping`

These are linear-update variants of
`isubmapping=`

, etc.. They may
mutate and return the *imap* parameter instead of allocating
a new imapping.

`(imapping-split`

*imap k*`) → [imapping, imapping]`

Returns two new imappings. The first contains all of the associations
of *imap* whose keys are less than or equal to *k*, and the second
contains the remaining associations. The following are equivalent:

```
(imapping-split imap k)
≡
(values (isubmapping<= imap k) (isubmapping> imap k))
```

If *imap* is empty, then both of the imappings returned by
`imapping-split`

are empty.

Example:

```
(let-values ((imaps (imapping-split (imapping 0 'a 1 'b 2 'c 3 'd) 2)))
(map imapping->alist imaps))
⇒ (((0 . a) (1 . b) (2 . c))
((3 . d)))
```

The sample implementation is found in the repository for this SRFI. The imapping implementation is based on big-endian radix (Patricia) trees as described by Chris Okasaki and Andrew Gill in “Fast Mergeable Integer Maps” (see References). These trees provide fast insert, lookup, and set-theoretical operations. Keys are currently restricted to fixnums.

The implementation should be portable without changes to any R7RS Scheme that provides SRFIs 1, 128, 143, 145, 158, 189, and 217. The provided tests can be run with SRFIs 64 or 78; additional shims for the test libraries preferred by chibi-scheme and CHICKEN are also included.

Thanks to Marc-Nieper Wißkirchen and Arthur A. Gleckler, the authors of SRFI 146, as well as to Daan Leijen and Andriy Palamarchuk, who created the Haskell IntMap library. These libraries provided critical inspiration and implementation clues in the creation of this SRFI.

Thanks to the SRFI editor and to the contributors to the SRFI
mailing list, as well as to those who provided feedback on this SRFI
via the `#scheme`

IRC channel.

This SRFI contains ideas and language drawn from dozens of other
SRFIs, in particular specifications by Olin Shivers, John Cowan, and
Taylor Campbell. The R7RS and earlier standards also provided
constant design and literary guidance. Thus, little of what appears
in this SRFI is “original”. Thanks to all of the Schemers who have
contributed their knowledge and time to the SRFI process and to the
R^{n}RS standards.

Of course, none of this should be understood to imply that any of the individuals mentioned above endorse this SRFI.

Alex Shinn, John Cowan, & Arthur A. Gleckler, eds., *Revised⁷ Report
on the Algorithmic Language Scheme* (R7RS) (2013). Available
on the Web.

Michael Sperber, R. Kent Dybvig, Matthew Flatt, & Anton van
Straaten, eds., *The Revised⁶ Report on the Algorithmic Language
Scheme* (R6RS). Cambridge University Press, 2010. Available
on the Web.

Chris Okasaki & Andrew Gill, “Fast Mergeable Integer Maps”,
1998 *Workshop on ML*, p. 77-86.

S. Bradner, “Key words for use in RFCs to Indicate Requirement Levels”. 1997. http://www.ietf.org/rfc/rfc2119.txt

© 2021 Wolfgang Corcoran-Mathe. All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler