224: Integer Mappings

by Wolfgang Corcoran-Mathe

Status

This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-224@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

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

Issues

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

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 exact integers. This is a ubiquitous type in computing, and broadly useful as a key-type for mappings; its use opens up a range of implementation options.

This library provides an interface similar to that used by SRFI 146, although it diverges in some areas. In addition, imapping-adjust, imapping-alter, and several other forms derive from Haskell’s IntMap library.

Many forms make instrumental use of SRFI 189’s Maybe type; I believe that this choice results in simpler, more compositional definitions. (Compare, for instance, the conventional imapping-ref form with imapping-lookup.) Where the use of Maybe values would clarify nothing, I have preferred the traditional “value or #f” Lisp protocol.

This library provides “with-key” variants for many staple higher-order procedures (e.g. map, fold, etc.). These variants, indicated by the suffix -/key, call their auxiliary functions on both the keys and values of an imapping (possibly along with other parameters). A smaller library proposal might eschew variant forms of a procedure; consider, for example, the single index-and-value form of vector-map from SRFI 133. However, this creates unnecessary inflexibility and incompatibility between SRFIs. In practice, the added complexity of providing variant higher-order forms is minimal, and their availability can be a boon to both the programmer and the standardizer.

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

Specification

Imappings form a new type, as if created by define-record-type (see R7RS § 5.5). The effects of using record-type inspection or inheritance for the imapping type are unspecified.

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

Exact integers

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

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

Implementations may support bignum keys.

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:

objAny Scheme object.
booleanA boolean.
imapAn integer map (imapping).
kAn exact integer.
listA proper list.
alistAn association list.
procA procedure.
mprocA procedure returning a Maybe object.
predA predicate.
compA SRFI 128 comparator object.

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

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

Each procedure is written in the form

(proc arg₁ arg₂) → [type₁, type₂, …]

where proc is the name of the procedure, the args are its parameters, and the types are the types of the objects it returns. If the procedure returns a single value, the brackets on the right-hand side may be omitted. The types refer (informally) to Scheme types; e.g. boolean denotes a Scheme boolean, list[integer] denotes a list of integers, etc. The special notation ‘*’ indicates that the type of the value may be anything, depending on the context of the procedure call. For example, Scheme’s list-ref procedure would be written

(list-ref list k) → *

since the type of the return value depends on list. Multiple * values appearing in the same type signature do not necessarily denote the same type. For example, the signature * * → boolean might denote the type of a procedure taking two values of the same type to a boolean, or two values of differing types. The accompanying description may clarify the semantics of procedures defined on * values, but Scheme's type system makes it difficult to explain all of the possible interactions of these procedures.

A procedure which returns a value of type τ-or-false (where τ denotes a type) returns a τ on success, and #f otherwise. Thus the memv procedure of R7RS would have the type signature * list[*] → list[*]-or-false.

Linear update

The procedures of this SRFI, by default, are "pure functional" — they do not alter their parameters. However, this SRFI also defines "linear-update" procedures, all of whose names end in !. They have hybrid pure/side-effecting semantics: they are allowed, but not required, to side-effect one of their parameters in order to construct their result. An implementation may legally implement these procedures as pure, side-effect-free functions, or it may implement them using side effects, depending upon the details of what is the most efficient or simple to implement in terms of the underlying representation.

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

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

However, this is well-defined:

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

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

There are two benefits to this convention:

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

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

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

Index

Constructors

(imapping kobjk…) → imapping

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

Examples:

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

(imapping-unfold stop? mapper successor seed) → imapping

The arguments have the following types:

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

Example:

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

(imapping-unfold-maybe mproc seed) → imapping

The arguments have the following types:

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

Example:

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

Rationale: As well as sometimes leading to more compact expressions than the traditional "three procedure" unfold, imapping-unfold-maybe is also more efficient when the programmer wants the value of each new seed to depend on the computed key and value. For example, assume that we apply some procedure f to a seed s to get a key k and a value v, and that we also want to compute a new seed from k and v. Using imapping-unfold, we'd have no choice other than to compute k and v twice:

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

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

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

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

(alist->imapping alist) → imapping

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

Example:

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

(iset->imapping proc iset) → imapping

proc is of type exact-integer → *.

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

Example:

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

Predicates

(imapping? obj) → boolean

Returns #t if and only if obj is an imapping.

(imapping-contains? imap k) → boolean

Returns #t if and only if imap contains an association for key k.

