## Title

Integer Mappings

## Author

Wolfgang Corcoran-Mathe

## Status

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
- Revised to fix errata:
  - 2021-09-14 (Fixed an omission in the spec. of `fxmapping-alter`.)

## Abstract

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.

## Rationale

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

## Specification

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.

### Non-local control flow

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.

### Notation

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

### Index

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

### Constructors

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

The arguments have the following types:

- 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 seeds. The mapper is applied to the seeds and returns two values, a key and an associated value, which are adjoined to the new fxmapping. The successor maps the seeds 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`

The arguments have the following types:

- 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 seeds. The procedure proc is applied to a procedure abort-with-result and the seeds, 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"))

### Predicates

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

### Accessors

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

### Updaters

`(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, except for (k, v).

- 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)))

### The whole fxmapping

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

### Traversal

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

### Filter

`(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))

### Conversion

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

### Comparison

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

### Set theory operations

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

### Submappings

`(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)))

## Implementation

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.

## Acknowledgements

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 RnRS standards.

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

## References

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

## Copyright

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