224: Integer Mappings224: Integer Mappingsby Wolfgang Corcoran-Mathe
This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-224@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
fxmapping-alter.)Integer maps, or fxmappings, are finite sets, where each element is an association between a fixnum (exact integer) key and an arbitrary Scheme object. They are similar to the general mappings of SRFI 146, but the restricted key-type allows implementations of fxmappings to benefit from optimized structures and algorithms. This library provides a rich set of operations on fxmappings, including analogues of most of the forms provided by SRFI 146. Fxmappings have no intrinsic order, but may be treated as ordered sets, using the natural ordering on keys; a substantial sublibrary for working with fxmappings in this fashion is included.
“Finite maps are the workhorse data structure in every compiler.” —Okasaki & Gill
Mappings provide operations that are critical to a host of functional algorithms. They describe finite sets of key-value associations (pairs) which can be extended, queried, and transformed. Critically, all of these operations can be efficiently implemented as “pure” functions. While hash-tables (see SRFI 125) provide similar operations, they generally provide a strictly imperative language for insertion and mutation of association sets.
Mappings are already familiar to Scheme programmers; SRFI 146 provides general mappings and was added to the Tangerine Edition of R7RS-large. But the generality of SRFI 146 is costly. Any comparable type of Scheme object can be used as a key in a SRFI 146 mapping, so comparisons between keys must use the generic methods of SRFI 128. This is overkill for many use cases; in particular, if we wish to use exact integers as keys, we expect comparisons to be very fast and to require no mediation from a comparison dictionary. In addition, some efficient and simple mapping representations, for example the Okasaki-Gill radix tree model used in this SRFI’s sample implementation, are unsuitable for representing general mappings.
The integer mappings we describe restrict the type of keys to fixnums, a subrange of the exact integers provided by most Schemes (See the R⁶RS § 3.3 and SRFI 143). The fixnum subset is broadly useful as a key-type for mappings; its use opens up a range of implementation options.
This library provides an interface similar to that used by
SRFI 146, although it diverges in some areas. In addition,
fxmapping-adjust, fxmapping-alter, and
several other forms derive from Haskell’s
IntMap
library.
The specification of this SRFI depends on the comparator type (used to determine the equality of values, not keys) described in SRFI 128. Conversions from fxmappings to SRFI 158 generators are provided. The sample implementation has further dependencies; see the appropriate section for more details.
Fxmappings (pronounced "fix-mappings") form a new type as if
created by define-record-type (see R7RS § 5.5). The
effects of using record-type inspection or inheritance for the
fxmapping type are unspecified.
In systems supporting R6RS record-type semantics, fxmappings are
instances of a nongenerative record type with uid
fxmapping-7a1f4d5b-a540-462b-82b1-47283c935b85.
Fxmappings represent finite sets of associations whose keys are fixnums, an implementation-defined subset of the exact integers. This is a closed interval,
[-(2 ^ (w - 1)), (2 ^ (w - 1)) - 1],
where w is an integer greater than or equal to 24. Portable code should not assume that w is greater than 24.
Fxmappings are immutable in the sense that all of the procedures defined in this SRFI are “pure”, that is, they must not mutate their arguments. If an implementation allows fxmappings to be mutated, the effects of combining mutation and the procedures of this library are unspecified.
The procedures in this SRFI must fully support non-local control
flow, e.g. as created by exception handling or invocation of
continuations. In particular, if multiple returns occur from
a higher-order procedure, such as fxmapping-unfold, then
the values returned by earlier returns must not be mutated.
The words “must”, “may”, etc., though not capitalized in this SRFI, are to be interpreted as described in RFC 2119.
The naming conventions of this document are consistent with those used in the R7RS Scheme standard.
The following names are used for the parameters of procedures:
| obj | any Scheme object |
| boolean | a boolean |
| fxmap | a fxmapping with values of arbitrary type |
| k | a fixnum satisfying SRFI 143's fixnum? |
| list | a proper list |
| alist | an association list |
| proc | a procedure |
| pred | a predicate that is assumed to have no side effects |
| comp | a SRFI 128 comparator object |
Unless otherwise noted, it is an error if the procedures are passed arguments that do not have the type implied by the argument names.
The pair notation (k,v) is often used to describe
an association of a fxmapping. Here, k is the key and
v its associated value. If a fxmapping fxmap is said
to "contain the association (k,v)", then this is to
be understood in the sense that looking up k in fxmap
(via (fxmapping-ref fxmap k), for
example) will produce the value v.
Each procedure is written in the form
(proc arg₁ arg₂ …) → [type₁, type₂, …]
where proc is the name of the procedure, the args are its
parameters, and the types are the types of the objects it returns.
If the procedure returns a single value, the brackets on the right-hand side
may be omitted. A pair of empty brackets, [], denotes zero values;
thus a "thunk" (nullary procedure) returning zero or more values is of type
[] → [*, …].
The types refer (informally) to Scheme types; e.g. boolean
denotes a Scheme boolean, list[integer] denotes a list of integers,
etc. The special notation ‘*’ indicates that the type
of the value may be anything, depending on the context of the procedure call.
For example, Scheme’s list-ref procedure would be written
(list-ref list k) → *
since the type of the return value depends on list. Multiple
* values appearing in the same type signature do not necessarily
denote the same type. For example, the signature * * → boolean might
denote the type of a procedure taking two values of the same type to a boolean,
or two values of differing types. The accompanying description may clarify
the semantics of procedures defined on * values, but Scheme's
type system makes it difficult to explain all of the possible interactions of
these procedures.
A procedure which returns a value of type τ-or-false
(where τ denotes a type) returns a τ on success, and
#f otherwise. Thus the memv procedure of R7RS
would have the type signature * list[*] → list[*]-or-false.
Constructors: fxmapping, fxmapping-unfold,
fxmapping-accumulate, alist->fxmapping,
alist->fxmapping/combinator
Predicates: fxmapping?, fxmapping-contains?, fxmapping-empty?, fxmapping-disjoint?
Accessors: fxmapping-ref, fxmapping-ref/default,
fxmapping-min, fxmapping-max
Updaters: fxmapping-adjoin, fxmapping-adjoin/combinator,
fxmapping-set, fxmapping-adjust, fxmapping-delete,
fxmapping-delete-all, fxmapping-alter,
fxmapping-update, fxmapping-delete-min,
fxmapping-delete-max,
fxmapping-update-min, fxmapping-update-max,
fxmapping-pop-min, fxmapping-pop-max
The whole fxmapping: fxmapping-size,
fxmapping-find,
fxmapping-count, fxmapping-any?, fxmapping-every?
Traversal: fxmapping-fold,
fxmapping-fold-right, fxmapping-map, fxmapping-map->list,
fxmapping-map->list, fxmapping-for-each,
fxmapping-relation-map
Filter: fxmapping-filter,
fxmapping-remove, fxmapping-partition
Conversion: fxmapping->alist,
fxmapping->decreasing-alist, fxmapping-keys, fxmapping-values,
fxmapping->generator, fxmapping->decreasing-generator
Comparison: fxmapping=?, fxmapping<?, fxmapping>?, fxmapping<=?, fxmapping>=?
Set theory operations: fxmapping-union, fxmapping-intersection, fxmapping-difference,
fxmapping-xor,
fxmapping-union/combinator,
fxmapping-intersection/combinator
Submappings: fxmapping-open-interval, fxmapping-closed-interval,
fxmapping-open-closed-interval, fxmapping-closed-open-interval,
fxsubmapping=, fxsubmapping<, fxsubmapping<=, fxsubmapping>=,
fxsubmapping>,
fxmapping-split
(fxmapping k₁ obj₁ k₂ …) → fxmapping
Constructs a fxmapping from the given arguments, which alternate between keys and values (which are arbitrary Scheme objects); the resulting fxmapping is newly allocated and contains these (k, obj) associations. The number of arguments must be even. If duplicate keys occur in the arguments, earlier associations take priority.
Examples:
(fxmapping->alist (fxmapping 0 'a 1 'b 2 'c))
⇒ ((0 . a) (1 . b) (2 . c))
(fxmapping->alist (fxmapping -10 "worf" -10 "yar"))
⇒ ((-10 . "worf"))
(fxmapping-unfold stop? mapper successor seed₁ seed₂ …) → fxmapping
* * … → *-or-false* * … → [fixnum, *]* * … → * * …*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
(* … → [fxmapping, *, …]) * * … → [fixnum, *, *, *, …]*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"))
(fxmapping? obj) → boolean
Returns #t if and only if obj is a fxmapping.
(fxmapping-contains? fxmap k) → boolean
Returns #t if and only if fxmap contains an association for key k.
Examples:
(fxmapping-contains? (fxmapping 1 'b) 1) ⇒ #t
(fxmapping-contains? (fxmapping 1 'b) 0) ⇒ #f
(fxmapping-empty? fxmap) → boolean
Returns #t if and only if fxmap contains no associations.
Examples:
(fxmapping-empty? (alist->fxmapping '())) ⇒ #t
(fxmapping-empty? (alist->fxmapping '((0 . a)))) ⇒ #f
(fxmapping-disjoint? fxmap₁ fxmap₂) → boolean
Returns #t if and only if fxmap₁ and fxmap₂ have no keys in common.
Examples:
(fxmapping-disjoint? (fxmapping 0 'a) (fxmapping 1 'b)) ⇒ #t
(fxmapping-disjoint? (fxmapping 1 '(b)) (fxmapping 1 'b)) ⇒ #f
(fxmapping-ref fxmap k [ failure [ success ] ]) → * …
The optional failure parameter is a procedure of type
[] → [*, …]. The optional success parameter
is a procedure of type * → [*, …]. The success procedure
defaults to values.
If an association (k, v)
occurs in fxmap, then success is invoked in tail
context on v, and its values are returned. If k does
not have an association in fxmap and failure is
supplied, then it is invoked in tail context on no arguments, and
its values are returned. Otherwise, it is an error.
Examples:
(fxmapping-ref (fxmapping 36864 'zap) 36864) ⇒ zap
(fxmapping-ref (fxmapping 0 'a) 36864) ⇒ ; error
(fxmapping-ref (fxmapping 0 "worf")
0
(lambda () #f)
string-length)
⇒ 4
(fxmapping-ref/default fxmap k obj) → *
If an association (k, v) occurs in fxmap, returns v.
Otherwise, returns obj.
Examples:
(fxmapping-ref/default (fxmapping 36864 'zap) 36864 #f) ⇒ zap
(fxmapping-ref/default (fxmapping 0 'a) 36864 #f) ⇒ #f
(fxmapping-min fxmap) → [fixnum, *]
Returns two values: the least key of fxmap and its associated value. It is an error if fxmap is empty.
Example:
(fxmapping-min (fxmapping 0 'a 1 'b 2 'c)) ⇒ 0 a
(fxmapping-max fxmap) → [fixnum, *]
Returns two values: the greatest key of fxmap and its associated value. It is an error if fxmap is empty.
Example:
(fxmapping-max (fxmapping 0 'a 1 'b 2 'c)) ⇒ 2 c
(fxmapping-adjoin fxmap k₁ obj₁ k₂ …) → fxmapping
Returns a fxmapping containing all of the associations of fxmap as well as the associations (k₁, obj₁), (k₂, obj₂), …. The number of key/value arguments must be even.
If any of the keys already have associations in fxmap, the old associations are preserved.
Examples:
(fxmapping->alist (fxmapping-adjoin (fxmapping 1 'b) 0 'a))
⇒ ((0 . a) (1 . b))
(fxmapping-adjoin/combinator fxmap proc k₁ obj₁ k₂ …) → fxmapping
Similar to fxmapping-adjoin, except that duplicate associations
are combined with proc, which is a procedure of type fixnum * * → *.
The proc procedure is called on the new and old values (in that order) associated
with a duplicated key, and is expected to return a value to be
associated with that key in the resulting fxmapping. For example, if
fxmap contains the association (k, v₁), then
the value of
(fxmapping-adjoin/combinator fxmap f k v₂)
will be a fxmapping with the association
(k, (f k v₂ v₁)).
Example:
(fxmapping->alist
(fxmapping-adjoin/combinator
(fxmapping 0 "geordi" 1 "reginald")
(lambda (_ last first)
(string-append first " " last))
0 "laforge"
1 "barclay"))
⇒ ((0 . "geordi laforge") (1 . "reginald barclay"))
(fxmapping-set fxmap k₁ obj₁ k₂ …) → fxmapping
fxmapping-set is the same as fxmapping-adjoin,
except that any existing associations for k₁, k₂, … are
replaced.
Example:
(fxmapping->alist
(fxmapping-set (fxmapping 0 "geordi" 1 "reginald")
1
"tasha"))
⇒ ((0 . "geordi") (1 . "tasha"))
(fxmapping-adjust fxmap k proc) → fxmapping
The proc parameter of fxmapping-adjust is a
procedure of type fixnum * → *.
Returns a fxmapping in which the association (k, v) in fxmap is replaced by (k, (proc k v)). If k has no association in fxmap, then a fxmapping with the same associations as fxmap is returned.
Examples:
(fxmapping->alist
(fxmapping-adjust (fxmapping 64 "var")
64
(lambda (k s)
(string-append s (number->string k)))))
⇒ ((64 . "var64"))
(fxmapping-delete fxmap k₁ k₂ …) → fxmapping
Returns a fxmapping with the same associations as fxmap, except those with keys equal to one of k₁, k₂, ….
Example:
(fxmapping->alist
(fxmapping-delete (fxmapping 0 -200 1 -100) 0))
⇒ ((1 . -100))
(fxmapping-delete-all fxmap list) → fxmapping
Returns a fxmapping with the same associations as fxmap, except those for keys equal to an element of list.
Example:
(fxmapping->alist
(fxmapping-delete-all (fxmapping 0 'a 1 'b 2 'c) '(1 2)))
⇒ ((0 . a))
(fxmapping-update fxmap k proc [ failure ]) → * …
The procedure proc is of type
fixnum * (* → fxmapping) ([] → fxmapping) → * ….
If the optional failure parameter is provided, then it must
be a procedure of type [] → [*, …].
Updates the association for k in fxmap as follows. If k has an association in fxmap, then proc is invoked in tail context on k, its associated value, and two procedure arguments, replace and delete, and its values are returned. Invoking replace on a value v returns a fxmapping with the association (k, v) and all of fxmap's other associations. Invoking delete returns a fxmapping with all of the associations of fxmap, but without an association for k. If k has no association in fxmap and failure is provided, then failure is invoked in tail context on no arguments and its values are returned. Otherwise, it is an error.
Note that, in contrast to similar Scheme forms, proc is
not required to tail-call one of delete or replace,
and that fxmapping-update simply returns the results of
invoking proc (assuming k is found).
Thus, the following is valid:
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (k v replace _del)
(values k
v
(fxmapping->alist (replace 'z)))))
⇒ 1
b
((0 . a) (1 . z) (2 . c))
Simple versions of several other update operations may be defined
in terms of fxmapping-update, e.g.:
(fxmapping-delete fxmap k)
≡
(fxmapping-update fxmap k (lambda (_k _v _r delete) (delete)))
(fxmapping-set fxmap k v)
≡
(fxmapping-update fxmap
k
(lambda (_k _u replace _d) (replace v)))
Examples:
;; Delete the association for 1 if its value is a symbol.
(fxmapping->alist
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (_k v replace delete)
(if (symbol? v)
(delete)
(replace v)))))
⇒ ((0 . a) (2 . c))
(fxmapping->alist
(fxmapping-update (fxmapping 0 'a 1 'b 2 'c)
1
(lambda (k _v replace _d)
(replace k)))))
⇒ ((0 . a) (1 . 1) (2 . c))
(fxmapping-alter fxmap k failure success) → * …
The procedure failure is of type
(* → fxmapping) ([] → fxmapping) → [*, …].
The procedure success is of type
fixnum * (* → fxmapping) ([] → fxmapping) → [*, …].
Updates the association, or lack thereof, for k in fxmap as follows. If the association (k, v) exists in fxmap, then success is invoked in tail context on k, v, and two procedure arguments, replace and delete, and its values are returned.
Invoking (replace v′) returns
a fxmapping with the association (k, v′)
as well as all of fxmap’s other associations, 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)))
(fxmapping-size fxmap) → fixnum
Returns the number of associations in fxmap.
(fxmapping-find pred fxmap failure [ success ]) → [*, …]
Procedure pred is a predicate of type fixnum * → boolean.
Procedure failure is of type [] → [*, …].
If the optional success parameter is supplied, then it must be
a procedure of type fixnum * → [*, …]. Procedure success
defaults to values.
Invokes success in tail context on k and
v and returns it results, where (k, v)
is the association of fxmap with the least key such that
(pred k v) is true.
If there is no
such association, then failure is tail-called with no
arguments and its results are returned.
Examples:
(fxmapping-find (lambda (_ v) (even? v))
(fxmapping 0 1 1 2 2 4 3 8)
(lambda () (values #f #f)))
⇒ 1 2
(fxmapping-find (lambda (_ v) (negative? v))
(fxmapping 0 1 1 2 2 4 3 8)
(lambda () (values 'nope 'nada)))
⇒ nope nada
(fxmapping-find (lambda (k s) (= k (string-length s)))
(fxmapping 2 "worf" 3 "data" 4 "troi")
(lambda () (error "not found"))
list)
⇒ (4 "troi")
(fxmapping-count pred fxmap) → fixnum
Procedure pred is a predicate of type
fixnum * → boolean.
Returns the number of associations in fxmap that satisfy
pred (in the sense of fxmapping-find).
Examples:
(fxmapping-count (lambda (_ v) (even? v))
(fxmapping 0 1 1 2 2 4 3 8)) ⇒ 3
(fxmapping-count (lambda (k s) (= k (string-length s)))
(fxmapping 0 "x" 1 "y" 2 "z"))
⇒ 1
(fxmapping-any? pred fxmap) → boolean
Procedure pred is a predicate of type
fixnum * → boolean.
Returns #t if and only if there exists an association
in fxmap that satisfies pred (in the sense of
fxmapping-find). The fxmap is traversed in ascending
numerical order of keys.
Example:
(fxmapping-any? (lambda (_ v) (odd? v))
(fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t
(fxmapping-every? pred fxmap) → boolean
Procedure pred is a predicate of type
fixnum * → boolean.
Returns #t if and only every association in
fxmap satisfies pred (in the sense of
fxmapping-find), or if fxmap is empty.
The fxmap is traversed in ascending numerical order of keys.
Example:
(fxmapping-every? (lambda (_ v) (integer? v))
(fxmapping 0 1 1 2 2 4 3 8)) ⇒ #t
(fxmapping-map proc fxmap) → fxmapping
The proc argument of fxmapping-map is of type
fixnum * → *.
Returns a fxmapping with the same keys as fxmap whose values
are the result of transforming the values of fxmap with proc.
For each association
(k, v) in fxmap, the association
(k, (proc k v))
is added to the resulting fxmapping.
The dynamic order
of the applications of proc to the elements of fxmap is
unspecified.
Examples:
(fxmapping->alist
(fxmapping-map (lambda (_ s) (string-length s))
(fxmapping 0 "picard" 1 "riker" 2 "troi")))
⇒ ((0 . 6) (1 . 5) (2 . 4))
(fxmapping->alist
(fxmapping-map (lambda (k s)
(string-append s (number->string k)))
(fxmapping 256 "x" 512 "y" 1024 "z")))
⇒ ((256 . "x256") (512 . "y512") (1024 . "z1024"))
Note that, in contrast to SRFI 146’s mapping-map
procedure, this procedure transforms the values of fxmap only;
that is, the set of keys of the resulting fxmapping is the same as that
of fxmap.
(fxmapping-for-each proc fxmap) → unspecified
Procedure proc is of type fixnum * → *.
Calls proc on the key and value of each association in fxmap and returns an unspecified value. The fxmap is traversed in ascending numerical order of keys.
Example:
(let ((sum 0))
(fxmapping-for-each (lambda (_ v) (set! sum (+ sum v)))
(fxmapping 0 1 1 2 2 4 3 8))
sum)
⇒ 15
(fxmapping-fold kons knil fxmap) → *
(fxmapping-fold-right kons knil fxmap) → *
The kons argument of fxmapping-fold and fxmapping-fold-right is a
procedure of type fixnum * * → *.
The knil argument is an object of any type which can be passed to kons
as its third argument.
Folds kons over fxmap, using knil as the base value. At
each step, kons is applied to the key of an association, its
associated value, and to the result of the last application.
fxmapping-fold folds in ascending numerical order of keys;
fxmapping-fold-right folds in descending order.
Examples:
(fxmapping-fold-right
(lambda (_ v vs) (cons v vs))
'()
(fxmapping 0 "worf" 1 "data" 2 "crusher"))
⇒ ("worf" "data" "crusher")
(fxmapping-fold (lambda (k _ ks) (cons k ks))
'()
(fxmapping 0 "worf" 1 "data" 2 "crusher"))
⇒ (2 1 0)
(fxmapping-map->list proc fxmap) → list
Equivalent to
(fxmapping-values (fxmapping-map proc fxmap)),
but may be implemented more efficiently.
Example:
(fxmapping-map->list
(lambda (_ v) (string-length v))
(fxmapping 0 "picard" 1 "riker" 2 "troi"))
⇒ (6 5 4)
(fxmapping-relation-map proc fxmap) → fxmapping
Procedure proc must be of type
fixnum * → [fixnum, *].
Returns a fxmapping whose associations are the results of transforming both the keys and the values of fxmap with proc. For each association (k, v) in fxmap, (proc k v) is evaluated to return a new key and a new value which are associated in the new fxmapping. Duplicate keys are replaced, but the results in this case are unpredictable; if proc is not injective, that is, if it produces multiple associations with the same key, then it is unspecified which one of these associations will be present in the resulting fxmapping. The dynamic order of the applications of proc to the elements of fxmap is unspecified.
Rationale: fxmapping-relation-map
corresponds to mapping-map from SRFI 146 and is specified
primarily for compatibility with that SRFI. It generalizes
fxmapping-map, and can
be used to produce a wide range of transformations on fxmappings. This
generality comes at a price, however. Certain familiar laws that hold
of fxmapping-map and other Scheme "map" functions do not
hold of fxmapping-relation-map; in particular, the size of
the fxmap may not be preserved, and a key with an
association in fxmap may not have an association in the
resulting fxmapping.
As such, fxmapping-map
likely conforms better to the familiar pattern of Scheme "map" functions,
while being sufficiently general for most purposes.
(fxmapping-filter pred fxmap) → fxmapping
Returns a fxmapping containing all of the associations of fxmap
that satisfy pred (in the sense of fxmapping-find).
Example:
(fxmapping->alist
(fxmapping-filter (lambda (_ v) (positive? v))
(fxmapping 0 2 1 -4 2 8 3 -16)))
⇒ ((0 . 2) (2 . 8))
(fxmapping-remove pred fxmap) → fxmapping
Returns a fxmapping containing all of the associations of
fxmap that do not satisfy pred (in the sense of
fxmapping-find).
Example:
(fxmapping->alist
(fxmapping-remove (lambda (_ v) (positive? v))
(fxmapping 0 2 1 -4 2 8 3 -16)))
⇒ ((1 . -4) (3 . -16))
(fxmapping-partition pred fxmap) → [fxmapping, fxmapping]
Returns two fxmappings. The first contains all associations of
fxmap that satisfy pred (in the sense of
fxmapping-find), and the second contains those
that do not.
Example:
(let-values (((pos ~pos)
(fxmapping-partition
(lambda (_ v) (positive? v))
(fxmapping 0 2 1 -4 2 8 3 -16))))
(values (fxmapping->alist pos)
(fxmapping->alist ~pos)))
⇒ ((0 . 2) (2 . 8))
((1 . -4) (3 . -16))
(fxmapping->alist fxmap) → alist[fixnum, *]
Returns an alist containing the associations of
fxmap in increasing numerical order of key.
That is, if (k₁, v₁), …, (kₙ,
vₙ) are the associations of fxmap ordered so that
k₁ ≤ … ≤ kₙ, then
(fxmapping->alist fxmap)
produces the list ((k₁ .
v₁) … (kₙ
. vₙ)).
Example:
(fxmapping->alist (fxmapping 1 'a 2 'b)) ⇒ ((1 . a) (2 . b))
(fxmapping->decreasing-alist fxmap) → alist[fixnum, *]
Identical to fxmapping->alist, except that the
resulting alist contains the associations of fxmap in
decreasing numerical order of key.
Example:
(fxmapping->decreasing-alist (fxmapping 1 'a 2 'b))
⇒ ((2 . b) (1 . a))
(fxmapping-keys fxmap) → list[fixnum]
Returns the keys of fxmap as a list in ascending numerical order.
Example:
(fxmapping-keys (fxmapping 137 'a -24 'b -5072 'c))
⇒ (-5072 -24 137)
(fxmapping-values fxmap) → list[*]
Returns the values of fxmap as a list in ascending numerical
order of key.
That is, if (k₁, v₁), …, (kₙ,
vₙ) are the associations of fxmap ordered so that
k₁ ≤ … ≤ kₙ, then
(fxmapping-values fxmap)
produces the list
(v₁ … vₙ).
Example:
(fxmapping-values (fxmapping 0 "picard" 1 "riker" 2 "troi"))
⇒ ("picard" "riker" "troi")
(fxmapping->generator fxmapping) → generator[pair(fixnum, *)]
Returns a SRFI 158 generator which
produces the associations of fxmapping as key/value pairs in increasing
order of key. That is, if (k₁, v₁), …, (kₙ,
vₙ) are the associations of fxmap ordered so that
k₁ ≤ … ≤ kₙ, then the generator returned by
(fxmapping->generator fxmap)
produces the pairs (k₁ .
v₁), …, (kₙ
. vₙ), in that order.
Example:
(generator->list
(fxmapping->generator (fxmapping 3 "yar" 2 "troi")))
⇒ ((2 . "troi") (3 . "yar"))
(fxmapping->decreasing-generator fxmapping) → generator[pair(fixnum, *)]
This is the same as fxmapping->generator, except that the associations
of fxmapping are produced in decreasing order of key.
Example:
(generator->list
(fxmapping->decreasing-generator
(fxmapping 3 "yar" 2 "troi")))
⇒ ((3 . "yar") (2 . "troi"))
Each of the following predicates takes a
SRFI 128 comparator
argument which is used to compare the values of the associations of
two fxmappings. (Keys are always compared as if with =.)
Note that none of these five predicates produces a total order on
fxmappings. In particular, fxmapping=?, fxmapping<?,
and fxmapping>? do not obey the
trichotomy law.
(fxmapping=? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean
Returns #t if and only if all of the fxmaps contain equal
associations. Two associations are equal exactly when their keys are
equal (in the sense of =) and their values are equal in the sense
of the equality predicate of comp.
Examples:
(fxmapping=? (make-default-comparator)
(fxmapping 1 'a 2 'b)
(fxmapping 2 'b 1 'a))
⇒ #t
(fxmapping=? (make-default-comparator)
(fxmapping 1 'a 2 'b 3 'c)
(fxmapping 2 'b 1 'a))
⇒ #f
(fxmapping<? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean
(fxmapping<=? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean
(fxmapping>? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean
(fxmapping>=? comp fxmap₁ fxmap₂ fxmap₃ …) → boolean
Returns #t if and only if each fxmap other than the last is a proper
subset/subset/proper superset/superset of the following fxmap. Values are
compared using the equality predicate of comp.
Examples:
(fxmapping<? (make-default-comparator)
(fxmapping 1 'a 2 'b)
(fxmapping 2 'b 1 'a 3 'c))
⇒ #t
(fxmapping>? (make-default-comparator)
(fxmapping 2 'b 1 "worf" 3 'c)
(fxmapping 1 'a 2 'b))
⇒ #f
(fxmapping>=? (make-default-comparator)
(fxmapping 2 'b 1 'a 3 'c)
(fxmapping 1 'a 2 'b)
(fxmapping 2 'b 1 'a)
(fxmapping 1 'a))
⇒ #t
(fxmapping-union fxmap₁ fxmap₂ fxmap₃ …) → fxmapping
(fxmapping-intersection fxmap₁ fxmap₂ fxmap₃ …) → fxmapping
(fxmapping-difference fxmap₁ fxmap₂ fxmap₃ …) → fxmapping
(fxmapping-xor fxmap₁ fxmap₂) → fxmapping
Return a fxmapping whose set of associations is the union, intersection, asymmetric difference, or symmetric difference of the sets of associations of the fxmaps. Asymmetric difference is extended to more than two fxmappings by taking the difference between the first fxmapping and the union of the others. Symmetric difference is not extended beyond two fxmappings. When comparing associations, only the keys are compared. In case of duplicate keys, associations in the result fxmapping are drawn from the first fxmapping in which they appear.
Examples:
(fxmapping->alist (fxmapping-union (fxmapping 0 'a 2 'c)
(fxmapping 1 'b 3 'd)))
⇒ ((0 . a) (1 . b) (2 . c) (3 . d))
(fxmapping->alist
(fxmapping-intersection (fxmapping 0 'a 2 'c)
(fxmapping 1 'b 2 'c 3 'd)
(fxmapping 2 'c 4 'e)))
⇒ ((2 . c))
(fxmapping->alist
(fxmapping-difference (fxmapping 0 'a 1 'b 2 'c)
(fxmapping 2 "worf")
(fxmapping 1 "data")))
⇒ ((0 . a))
(fxmapping-union/combinator proc fxmap₁ fxmap₂ fxmap₃ …) → fxmapping
(fxmapping-intersection/combinator proc fxmap₁ fxmap₂ fxmap₃ …) → fxmapping
Procedure proc is of type fixnum * * → *.
Return a fxmapping whose set of keys is the union/intersection of the sets of keys of the fxmaps. The values associated with duplicate keys are combined left-associatively with proc, which is also passed the duplicated key as its first argument; that is, if an integer k is associated with values v₁, v₂, …, vₙ in fxmap₁, fxmap₂, …, fxmapₙ, respectively, then the resulting fxmapping will contain the association (k, (proc k … (proc k v₁ v₂) … vₙ)).
Examples:
;; Right-biased union.
(fxmapping->alist
(fxmapping-union/combinator (lambda (_k _l r) r)
(fxmapping 1 'b 2 'c)
(fxmapping 2 "data" 3 "picard")))
⇒ ((1 . b) (2 . "data") (3 . "picard"))
(fxmapping->alist
(fxmapping-intersection/combinator
(lambda (_ l r) (string-append l " " r))
(fxmapping 1 "q" 3 "jean-luc" 5 "miles" 7 "quark")
(fxmapping 3 "picard" 5 "o'brien")))
⇒ ((3 . "jean-luc picard") (5 . "miles o'brien"))
(fxmapping-open-interval fxmap low high) → fxmapping
(fxmapping-closed-interval fxmap low high) → fxmapping
(fxmapping-open-closed-interval fxmap low high) → fxmapping
(fxmapping-closed-open-interval fxmap low high) → fxmapping
Arguments low and high are both fixnums.
Procedures that return a subset of fxmap containing the associations whose keys are contained in the interval from low to high. The interval is open/closed/open below and closed above/open above and closed below.
Examples:
(fxmapping->alist
(fxmapping-open-interval
(fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3))
⇒ ((2 . c))
(fxmapping->alist
(fxmapping-closed-interval
(fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3))
⇒ ((1 . b) (2 . c) (3 . d))
(fxmapping->alist
(fxmapping-closed-open-interval
(fxmapping 0 'a 1 'b 2 'c 3 'd) 1 3))
⇒ ((1 . b) (2 . c))
(fxsubmapping= fxmap k) → fxmapping
(fxsubmapping< fxmap k) → fxmapping
(fxsubmapping<= fxmap k) → fxmapping
(fxsubmapping> fxmap k) → fxmapping
(fxsubmapping>= fxmap k) → fxmapping
Procedures that return a fxmapping containing the associations of
fxmap whose keys are equal to/less than/less than or equal
to/greater than/greater than or equal to k. Note that the result of
fxsubmapping= contains at most one element.
Examples:
(fxmapping->alist
(fxsubmapping= (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))
⇒ ((2 . c))
(fxmapping->alist
(fxsubmapping< (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))
⇒ ((0 . a) (1 . b))
(fxmapping->alist
(fxsubmapping>= (fxmapping 0 'a 1 'b 2 'c 3 'd) 2))
⇒ ((2 . c) (3 . d))
(fxmapping-split fxmap k) → [fxmapping, fxmapping]
Returns two fxmappings. The first contains all of the associations
of fxmap whose keys are less than or equal to k, and the second
contains the remaining associations. This is equivalent to
(values (fxsubmapping<= fxmap k)
(fxsubmapping> fxmap k)), but may be
implemented more efficiently.
If fxmap is empty, then both of the fxmappings returned by
fxmapping-split are empty.
Example:
(let-values ((fxmaps
(fxmapping-split
(fxmapping 0 'a 1 'b 2 'c 3 'd) 2)))
(map fxmapping->alist fxmaps))
⇒ (((0 . a) (1 . b) (2 . c))
((3 . d)))
The sample implementation is found in the repository for this SRFI. The fxmapping implementation is based on big-endian radix (Patricia) trees as described by Chris Okasaki and Andrew Gill in “Fast Mergeable Integer Maps” (see References). These trees provide fast insert, lookup, and set-theoretical operations.
The implementation should be portable without changes to any R7RS Scheme that provides SRFIs 1, 128, and 143. The provided tests can be run with SRFIs 64 or 78; additional shims for the test libraries preferred by chibi-scheme and CHICKEN are also included.
Thanks to Marc-Nieper Wißkirchen and Arthur A. Gleckler, the authors of SRFI 146, as well as to Daan Leijen and Andriy Palamarchuk, who created the Haskell IntMap library. These libraries provided critical inspiration and implementation clues in the creation of this SRFI.
Thanks to the SRFI editor and to the contributors to the SRFI
mailing list, as well as to those who provided feedback on this SRFI
via the #scheme IRC channel.
This SRFI contains ideas and language drawn from dozens of other SRFIs, in particular specifications by Olin Shivers, John Cowan, and Taylor Campbell. The R7RS and earlier standards also provided constant design and literary guidance. Thus, little of what appears in this SRFI is “original”. Thanks to all of the Schemers who have contributed their knowledge and time to the SRFI process and to the RnRS standards.
Of course, none of this should be understood to imply that any of the individuals mentioned above endorse this SRFI.
Alex Shinn, John Cowan, & Arthur A. Gleckler, eds., Revised⁷ Report on the Algorithmic Language Scheme (R7RS) (2013). Available on the Web.
Michael Sperber, R. Kent Dybvig, Matthew Flatt, & Anton van Straaten, eds., The Revised⁶ Report on the Algorithmic Language Scheme (R6RS). Cambridge University Press, 2010. Available on the Web.
Chris Okasaki & Andrew Gill, “Fast Mergeable Integer Maps”, 1998 Workshop on ML, p. 77-86.
S. Bradner, “Key words for use in RFCs to Indicate Requirement Levels”. 1997. http://www.ietf.org/rfc/rfc2119.txt
© 2021 Wolfgang Corcoran-Mathe. All rights reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.