Examples:

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

(imapping-empty? imap) → boolean

Returns #t if and only if imap contains no associations.

Examples:

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

(imapping-disjoint? imapimap) → boolean

Returns #t if and only if imap₁ and imap₂ have no keys in common.

Examples:

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

Accessors

(imapping-ref imap k [ failure [ success ] ]) → *

If the optional failure parameter is supplied, then it must be a procedure of no arguments returning zero or more values of arbitrary type. The optional success parameter is a procedure of type * → *. failure defaults to a procedure which signals an error; success defaults to values.

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

Examples:

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

(imapping-ref/default imap k obj) → *

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

Examples:

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

(imapping-lookup imap k) → maybe[*]

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

Examples:

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

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

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

Examples:

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

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

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

Examples:

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

Updaters

(imapping-adjoin imap kobjk…) → imapping

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

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

Examples:

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

(imapping-adjoin! imap kobjk…) → imapping

imapping-adjoin! is the same as imapping-adjoin, except that it may mutate and return the imap argument instead of allocating a new imapping.

(imapping-adjoin/combinator imap proc kobjk…)

Similar to imapping-adjoin, except that duplicate associations are combined with proc, which is a procedure of type * * → *. proc is called on the new and old values (in that order) associated with a duplicated key and is expected to return a value for the key.

Example:

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

(imapping-adjoin/combinator! imap proc kobjk…)

imapping-adjoin/combinator! is the same as imapping-adjoin/combinator, except that it may mutate and return the imap argument instead of allocating a new imapping.

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

The proc parameter of imapping-adjust is a procedure of type * → *; that of imapping-adjust/key is of type exact-integer * → *.

Returns a new imapping in which the association (k, v) in imap is replaced by (k, (proc v)), or by (k, (proc k v)) in the case of imapping-adjust/key. If k has no association in imap, then a copy of imap is returned.

Examples:

(imapping->alist (imapping-adjust (imapping 0 -200 1 -100) 0 abs))
 ⇒ '((0 . 200) (1 -100))

(imapping->alist
 (imapping-adjust/key (imapping 64 "var")
                      64
                      (lambda (k s) (string-append s (number->string k)))))
 ⇒ ((64 . "var64"))

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

imapping-adjust! and imapping-adjust/key! are the same as imapping-adjust and imapping-adjust/key, respectively, except that they may mutate and return the imap argument instead of allocating a new imapping.

(imapping-delete imap kk…) → imapping

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

Example:

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

(imapping-delete! imap kk…) → imapping

imapping-delete! is the same as imapping-delete, except that it may mutate and return the imap argument instead of allocating a new imapping.

(imapping-delete-all imap list) → imapping

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

Example:

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

(imapping-delete-all! imap list) → imapping

imapping-delete-all! is the same as imapping-delete-all, except that it may mutate and return the imap argument instead of allocating a new imapping.

(imapping-update imap k mproc) → imapping
(imapping-update/key imap k mproc) → imapping

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

imapping-update/key is the same as imapping-update, except that mproc is called on n and its associated value, in that order.

Simple versions of several other update operations may be defined in terms of imapping-update, e.g.:

  (imapping-delete imap k)
   ≡
  (imapping-update imap k (lambda (_) (nothing)))

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

Examples:

