by Wolfgang Corcoran-Mathe

This SRFI is currently in *final* 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
- Draft #1 published: 2021-03-24
- Draft #2 published: 2021-03-29
- Draft #3 published: 2021-04-01
- Draft #4 published: 2021-04-20
- Draft #5 published: 2021-05-12
- Draft #6 published: 2021-05-28
- Draft #7 published: 2021-06-01
- Draft #8 published: 2021-06-08
- Draft #9 published: 2021-06-10
- Draft #10 published: 2021-06-16
- Draft #11 published: 2021-06-19
- Draft #12 published: 2021-06-21
- Draft #13 published: 2021-06-22
- Draft #14 published: 2021-06-26
- Finalized: 2021-06-30

Integer maps, or *fxmappings*, are finite sets, where each element is
an association between a fixnum (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
fxmappings to benefit from optimized structures and algorithms. This
library provides a rich set of operations on fxmappings, including
analogues of most of the forms provided by SRFI 146. Fxmappings have
no intrinsic order, but may be treated as ordered sets, using the
natural ordering on keys; a substantial sublibrary for working with
fxmappings in this fashion is included.

“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 fixnums, a subrange of the exact integers provided by most Schemes (See the R⁶RS § 3.3 and SRFI 143). The fixnum subset is 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,
`fxmapping-adjust`

, `fxmapping-alter`

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

The specification of this SRFI depends on the comparator type (used to determine the equality of values, not keys) described in SRFI 128. Conversions from fxmappings to SRFI 158 generators are provided. The sample implementation has further dependencies; see the appropriate section for more details.

Fxmappings (pronounced "fix-mappings") 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
fxmapping type are unspecified.

In systems supporting R6RS record-type semantics, fxmappings are
instances of a nongenerative record type with uid
`fxmapping-7a1f4d5b-a540-462b-82b1-47283c935b85`

.

Fxmappings represent finite sets of associations whose keys are fixnums, an implementation-defined subset of the exact integers. This is a closed interval,

[-(2 ^ (w- 1)), (2 ^ (w- 1)) - 1],

where *w* is an integer greater than or equal to 24.
Portable code should not assume that *w* is greater than 24.

Fxmappings are immutable in the sense that all of the procedures defined in this SRFI are “pure”, that is, they must not mutate their arguments. If an implementation allows fxmappings to be mutated, the effects of combining mutation and the procedures of this library are unspecified.

The procedures in this SRFI must fully support non-local control
flow, e.g. as created by exception handling or invocation of
continuations. In particular, if multiple returns occur from
a higher-order procedure, such as `fxmapping-unfold`

, then
the values returned by earlier returns must not be mutated.

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 |

fxmap | a fxmapping with values of arbitrary type |

k | a fixnum satisfying SRFI 143's `fixnum?` |

list | a proper list |

alist | an association list |

proc | a procedure |

pred | a predicate that is assumed to have no side effects |

comp | a SRFI 128 comparator object |

Unless otherwise noted, it is an error 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 a fxmapping. Here, *k* is the key and
*v* its associated value. If a fxmapping *fxmap* is said
to "contain the association (*k*,*v*)", then this is to
be understood in the sense that looking up *k* in *fxmap*
(via `(fxmapping-ref`

*fxmap 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. A pair of empty brackets, `[]`

, denotes zero values;
thus a "thunk" (nullary procedure) returning zero or more values is of type
`[] → [*, …]`

.
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`

.

Constructors:

`fxmapping, fxmapping-unfold, fxmapping-accumulate, alist->fxmapping, alist->fxmapping/combinator`

Predicates:

`fxmapping?, fxmapping-contains?, fxmapping-empty?, fxmapping-disjoint?`

Accessors:

`fxmapping-ref, fxmapping-ref/default, fxmapping-min, fxmapping-max`

Updaters:

`fxmapping-adjoin, fxmapping-adjoin/combinator, fxmapping-set, fxmapping-adjust, fxmapping-delete, fxmapping-delete-all, fxmapping-alter, fxmapping-update, fxmapping-delete-min, fxmapping-delete-max, fxmapping-update-min, fxmapping-update-max, fxmapping-pop-min, fxmapping-pop-max`

The whole fxmapping:

`fxmapping-size, fxmapping-find, fxmapping-count, fxmapping-any?, fxmapping-every?`

Traversal:

`fxmapping-fold, fxmapping-fold-right, fxmapping-map, fxmapping-map->list, fxmapping-map->list, fxmapping-for-each, fxmapping-relation-map`

Filter:

`fxmapping-filter, fxmapping-remove, fxmapping-partition`

Conversion:

`fxmapping->alist, fxmapping->decreasing-alist, fxmapping-keys, fxmapping-values, fxmapping->generator, fxmapping->decreasing-generator`

Comparison:

`fxmapping=?, fxmapping<?, fxmapping>?, fxmapping<=?, fxmapping>=?`

Set theory operations:

`fxmapping-union, fxmapping-intersection, fxmapping-difference, fxmapping-xor, fxmapping-union/combinator, fxmapping-intersection/combinator`

Submappings:

`fxmapping-open-interval, fxmapping-closed-interval, fxmapping-open-closed-interval, fxmapping-closed-open-interval, fxsubmapping=, fxsubmapping<, fxsubmapping<=, fxsubmapping>=, fxsubmapping>, fxmapping-split`

`(fxmapping`

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

Constructs a fxmapping from the given arguments, which alternate between keys
and values (which are arbitrary Scheme objects); the
resulting fxmapping is newly allocated and contains these (*k*, *obj*) associations.
The number of arguments must be even. If duplicate keys occur in
the arguments, earlier associations take priority.

Examples:

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

`(fxmapping-unfold`

*stop? mapper successor seed*₁ *seed*₂ …`) → fxmapping`

*stop?*:`* *`

…`→ *-or-false`

*mapper*:`* *`

…`→ [fixnum, *]`

*successor*:`* *`

…`→ * *`

…*seed*₁,*seed*₂, … :`*`

The *stop?*, *mapper*, and *successor*
procedures must accept as many arguments as there are *seed*
parameters. In addition, the number of values returned by the
*successor* procedure must agree with the number of arguments
expected by *mapper*; that is, the expression

`(call-with-values (lambda () (`

successor seed₁seed₂ …`))`

mapper`)`

must result in a valid procedure application.

Unfold a fxmapping from the initial *seed*s.
The *mapper* is applied to the *seed*s and returns two values, a key
and an associated value, which are adjoined to the new fxmapping.
The *successor* maps the *seed*s to new seeds.
Unfolding terminates when the predicate *stop?* returns a true
value when applied to the current seeds. The resulting fxmapping is
newly allocated.

It is an error for the number of seeds to vary between steps of the unfolding process. If different steps of this process produce associations with the same key, then the first such association takes precedence.

Example:

```
(fxmapping->alist
(fxmapping-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"))
```

`(fxmapping-accumulate`

*proc seed*₁ *seed*₂ …`) → fxmapping`

*proc*:`(* … → [fxmapping, *, …]) * *`

…`→ [fixnum, *, *, *, …]`

*seed*₁,*seed*₂, … :`*`

Similar to `fxmapping-unfold`

, except that a single
procedure controls the unfolding of a new fxmapping. Let *n*
be the number of *seed*s. The procedure *proc* is applied to a
procedure *abort-with-result* and the *seed*s, in that order, and is
expected to return *n*` + 2`

values: a key (fixnum), an
associated value, and *n* new seed values. The key/value
association is added to the new fxmapping, and unfolding continues
with the new seeds. If, instead, *abort-with-result* is invoked on any
number of arbitrary values, then the current continuation is discarded
and the new fxmapping along with the arguments passed to *abort-with-result*
are delivered as multiple values to the continuation that was in effect when
`fxmapping-accumulate`

was called.

It is an error for the number of seeds to vary between steps of the unfolding process. If different steps of this process produce associations with the same key, then the first such association takes precedence.

Example:

```
(let-values (((fxmap s)
(fxmapping-accumulate
(lambda (abort-with-result i)
(if (< i -3)
(abort-with-result 'finished)
(values i (square i) (- i 1))))
-1)))
(values (fxmapping->alist fxmap) s))
⇒ ((-3 . 9) (-2 . 4) (-1 . 1))
finished
```

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

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 *fxmapping-unfold*, we'd
have no choice other than to compute *k* and *v* twice:

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

Using `fxmapping-accumulate`

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

```
(fxmapping-accumulate (lambda (abort-with-result s)
(if (stop? s)
(abort-with-result)
(let-values (((k v) (f s)))
(let ((s* …))
(values k v s*)))))
seed)
```

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

`(alist->fxmapping`

*alist*`) → fxmapping`

Returns a newly allocated fxmapping containing the associations of *alist*.
It is an error if the car of any pair in *alist* is not a
fixnum. If an integer *k* appears as the key of multiple
associations in *alist* (i.e. as the car of multiple pairs),
then the first association for *k* is preferred.

Example:

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

`(alist->fxmapping/combinator`

*proc alist*`) → fxmapping`

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

.

Returns a newly allocated fxmapping containing the associations of *alist*.
It is an error if the car of any pair in *alist* is not a
fixnum. If pairs (*k* . *v*₁) and
(*k* . *v*₂) appear (in that order) in *alist*, then
the association
(*k*, (*proc k v*₂ *v*₁)) is
added to the resulting fxmapping; in general, if *k* is associated with
values v₁, …, vₙ in *alist*, then *k* will be associated
with the value of

(proc k vₙ (proc k… (proc k v₂v₁)))

in the resulting fxmapping.

Example:

```
(fxmapping->alist
(alist->fxmapping/combinator (lambda (_k x _y) x)
'((1 . b) (0 . a) (1 . c))))
⇒ ((0 . a) (1 . c))
(fxmapping->alist
(alist->fxmapping/combinator
(lambda (_k s t) (string-append s " " t))
'((1 . "riker") (2 . "yar") (2 . "tasha"))))
⇒ ((1 . "riker") (2 . "tasha yar"))
```

`(fxmapping?`

*obj*`) → boolean`

Returns `#t`

if and only if *obj* is a fxmapping.

`(fxmapping-contains?`

*fxmap k*`) → boolean`

Returns `#t`

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

Examples:

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

`(fxmapping-empty?`

*fxmap*`) → boolean`

Returns `#t`

if and only if *fxmap* contains no associations.

Examples:

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

`(fxmapping-disjoint?`

*fxmap*₁ *fxmap*₂`) → boolean`

Returns `#t`

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

Examples:

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

`(fxmapping-ref`

*fxmap k*` [ `

*failure*` [ `

*success*` ] ]) → * …`

The optional *failure* parameter is a procedure of type
`[] → [*, …]`

. The optional *success* parameter
is a procedure of type `* → [*, …]`

. The *success* procedure
defaults to `values`

.

If an association `(`

*k*, *v*`)`

occurs in *fxmap*, then *success* is invoked in tail
context on *v*, and its values are returned. If *k* does
not have an association in *fxmap* and *failure* is
supplied, then it is invoked in tail context on no arguments, and
its values are returned. Otherwise, it is an error.

Examples:

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

`(fxmapping-ref/default`

*fxmap k obj*`) → *`

If an association `(`

*k*, *v*`)`

occurs in *fxmap*, returns *v*.
Otherwise, returns *obj*.

Examples:

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

`(fxmapping-min`

*fxmap*`) → [fixnum, *]`

Returns two values: the least key of *fxmap* and its
associated value. It is an error if *fxmap* is empty.

Example:

```
(fxmapping-min (fxmapping 0 'a 1 'b 2 'c)) ⇒ 0 a
```

`(fxmapping-max`

*fxmap*`) → [fixnum, *]`

Returns two values: the greatest key of *fxmap* and its
associated value. It is an error if *fxmap* is empty.

Example:

```
(fxmapping-max (fxmapping 0 'a 1 'b 2 'c)) ⇒ 2 c
```

`(fxmapping-adjoin`

*fxmap k*₁ *obj*₁ *k*₂ `…) → fxmapping`

Returns a fxmapping containing all of the associations of
*fxmap* as well as the associations (*k*₁, *obj*₁),
(*k*₂, *obj*₂), ….
The number of key/value arguments must be even.

If any of the keys already have associations in *fxmap*, the old
associations are preserved.

Examples:

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

`(fxmapping-adjoin/combinator`

*fxmap proc k*₁ *obj*₁ *k*₂ `…) → fxmapping`

Similar to `fxmapping-adjoin`

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

.
The *proc* procedure is called on the new and old values (in that order) associated
with a duplicated key, and is expected to return a value to be
associated with that key in the resulting fxmapping. For example, if
*fxmap* contains the association (*k*, *v*₁), then
the value of
`(fxmapping-adjoin/combinator`

*fxmap f k v*₂`)`

will be a fxmapping with the association
(*k*, (*f k v*₂ *v*₁)).

Example:

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

`(fxmapping-set`

*fxmap k*₁ *obj*₁ *k*₂ `…) → fxmapping`

`fxmapping-set`

is the same as `fxmapping-adjoin`

,
except that any existing associations for *k*₁, *k*₂, … are
replaced.

Example:

```
(fxmapping->alist
(fxmapping-set (fxmapping 0 "geordi" 1 "reginald")
1
"tasha"))
⇒ ((0 . "geordi") (1 . "tasha"))
```

`(fxmapping-adjust fxmap k proc) → fxmapping`

The *proc* parameter of `fxmapping-adjust`

is a
procedure of type `fixnum * → *`

.

Returns a fxmapping in which the association (*k*, *v*) in *fxmap*
is replaced by (*k*, (*proc k v*)). If *k* has
no association in *fxmap*,
then a fxmapping with the same associations as *fxmap* is returned.

Examples:

```
(fxmapping->alist
(fxmapping-adjust (fxmapping 64 "var")
64
(lambda (k s)
(string-append s (number->string k)))))
⇒ ((64 . "var64"))
```

`(fxmapping-delete fxmap`

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

Returns a fxmapping with the same associations as *fxmap*, except
those with keys equal to one of *k*₁, *k*₂, ….

Example:

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

`(fxmapping-delete-all`

*fxmap list*`) → fxmapping`

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

Example:

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

`(fxmapping-update`

*fxmap k proc*` [ `

*failure*` ]) → *`

…

The procedure *proc* is of type
`fixnum * (* → fxmapping) ([] → fxmapping) → *`

….
If the optional *failure* parameter is provided, then it must
be a procedure of type `[] → [*, …]`

.

Updates the association for *k* in *fxmap* as follows.
If *k* has an association in *fxmap*, then *proc* is
invoked in tail context on *k*, its associated value, and two procedure arguments,
*replace* and *delete*, and its values are returned.
Invoking *replace* on a value *v* returns a fxmapping with
the association (*k*, *v*) and all of *fxmap*'s other
associations.
Invoking *delete* returns a fxmapping with all of the associations of
*fxmap*, but without an association for *k*.
If *k* has no association in *fxmap* and *failure*
is provided, then *failure* is invoked in tail context on no
arguments and its values are returned. Otherwise, it is an error.

Note that, in contrast to similar Scheme forms, *proc* is
not required to tail-call one of *delete* or *replace*,
and that `fxmapping-update`

simply returns the results of
invoking *proc* (assuming *k* is found).
Thus, the following is valid:

```
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (k v replace _del)
(values k
v
(fxmapping->alist (replace 'z)))))
⇒ 1
b
((0 . a) (1 . z) (2 . c))
```

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

, e.g.:

```
(fxmapping-delete fxmap k)
≡
(fxmapping-update fxmap k (lambda (_k _v _r delete) (delete)))
(fxmapping-set fxmap k v)
≡
(fxmapping-update fxmap
k
(lambda (_k _u replace _d) (replace v)))
```

Examples:

```
;; Delete the association for 1 if its value is a symbol.
(fxmapping->alist
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (_k v replace delete)
(if (symbol? v)
(delete)
(replace v)))))
⇒ ((0 . a) (2 . c))
(fxmapping->alist
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (k _v replace _d)
(replace k)))))
⇒ ((0 . a) (1 . 1) (2 . c))
```

`(fxmapping-alter`

*fxmap k failure success*`) → *`

…

The procedure *failure* is of type
`(* → fxmapping) ([] → fxmapping) → [*, …]`

.
The procedure *success* is of type
`fixnum * (* → fxmapping) ([] → fxmapping) → [*, …]`

.

Updates the association, or lack thereof, for *k* in *fxmap* as
follows. If the association (*k*, *v*) exists in *fxmap*,
then *success* is invoked in tail context on *k*, *v*, and two procedure
arguments, *replace* and *delete*, and its values are
returned.

Invoking

`(`

*replace v′*`)`

returns a fxmapping with the association (*k*,*v′*) as well as all of*fxmap*’s other associations.Invoking

`(`

*delete*`)`

returns a fxmapping with all of*fxmap*’s associations except for (*k*,*v*).

If no association for *k* exists in *fxmap*, then
*failure* is invoked in tail context on two procedure arguments, *insert* and
*ignore*, and its values are returned.

Invoking

`(`

*insert u*`)`

returns a fxmapping with all of the associations of*fxmap*as well as (*k*,*u*).Invoking

`(`

*ignore*`)`

returns a fxmapping with the same associations as*fxmap*.

Note that, in contrast to similar Scheme forms, *failure* and
*success* are not required to tail-call one of their procedure
arguments, and that `fxmapping-alter`

simply returns the
results of invoking *failure* or *success*. Thus, the
following is valid:

```
;; Returns an additional boolean value indicating
;; whether the fxmapping was updated.
(fxmapping-alter (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (_ins ignore)
(values (ignore) #f))
(lambda (_k _v replace _del)
(values (replace 'z) #t)))
⇒ <fxmapping>
#t
```

Examples:

```
;; Insert an association for 4 if it's not present.
(fxmapping->alist
(fxmapping-alter (fxmapping 0 'a 1 'b)
4
(lambda (insert _ig) (insert 'e))
(lambda (_k v replace _del)
(replace v)))) ; keep original value
⇒ ((0 . a) (1 . b) (4 . e))
;; Delete an association for 1 if its value is a symbol.
(fxmapping->alist
(fxmapping-alter (fxmapping 0 'a 1 'b)
1
(lambda (_ins ignore) (ignore))
(lambda (_k v replace delete)
(if (symbol? v)
(delete)
(replace v)))))
⇒ ((0 . a))
```

`(fxmapping-delete-min`

*fxmap*`) → fxmapping`

`(fxmapping-delete-max`

*fxmap*`) → fxmapping`

Returns a fxmapping with the same associations as *fxmap* except
for the association with the least/greatest key. It is an error if
*fxmap* is empty.

Examples:

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

`(fxmapping-update-min`

*fxmap proc*`) → *`

…

`(fxmapping-update-max`

*fxmap proc*`) → *`

…

The *proc* argument of `fxmapping-update-min`

and `-max`

is of
type `fixnum * (* → fxmapping) ([] → fxmapping) → *`

….

Updates the association of *fxmap* with the least/greatest key
*k* as follows. Procedure *proc* is invoked in tail context on *k*, its
associated value, and two procedure arguments, *replace* and
*delete*, and its values are returned. Invoking
*replace* on a value *v* returns a fxmapping with
the association (*k*, *v*) and all of *fxmap*'s other
associations. Invoking *delete* returns a fxmapping with all of
the associations of *fxmap*, but without an association for
*k*. It is an error if *fxmap* is empty.

Note that, in contrast to similar Scheme forms, *proc* is
not required to tail-call one of *delete* or *replace*,
and that `fxmapping-update-min`

and `-max`

simply
return the results of invoking *proc*. Thus, the following is
valid:

```
(fxmapping-update-min
(fxmapping 0 'a 1 'b 2 'c)
(lambda (k v _r delete)
(values k v (fxmapping->alist (delete)))))
⇒ 0
a
((1 . b) (2 . c))
```

Examples:

```
(fxmapping->alist
(fxmapping-update-min (fxmapping -5 "phaser" -1 "tricorder")
(lambda (_ v replace delete)
(if (symbol? v)
(replace v)
(delete)))))
⇒ ((-1 . "tricorder"))
(fxmapping->alist
(fxmapping-update-max (fxmapping -5 "phaser" -1 "tricorder")
(lambda (k v replace delete)
(if (and (negative? k) (string? v))
(replace (string-length v))
(delete)))))
⇒ ((-5 . "phaser") (-1 . 9))
```

`(fxmapping-pop-min`

*fxmap*`) → [fixnum, *, fxmapping]`

`(fxmapping-pop-max`

*fxmap*`) → [fixnum, *, fxmapping]`

Returns three values: *k*, *v*, and *fxmap′*,
where (*k*, *v*) is the association of
*fxmap* with the least/greatest key and *fxmap′* is a
fxmapping containing all of the associations of *fxmap* except for
(*k*, *v*). It is an error if *fxmap* is empty.

Example:

```
(let-values (((k v fxmap)
(fxmapping-pop-min (fxmapping 0 'a 1 'b 2 'c))))
(values k v (fxmapping->alist fxmap)))
⇒ (0 a ((1 . b) (2 . c)))
```

`(fxmapping-size`

*fxmap*`) → fixnum`

Returns the number of associations in *fxmap*.

`(fxmapping-find`

*pred fxmap failure*` [ `

*success*` ])`

→ `[*, …]`

Procedure *pred* is a predicate of type `fixnum * → boolean`

.
Procedure *failure* is of type `[] → [*, …]`

.
If the optional *success* parameter is supplied, then it must be
a procedure of type `fixnum * → [*, …]`

. Procedure *success*
defaults to `values`

.

Invokes *success* in tail context on *k* and
*v* and returns it results, where (*k*, *v*)
is the association of *fxmap* with the least key such that
`(`

*pred k v*`)`

is true.
If there is no
such association, then *failure* is tail-called with no
arguments and its results are returned.

Examples:

```
(fxmapping-find (lambda (_ v) (even? v))
(fxmapping 0 1 1 2 2 4 3 8)
(lambda () (values #f #f)))
⇒ 1 2
(fxmapping-find (lambda (_ v) (negative? v))
(fxmapping 0 1 1 2 2 4 3 8)
(lambda () (values 'nope 'nada)))
⇒ nope nada
(fxmapping-find (lambda (k s) (= k (string-length s)))
(fxmapping 2 "worf" 3 "data" 4 "troi")
(lambda () (error "not found"))
list)
⇒ (4 "troi")
```

`(fxmapping-count`

*pred fxmap*`) → fixnum`

Procedure *pred* is a predicate of type
`fixnum * → boolean`

.

Returns the number of associations in *fxmap* that satisfy
*pred* (in the sense of `fxmapping-find`

).

Examples:

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

`(fxmapping-any?`

*pred fxmap*`) → boolean`

Procedure *pred* is a predicate of type
`fixnum * → boolean`

.

Returns `#t`

if and only if there exists an association
in *fxmap* that satisfies *pred* (in the sense of
`fxmapping-find`

). The *fxmap* is traversed in ascending
numerical order of keys.

Example:

```
(fxmapping-any? (lambda (_ v) (odd? v))
(fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t
```

`(fxmapping-every?`

*pred fxmap*`) → boolean`

Procedure *pred* is a predicate of type
`fixnum * → boolean`

.

Returns `#t`

if and only every association in
*fxmap* satisfies *pred* (in the sense of
`fxmapping-find`

), or if *fxmap* is empty.
The *fxmap* is traversed in ascending numerical order of keys.

Example:

```
(fxmapping-every? (lambda (_ v) (integer? v))
(fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t
```

`(fxmapping-map`

*proc fxmap*`) → fxmapping`

The *proc* argument of `fxmapping-map`

is of type
`fixnum * → *`

.

Returns a fxmapping with the same keys as *fxmap* whose values
are the result of transforming the values of *fxmap* with *proc*.
For each association
`(`

*k, v*`)`

in *fxmap*, the association
`(`

*k*`, (`

*proc k v*`))`

is added to the resulting fxmapping.
The dynamic order
of the applications of *proc* to the elements of *fxmap* is
unspecified.

Examples:

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

Note that, in contrast to SRFI 146’s `mapping-map`

procedure, this procedure transforms the values of *fxmap* only;
that is, the set of keys of the resulting fxmapping is the same as that
of *fxmap*.

`(fxmapping-for-each`

*proc fxmap*`) → unspecified`

Procedure *proc* is of type `fixnum * → *`

.

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

Example:

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

`(fxmapping-fold`

*kons knil fxmap*`) → *`

`(fxmapping-fold-right`

*kons knil fxmap*`) → *`

The *kons* argument of `fxmapping-fold`

and `fxmapping-fold-right`

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

.
The *knil* argument is an object of any type which can be passed to *kons*
as its third argument.

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

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

folds in descending order.

Examples:

```
(fxmapping-fold-right
(lambda (_ v vs) (cons v vs))
'()
(fxmapping 0 "worf" 1 "data" 2 "crusher"))
⇒ ("worf" "data" "crusher")
(fxmapping-fold (lambda (k _ ks) (cons k ks))
'()
(fxmapping 0 "worf" 1 "data" 2 "crusher"))
⇒ (2 1 0)
```

`(fxmapping-map->list`

*proc fxmap*`) → list`

Equivalent to
`(fxmapping-values (fxmapping-map`

*proc fxmap*`))`

,
but may be implemented more efficiently.

Example:

```
(fxmapping-map->list
(lambda (_ v) (string-length v))
(fxmapping 0 "picard" 1 "riker" 2 "troi"))
⇒ (6 5 4)
```

`(fxmapping-relation-map`

*proc fxmap*`) → fxmapping`

Procedure *proc* must be of type
`fixnum * → [fixnum, *]`

.

Returns a fxmapping whose associations are the results of
transforming both the keys and the values of *fxmap* with
*proc*. For each association (*k*,
*v*) in *fxmap*, (*proc k v*) is evaluated to
return a new key and a new value which are associated in the new
fxmapping. 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
fxmapping. The dynamic order of the applications of *proc* to the
elements of *fxmap* is unspecified.

**Rationale:** `fxmapping-relation-map`

corresponds to `mapping-map`

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

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

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

; in particular, the size of
the *fxmap* may not be preserved, and a key with an
association in *fxmap* may not have an association in the
resulting fxmapping.

As such, `fxmapping-map`

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

`(fxmapping-filter`

*pred fxmap*`) → fxmapping`

Returns a fxmapping containing all of the associations of *fxmap*
that satisfy *pred* (in the sense of `fxmapping-find`

).

Example:

```
(fxmapping->alist
(fxmapping-filter (lambda (_ v) (positive? v))
(fxmapping 0 2 1 -4 2 8 3 -16)))
⇒ ((0 . 2) (2 . 8))
```

`(fxmapping-remove`

*pred fxmap*`) → fxmapping`

Returns a fxmapping containing all of the associations of
*fxmap* that do not satisfy *pred* (in the sense of
`fxmapping-find`

).

Example:

```
(fxmapping->alist
(fxmapping-remove (lambda (_ v) (positive? v))
(fxmapping 0 2 1 -4 2 8 3 -16)))
⇒ ((1 . -4) (3 . -16))
```

`(fxmapping-partition`

*pred fxmap*`) → [fxmapping, fxmapping]`

Returns two fxmappings. The first contains all associations of
*fxmap* that satisfy *pred* (in the sense of
`fxmapping-find`

), and the second contains those
that do not.

Example:

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

`(fxmapping->alist`

*fxmap*`) → alist[fixnum, *]`

Returns an alist containing the associations of
*fxmap* in increasing numerical order of key.
That is, if (*k*₁, *v*₁), …, (*k*ₙ,
*v*ₙ) are the associations of *fxmap* ordered so that
*k*₁ ≤ … ≤ *k*ₙ, then
`(fxmapping->alist`

*fxmap*`)`

produces the list `((`

*k*₁ `.`

*v*₁`)`

… `(`

*k*ₙ
`.`

*v*ₙ`))`

.

Example:

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

`(fxmapping->decreasing-alist`

*fxmap*`) → alist[fixnum, *]`

Identical to `fxmapping->alist`

, except that the
resulting alist contains the associations of *fxmap* in
decreasing numerical order of key.

Example:

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

`(fxmapping-keys`

*fxmap*`) → list[fixnum]`

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

Example:

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

`(fxmapping-values`

*fxmap*`) → list[*]`

Returns the values of *fxmap* as a list in ascending numerical
order of key.
That is, if (*k*₁, *v*₁), …, (*k*ₙ,
*v*ₙ) are the associations of *fxmap* ordered so that
*k*₁ ≤ … ≤ *k*ₙ, then
`(fxmapping-values`

*fxmap*`)`

produces the list
`(`

*v*₁ … *v*ₙ`)`

.

Example:

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

`(fxmapping->generator`

*fxmapping*`) → generator[pair(fixnum, *)]`

Returns a SRFI 158 generator which
produces the associations of *fxmapping* as key/value pairs in increasing
order of key. That is, if (*k*₁, *v*₁), …, (*k*ₙ,
*v*ₙ) are the associations of *fxmap* ordered so that
*k*₁ ≤ … ≤ *k*ₙ, then the generator returned by
`(fxmapping->generator`

*fxmap*`)`

produces the pairs `(`

*k*₁ `.`

*v*₁`)`

, …, `(`

*k*ₙ
`.`

*v*ₙ`)`

, in that order.

Example:

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

`(fxmapping->decreasing-generator`

*fxmapping*`) → generator[pair(fixnum, *)]`

This is the same as `fxmapping->generator`

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

Example:

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

Each of the following predicates takes a
SRFI 128 comparator
argument which is used to compare the values of the associations of
two fxmappings. (Keys are always compared as if with `=`

.)

Note that none of these five predicates produces a total order on
fxmappings. In particular, `fxmapping=?`

, `fxmapping<?`

,
and `fxmapping>?`

do not obey the
trichotomy law.

`(fxmapping=?`

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

Returns `#t`

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

) and their values are equal in the sense
of the equality predicate of *comp*.

Examples:

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

`(fxmapping<?`

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

`(fxmapping<=?`

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

`(fxmapping>?`

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

`(fxmapping>=?`

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

Returns `#t`

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

Examples:

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

`(fxmapping-union`

*fxmap*₁ *fxmap*₂ *fxmap*₃ …`) → fxmapping`

`(fxmapping-intersection`

*fxmap*₁ *fxmap*₂ *fxmap*₃ …`) → fxmapping`

`(fxmapping-difference`

*fxmap*₁ *fxmap*₂ *fxmap*₃ …`) → fxmapping`

`(fxmapping-xor`

*fxmap*₁ *fxmap*₂`) → fxmapping`

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

Examples:

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

`(fxmapping-union/combinator`

*proc fxmap*₁ *fxmap*₂ *fxmap*₃ …`) → fxmapping`

`(fxmapping-intersection/combinator`

*proc fxmap*₁ *fxmap*₂ *fxmap*₃ …`) → fxmapping`

Procedure *proc* is of type `fixnum * * → *`

.

Return a fxmapping whose set of keys is the union/intersection of
the sets of keys of the *fxmaps*. The values associated with duplicate
keys are combined left-associatively with *proc*, which is also passed
the duplicated key as its first argument; that is, if an integer *k* is associated
with values *v*₁, *v*₂, …, *v*ₙ in *fxmap*₁, *fxmap*₂, …, *fxmap*ₙ,
respectively, then the resulting fxmapping will contain the association
(*k*, (*proc k* … (*proc k v*₁ *v*₂) … *v*ₙ)).

Examples:

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

`(fxmapping-open-interval`

*fxmap low high*`) → fxmapping`

`(fxmapping-closed-interval`

*fxmap low high*`) → fxmapping`

`(fxmapping-open-closed-interval`

*fxmap low high*`) → fxmapping`

`(fxmapping-closed-open-interval`

*fxmap low high*`) → fxmapping`

Arguments *low* and *high* are both fixnums.

Procedures that return a subset of *fxmap* 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:

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

`(fxsubmapping=`

*fxmap k*`) → fxmapping`

`(fxsubmapping<`

*fxmap k*`) → fxmapping`

`(fxsubmapping<=`

*fxmap k*`) → fxmapping`

`(fxsubmapping>`

*fxmap k*`) → fxmapping`

`(fxsubmapping>=`

*fxmap k*`) → fxmapping`

Procedures that return a fxmapping containing the associations of
*fxmap* 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
`fxsubmapping=`

contains at most one element.

Examples:

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

`(fxmapping-split`

*fxmap k*`) → [fxmapping, fxmapping]`

Returns two fxmappings. The first contains all of the associations
of *fxmap* whose keys are less than or equal to *k*, and the second
contains the remaining associations. This is equivalent to
`(values (fxsubmapping<=`

*fxmap k*```
)
(fxsubmapping>
```

*fxmap k*`))`

, but may be
implemented more efficiently.

If *fxmap* is empty, then both of the fxmappings returned by
`fxmapping-split`

are empty.

Example:

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

The sample implementation is found in the repository for this SRFI. The fxmapping 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.

The implementation should be portable without changes to any R7RS Scheme that provides SRFIs 1, 128, and 143. 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