;; Delete the association for 1 if its value is a symbol.
(imapping->alist
 (imapping-update (imapping 0 'a 1 'b 2 'c)
                  1
                  (lambda (v)
                    (if (symbol? v)
                        (nothing)
                        (just v)))))
 ⇒ ((0 . a) (2 . c))

;; Replace the value associated with 1.
(imapping->alist
 (imapping-update/key (imapping 0 'a 1 'b 2 'c) 1 (lambda (k _v) (just k))))
 ⇒ ((0 . a) (1 . 1) (2 . c))

(imapping-update! imap k mproc) → imapping
(imapping-update/key! imap k mproc) → imapping

imapping-update! and imapping-update/key! are the same as imapping-update and imapping-update/key, respectively, except that they may mutate and return the imap argument instead of allocating a new imapping.

(imapping-alter imap k proc) → imapping

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

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

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

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

Examples:

;; Insert an association for 4 if it's not present.
(imapping->alist
 (imapping-alter (imapping 0 'a 1 'b)
                 4
                 (lambda (m)
                   (if (nothing? m) (just 'e) m))))
 ⇒ ((0 . a) (1 . b) (4 . e))

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

(imapping-alter! imap k proc) → imapping

imapping-alter! is the same as imapping-alter, except that it may mutate and return the imap argument instead of allocating a new imapping.

(imapping-delete-min imap) → imapping
(imapping-delete-max imap) → imapping

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

(imapping-delete-min! imap) → imapping
(imapping-delete-max! imap) → imapping

imapping-delete-min! and imapping-delete-max! are the same as imapping-delete-min and imapping-delete-max, respectively, except that they may mutate and return the imap argument instead of allocating a new imapping.

Examples:

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

(imapping-update-min imap mproc) → imapping
(imapping-update-max imap mproc) → imapping
(imapping-update-min/key imap mproc) → imapping
(imapping-update-max/key imap mproc) → imapping

The mproc argument of imapping-update-min and -max is of type * → maybe[*]; that of imapping-update-min/key and of -max/key is of type exact-integer * → maybe[*].

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

imapping-update-min/key and imapping-update-max/key are the same as imapping-update-min and imapping-update-max, respectively, except that mproc is called on k and its associated value, in that order.

Examples:

(imapping->alist
 (imapping-update-min (imapping -5 "phaser" -1 "tricorder")
                      (lambda (v)
                        (if (symbol? v)
                            (just v)
                            (nothing)))))
 ⇒ ((-1 . "tricorder"))

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

(imapping-update-min! imap mproc) → imapping
(imapping-update-max! imap mproc) → imapping
(imapping-update-min/key! imap mproc) → imapping
(imapping-update-max/key! imap mproc) → imapping

These are linear-update variants of imapping-update-min, etc.. They may mutate and return the imap argument instead of allocating a new imapping.

(imapping-pop-min imap) → maybe[exact-integer, *, imapping]
(imapping-pop-max imap) → maybe[exact-integer, *, imapping]

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

Example:

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

(imapping-pop-min! imap) → maybe[exact-integer, *, imapping]
(imapping-pop-max! imap) → maybe[exact-integer, *, imapping]

imapping-pop-min! and imapping-pop-max! are the same as imapping-pop-min and imapping-pop-max, respectively, except that they may mutate and return the imap argument instead of allocating a new imapping.

The whole imapping

(imapping-size imap) → exact-integer

Returns the number of associations in imap.

(imapping-count pred imap) → exact-integer
(imapping-count/key pred imap) → exact-integer

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

imapping-count/key is the same, except that pred is called on the key and value of each association.

Examples:

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

(imapping-any? pred imap) → boolean

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

Example:

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

(imapping-every? pred imap) → boolean

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

Example:

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

Traversal

(imapping-map proc imap) → imapping
(imapping-map/key proc imap) → imapping

The proc argument of imapping-map is of type * → *; that of imapping-map/key is of type exact-integer * → *.

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

imapping-map/key is the same, except that proc is called on the key and value of each association.

Examples:

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

(imapping->alist
 (imapping-map/key (lambda (k s)
                     (string-append s (number->string k)))
                   (imapping 256 "x" 512 "y" 1024 "z")))
 ⇒ ((256 . "x256") (512 . "y512") (1024 . "z1024"))

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

(imapping-map! proc imap) → imapping
(imapping-map/key! proc imap) → imapping

imapping-map! and imapping-map/key! are the same as imapping-map and imapping-map/key, respectively, except that they may mutate and return the imap argument instead of allocating a new imapping.

(imapping-for-each proc imap) → unspecified
(imapping-for-each/key proc imap) → unspecified

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

imapping-for-each/key is the same, except that proc is called on the key and value of each association.

Example:

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

(imapping-fold kons knil imap) → *
(imapping-fold-right kons knil imap) → *
(imapping-fold/key kons knil imap) → *
(imapping-fold-right/key kons knil imap) → *

The kons argument of imapping-fold and imapping-fold-right is a procedure of type * * → *; that of imapping-fold/key and of imapping-fold-right/key is of type exact-integer * * → *. knil can be any object.

Folds kons over imap, using knil as the base value. At each step, kons is applied to the value of an association and to the result of the last application. imapping-fold folds in ascending numerical order of keys; imapping-fold-right folds in descending order.

imapping-fold/key and imapping-fold-right/key are the same as imapping-fold and imapping-fold-right, respectively, except that kons is also passed the key of each association as its first argument.

Examples:

(imapping-fold-right cons '() (imapping 0 "worf" 1 "data" 2 "crusher"))
 ⇒ ("worf" "data" "crusher")

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

(imapping-map->list proc imap) → list
(imapping-map/key->list proc imap) → list

Efficient fusion of (imapping-values (imapping-map proc imap)).

imapping-map/key->list is the same, except that proc is called on the key and value of each association.

Example:

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

(imapping-filter-map proc imap) → imapping
(imapping-filter-map/key proc imap) → imapping

The proc parameter of imapping-filter-map is a procedure of type * → *-or-#f; that of imapping-filter-map/key is of type exact-integer * → *-or-#f.

imapping-filter-map is similar to imapping-map, but only associations for which proc returns a true value are added to the new imapping.

imapping-filter-map/key is the same, except that proc is called on the key and value of each association.

Example:

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

(imapping-filter-map! proc imap) → imapping
(imapping-filter-map/key! proc imap) → imapping

imapping-filter-map! and imapping-filter-map/key! are the same as imapping-filter-map and imapping-filter-map/key, respectively, except that they may mutate and return the imap argument instead of allocating a new imapping.

(imapping-map-either proc imap) → [imapping, imapping]
(imapping-map-either/key proc imap) → [imapping, imapping]

The proc of imapping-map-either is a procedure of type * → either[*], where either[*] denotes a SRFI 189 Either containing a single value. The proc parameter of imapping-map-either/key is of type exact-integer * → either[*].

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

imapping-map-either/key is the same, except that proc is called on the key and value of each association.

Example:

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

(imapping-map-either! proc imap) → imapping imapping
(imapping-map-either/key! proc imap) → imapping imapping

imapping-map-either! and imapping-map-either/key! are the same as imapping-map-either and imapping-map-either/key, respectively, except that they may mutate the imap parameter to produce their results.

(imapping-relation-map proc imap) → imapping

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

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

Rationale: imapping-relation-map corresponds to mapping-map from SRFI 146 and is specified primarily for compatibility with that SRFI. It generalizes imapping-map and imapping-map/key, and can be used to produce a wide range of transformations on imappings. This generality comes at a price, however. Certain familiar laws that hold of imapping-map and other Scheme "map" functions do not hold of imapping-relation-map; in particular, the size of the input imapping imap may not be preserved, and a key with an association in imap may not have an association in the transformed imapping.

As such, imapping-map and imapping-map/key likely conform better to the familiar pattern of Scheme "map" functions, while being sufficiently general for most purposes.

Filter

(imapping-filter pred imap) → imapping
(imapping-filter/key pred imap) → imapping

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

imapping-filter/key is the same, except that pred is applied to the key and value of each association.

Example:

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

(imapping-filter! pred imap) → imapping
(imapping-filter/key! pred imap) → imapping

imapping-filter! and imapping-filter/key! are the same as imapping-filter and imapping-filter/key, respectively, except that they may mutate and return the imap parameter instead of allocating a new imapping.

(imapping-remove pred imap) → imapping
(imapping-remove/key pred imap) → imapping

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

imapping-remove/key is the same, except that pred is applied to the key and value of each association.

Example:

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

(imapping-remove! pred imap) → imapping
(imapping-remove/key! pred imap) → imapping

imapping-remove! and imapping-remove/key! are the same as imapping-remove and imapping-remove/key, respectively, except that they may mutate and return the imap parameter instead of allocating a new imapping.

(imapping-partition pred imap) → [imapping, imapping]
(imapping-partition/key pred imap) → [imapping, imapping]

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

imapping-partition/key is the same, except that pred is applied to the key and value of each association.

Example:

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

(imapping-partition! pred imap) → imapping
(imapping-partition/key! pred imap) → imapping

imapping-partition! and imapping-partition/key! are the same as imapping-partition and imapping-partition/key, respectively, except that they may mutate the imap parameter to produce their results.

Conversion

(imapping-copy imap) → imapping

Returns a newly allocated imapping containing the associations of imap.

(imapping->alist imap) → alist[exact-integer, *]

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

Example:

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

(imapping->decreasing-alist imap) → alist[exact-integer, *]

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

Example:

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

(imapping-keys imap) → list[exact-integer]

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

Example:

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

(imapping-keys-set imap) → iset

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

Example:

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

(imapping-values imap) → list[*]

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

Example:

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

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

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

Example:

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

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

This is the same as imapping->generator, except that the associations of imapping are produced in decreasing order of key.

Example:

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

Comparison

(imapping=? comp imapimapimap…) → boolean

Returns #t if and only if all of the imaps contain equal associations. Two associations are equal exactly when their keys are equal (in the sense of =) and if their values are equal in the sense of the equality predicate of comp (see SRFI 128).

Examples:

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

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

(imapping<? comp imapimapimap…) → boolean
(imapping<=? comp imapimapimap…) → boolean
(imapping>? comp imapimapimap…) → boolean
(imapping>=? comp imapimapimap…) → boolean

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

Examples:

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

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

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

Set theory operations

(imapping-union imapimapimap₃ …) → imapping
(imapping-intersection imapimapimap₃ …) → imapping
(imapping-difference imapimapimap₃ …) → imapping
(imapping-xor imapimap) → imapping

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

Examples:

(imapping->alist (imapping-union (imapping 0 'a 2 'c)
                                 (imapping 1 'b 3 'd)))
 ⇒ ((0 . a) (1 . b) (2 . c) (3 . d))

(imapping->alist
 (imapping-intersection (imapping 0 'a 2 'c)
                        (imapping 1 'b 2 'c 3 'd)
                        (imapping 2 'c 4 'e)))
 ⇒ ((2 . c))

(imapping->alist (imapping-difference (imapping 0 'a 1 'b 2 'c)
                                      (imapping 2 "worf")
                                      (imapping 1 "data")))
 ⇒ ((0 . a))

(imapping-union! imapimapimap₃ …) → imapping
(imapping-intersection! imapimapimap₃ …) → imapping
(imapping-difference! imapimapimap₃ …) → imapping
(imapping-xor! imapimap) → imapping

These are linear-update variants of imapping-union, etc.. They may mutate any of the imap parameters to produce their results.

(imapping-union/combinator proc imapimapimap₃ …) → imapping
(imapping-intersection/combinator proc imapimapimap₃ …) → imapping

proc is a procedure of type * * → *.

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

Examples:

;; Right-biased union.
(imapping->alist
 (imapping-union/combinator (lambda (_l r) r)
                            (imapping 1 'b 2 'c)
                            (imapping 2 "data" 3 "picard")))

 ⇒ ((1 . b) (2 . "data") (3 . "picard"))

(imapping->alist
 (imapping-intersection/combinator
  (lambda (l r) (string-append l " " r))
  (imapping 1 "q" 3 "jean-luc" 5 "miles" 7 "quark")
  (imapping 3 "picard" 5 "o'brien")))

 ⇒ ((3 . "jean-luc picard") (5 . "miles o'brien"))

(imapping-union/combinator! proc imapimapimap₃ …) → imapping
(imapping-intersection/combinator! proc imapimapimap₃ …) → imapping

These are linear-update variants of imapping-union/combinator and imapping-intersection/combinator. They may mutate any of the imap parameters to produce their results.

Submappings

(imapping-open-interval imap low high) → imapping
(imapping-closed-interval imap low high) → imapping
(imapping-open-closed-interval imap low high) → imapping
(imapping-closed-open-interval imap low high) → imapping

low and high are both exact integers.

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

Examples:

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

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

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

(imapping-open-interval! imap low high) → imapping
(imapping-closed-interval! imap low high) → imapping
(imapping-open-closed-interval! imap low high) → imapping
(imapping-closed-open-interval! imap low high) → imapping

These are linear-update variants of imapping-open-interval, etc.. They may mutate and return the imap parameter instead of allocating a new imapping.

(isubmapping= imap k) → imapping
(isubmapping< imap k) → imapping
(isubmapping<= imap k) → imapping
(isubmapping> imap k) → imapping
(isubmapping>= imap k) → imapping

Procedures that return an imapping containing the associations of imap whose keys are equal to/less than/less than or equal to/greater than/greater than or equal to k. Note that the result of isubmapping= contains at most one element.

Examples:

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

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

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

(isubmapping=! imap k) → imapping
(isubmapping<! imap k) → imapping
(isubmapping<=! imap k) → imapping
(isubmapping>! imap k) → imapping
(isubmapping>=! imap k) → imapping

These are linear-update variants of isubmapping=, etc.. They may mutate and return the imap parameter instead of allocating a new imapping.

(imapping-split imap k) → [imapping, imapping]

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

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

If imap is empty, then both of the imappings returned by imapping-split are empty.

Example:

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

 ⇒ (((0 . a) (1 . b) (2 . c))
    ((3 . d)))

Implementation

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

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

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.


Editor: Arthur A. Gleckler