For Gauche 0.9.6


Next: , Previous: , Up: Library modules - SRFIs   [Contents][Index]

11.31 srfi-146 - Mappings and hashmaps

SRFI-146 defines a mapping data structure, which is a conceptually immutable collection of associations of key and value. Mappings are assumed to be built on top of treemaps (and indeed, Gauche uses built-in <tree-map> as mappings) but the API abstracts the implementation.

SRFI-146 also defines a submodlue (srfi-146 hash) which provides hashmaps, whose API is functionally almost identical to mappings but it assumes to be built on top of hashtables.

“Conceptually immutable” means that the mappings should be used as if they are immutable, but under a certain circumstance the APIs are allowed to mutate the mapping. Such circumstance is marked as


Next: , Previous: , Up: Mappings and hashmaps   [Contents][Index]

11.31.1 Mappings

Module: srfi-146

This module provides treemap-based mappings API. On Gauche, an instance of mapping is just an instance of built-in <tree-map> (see Treemaps). However, the API assumes a mapping to be treated as immutable data structure, except the “linear update” APIs, which is allowed to mutate the mappings passed to the arguments, under assumption that the argument won’t be used afterwards.

See Hashmaps, which is a sibling of mappings but based on hashtables.

Class: <mapping>

{srfi-146} On Gauche, this is just an alias of <tree-map>.

Constructors

Function: mapping comparator key value …

[SRFI-146] {srfi-146} Creates a new mapping with the given comparator, whose initial content is provided by key value ….

The comparator argument must be a comparator (see Basic comparators).

The key value … arguments must be even length, alternating keys and values.

(define m (mapping default-comparator 'a 1 'b 2))

(mapping-ref m 'a) ⇒ 1
(mapping-ref m 'b) ⇒ 2
Function: mapping-unfold p f g seed comparator

[SRFI-146] {srfi-146} Creates a new mapping, whose content is populated by three procedures, p, f and g, and a seed value seed, as follows.

In each iteration, we have a current seed value, whose initial value is seed.

First, p, a stop predicate, is applied to the current seed value. If it returns true, we stop iteration and returns the new mapping.

Next, f is applied to the current seed value. It must return two values. The first one is for a key and the second one for the value. We add this pair to the mapping.

Then, g is applied to the current seed value. The result becomes the seed value of the next iteration. And we iterate.

The following example creates a mapping that maps ASCII characters to their character codes:

(mapping-unfold (cut >= <> 128)
                (^c (values (integer->char c) c))
                (cut + <> 1)
                0
                default-comparator)
Function: mapping/ordered comparator key value …

[SRFI-146] {srfi-146} Similar to mapping, but keys are given in the ascending order w.r.t. the comparator. An implementation may use more efficient algorithm than mapping. In Gauche, this is the same as mapping at this moment.

Function: mapping-unfold/ordered p f g seed comparator

[SRFI-146] {srfi-146} Similar to mapping-unfold, but keys are generated in the ascendnig order w.r.t. the comparator. An implementation may use more efficient algorithm than mapping-unfold. In Gauche, this is the same as mapping-unfold at this moment.

Predicates

Function: mapping? obj

[SRFI-146] {srfi-146} Returns #t iff obj is a mapping object.

Function: mapping-empty? m

[SRFI-146] {srfi-146} M must be a mapping. Returns #t if m is empty, #f otherwise. In Gauche, this is same as tree-map-empty? (see Treemaps).

Function: mapping-contains? m key

[SRFI-146] {srfi-146} M must be a mapping. Returns #t if m has an entry with key, #f otherwise. In Gauche, this is same as tree-map-exists? (see Treemaps).

Function: mapping-disjoint? m1 m2

[SRFI-146] {srfi-146} Returns #t iff two mappings m1 and m2 have no keys in common. In other words, there’s no such key K that satisfy both (mapping-contains? m1 K) and (mapping-contains? m2 K).

Accessors

Function: mapping-ref m key :optional failure success

[SRFI-146] {srfi-146} Get the value from a mapping m associated with key, and calls success on the value, and returns its result. If m doesn’t have key, failure is invoked with no arguments and its result is returned. Both success and failure is called in tail context.

When failure is omitted and key is not found, an error is signaled. When success is omitted, identity is assumed.

Function: mapping-ref/default m key default

[SRFI-146] {srfi-146} Returns the value associated to key from a mapping m. If m doesn’t have key, default is returned.

Function: mapping-key-comparator m

[SRFI-146] {srfi-146} Returns a comparator used to compare keys in a mapping m. See Basic comparators, for the details of comparators.

Updaters

Note that the basic premise of mappings srfi is to treat mappings as immutable. Each updating operation comes with a purely functional version (without bang) and a linear update version (with bang), but the linear update version may not require to destructively modiy the passed mapping; it’s merely a hint that it may reuse the argument for the efficiency. You always need to use the returned mapping as the result of update. If you use linear update versions, you shouldn’t use the passed mapping afterwards, for there’s no guarantee how the state of the passed mapping is.

Function: mapping-adjoin m arg …
Function: mapping-adjoin! m arg …

[SRFI-146] {srfi-146}

Function: mapping-set m arg …
Function: mapping-set! m arg …

[SRFI-146] {srfi-146}

Function: mapping-replace m key value
Function: mapping-replace! m key value

[SRFI-146] {srfi-146}

Function: mapping-delete m key …
Function: mapping-delete! m key …

[SRFI-146] {srfi-146}

Function: mapping-delete-all m key-list
Function: mapping-delete-all! m key-list

[SRFI-146] {srfi-146}

Function: mapping-intern m key failure
Function: mapping-intern! m key failure

[SRFI-146] {srfi-146}

Function: mapping-update m key updater :optional failure success
Function: mapping-update! m key updater :optional failure success

[SRFI-146] {srfi-146}

Function: mapping-update/default m key updater default
Function: mapping-update!/default m key updater default

[SRFI-146] {srfi-146}

Function: mapping-pop m :optional failure
Function: mapping-pop! m :optional failure

[SRFI-146] {srfi-146}

Function: mapping-search m k failure success
Function: mapping-search! m k failure success

[SRFI-146] {srfi-146}

The whole mapping

Function: mapping-size m

[SRFI-146] {srfi-146}

Function: mapping-find pred m failure

[SRFI-146] {srfi-146}

Function: mapping-count pred m

[SRFI-146] {srfi-146}

Function: mapping-any? pred m
Function: mapping-every? pred m

[SRFI-146] {srfi-146}

Function: mapping-keys m
Function: mapping-values m

[SRFI-146] {srfi-146}

Function: mapping-entries m

[SRFI-146] {srfi-146}

11.31.1.1 Mapping and folding

Function: mapping-map proc comparator m

[SRFI-146] {srfi-146}

Function: mapping-map/monotone proc comparator m
Function: mapping-map/monotone! proc comparator m

[SRFI-146] {srfi-146}

Function: mapping-for-each proc m

[SRFI-146] {srfi-146}

Function: mapping-fold kons knil m

[SRFI-146] {srfi-146}

Function: mapping-fold/reverse kons knil m

[SRFI-146] {srfi-146}

Function: mapping-map->list proc m

[SRFI-146] {srfi-146}

Function: mapping-filter pred m
Function: mapping-filter! pred m

[SRFI-146] {srfi-146}

Function: mapping-remove pred m
Function: mapping-remove! pred m

[SRFI-146] {srfi-146}

Function: mapping-partition pred m
Function: mapping-partition! pred m

[SRFI-146] {srfi-146}

Copying and conversion

Function: mapping-copy m

[SRFI-146] {srfi-146}

Function: mapping->alist m

[SRFI-146] {srfi-146}

Function: alist->mapping comparator alist

[SRFI-146] {srfi-146}

Function: alist->mapping! m alist

[SRFI-146] {srfi-146}

Function: alist->mapping/ordered comparator alist
Function: alist->mapping/ordered! m alist

[SRFI-146] {srfi-146}

Submappings

Function: mapping=? comparator m1 m2 …

[SRFI-146] {srfi-146}

Function: mapping<? comparator m1 m2 …
Function: mapping<=? comparator m1 m2 …
Function: mapping>? comparator m1 m2 …
Function: mapping>=? comparator m1 m2 …

[SRFI-146] {srfi-146}

Set operations

Function: mapping-union m1 m2 …
Function: mapping-union! m1 m2 …

[SRFI-146] {srfi-146}

Function: mapping-intersection m1 m2 …
Function: mapping-intersection! m1 m2 …

[SRFI-146] {srfi-146}

Function: mapping-difference m1 m2 …
Function: mapping-difference! m1 m2 …

[SRFI-146] {srfi-146}

Function: mapping-xor m1 m2 …
Function: mapping-xor! m1 m2 …

[SRFI-146] {srfi-146}

Mappings with ordered keys

Function: mapping-min-key m
Function: mapping-max-key m

[SRFI-146] {srfi-146}

Function: mapping-min-value m
Function: mapping-max-value m

[SRFI-146] {srfi-146}

Function: mapping-min-entry m
Function: mapping-max-entry m

[SRFI-146] {srfi-146}

Function: mapping-key-predecessor m obj failure
Function: mapping-key-successor m obj failure

[SRFI-146] {srfi-146}

Function: mapping-range= m obj
Function: mapping-range< m obj
Function: mapping-range<= m obj
Function: mapping-range> m obj
Function: mapping-range>= m obj

[SRFI-146] {srfi-146}

Function: mapping-range=! m obj
Function: mapping-range<! m obj
Function: mapping-range<=! m obj
Function: mapping-range>! m obj
Function: mapping-range>=! m obj

[SRFI-146] {srfi-146}

Function: mapping-split m obj
Function: mapping-split! m obj

[SRFI-146] {srfi-146}

Function: mapping-catenate comparator m1 key value m2
Function: mapping-catenate! m1 key value m2

[SRFI-146] {srfi-146}

Comparators

Function: make-mapping-comparator comparator

[SRFI-146] {srfi-146}

Variable: mapping-comparator

[SRFI-146] {srfi-146}


Previous: , Up: Mappings and hashmaps   [Contents][Index]

11.31.2 Hashmaps

Module: srfi-146.hash

This module provides hashtable-based hashmap API. On Gauche, an instance of hashmap is just an instance of built-in <hash-table>. However, the API assumes a hashmap to be treated as immutable data structure, except the “linear update” APIs, which is allowed to mutate the hashmaps passed to the arguments, under assumption that the argument won’t be used afterwards.

See Mappings, which is a sibling of hashmaps but based on treemaps.

Constructors

Function: hashmap comparator key value …

[SRFI-146] {srfi-146.hash} Creates a new hashmap with the given comparator, whose initial content is provided by key value ….

The comparator argument must be a comparator (see Basic comparators).

The key value … arguments must be even length, alternating keys and values.

(define m (hashmap default-comparator 'a 1 'b 2))

(hashmap-ref m 'a) ⇒ 1
(hashmap-ref m 'b) ⇒ 2
Function: hashmap-unfold p f g seed comparator

[SRFI-146] {srfi-146.hash} Creates a new hashmap, whose content is populated by three procedures, p, f and g, and a seed value seed, as follows.

In each iteration, we have a current seed value, whose initial value is seed.

First, p, a stop predicate, is applied to the current seed value. If it returns true, we stop iteration and returns the new hashmap.

Next, f is applied to the current seed value. It must return two values. The first one is for a key and the second one for the value. We add this pair to the hashmap.

Then, g is applied to the current seed value. The result becomes the seed value of the next iteration. And we iterate.

The following example creates a hashmap that maps ASCII characters to their character codes:

(hashmap-unfold (cut >= <> 128)
                (^c (values (integer->char c) c))
                (cut + <> 1)
                0
                default-comparator)

Predicates

Function: hashmap? obj

[SRFI-146] {srfi-146.hash} Returns #t iff obj is a hashmap object.

Function: hashmap-empty? m

[SRFI-146] {srfi-146.hash} M must be a hashmap. Returns #t if m is empty, #f otherwise. In Gauche, this is same as tree-map-empty? (see Treemaps).

Function: hashmap-contains? m key

[SRFI-146] {srfi-146.hash} M must be a hashmap. Returns #t if m has an entry with key, #f otherwise. In Gauche, this is same as tree-map-exists? (see Treemaps).

Function: hashmap-disjoint? m1 m2

[SRFI-146] {srfi-146.hash} Returns #t iff two hashmaps m1 and m2 have no keys in common. In other words, there’s no such key K that satisfy both (hashmap-contains? m1 K) and (hashmap-contains? m2 K).

Accessors

Function: hashmap-ref m key :optional failure success

[SRFI-146] {srfi-146.hash} Get the value from a hashmap m associated with key, and calls success on the value, and returns its result. If m doesn’t have key, failure is invoked with no arguments and its result is returned. Both success and failure is called in tail context.

When failure is omitted and key is not found, an error is signaled. When success is omitted, identity is assumed.

Function: hashmap-ref/default m key default

[SRFI-146] {srfi-146.hash} Returns the value associated to key from a hashmap m. If m doesn’t have key, default is returned.

Function: hashmap-key-comparator m

[SRFI-146] {srfi-146.hash} Returns a comparator used to compare keys in a hashmap m. See Basic comparators, for the details of comparators.

Updaters

Note that the basic premise of hashmaps srfi is to treat hashmaps as immutable. Each updating operation comes with a purely functional version (without bang) and a linear update version (with bang), but the linear update version may not require to destructively modiy the passed hashmap; it’s merely a hint that it may reuse the argument for the efficiency. You always need to use the returned hashmap as the result of update. If you use linear update versions, you shouldn’t use the passed hashmap afterwards, for there’s no guarantee how the state of the passed hashmap is.

Function: hashmap-adjoin m arg …
Function: hashmap-adjoin! m arg …

[SRFI-146] {srfi-146.hash}

Function: hashmap-set m arg …
Function: hashmap-set! m arg …

[SRFI-146] {srfi-146.hash}

Function: hashmap-replace m key value
Function: hashmap-replace! m key value

[SRFI-146] {srfi-146.hash}

Function: hashmap-delete m key …
Function: hashmap-delete! m key …

[SRFI-146] {srfi-146.hash}

Function: hashmap-delete-all m key-list
Function: hashmap-delete-all! m key-list

[SRFI-146] {srfi-146.hash}

Function: hashmap-intern m key failure
Function: hashmap-intern! m key failure

[SRFI-146] {srfi-146.hash}

Function: hashmap-update m key updater :optional failure success
Function: hashmap-update! m key updater :optional failure success

[SRFI-146] {srfi-146.hash}

Function: hashmap-update/default m key updater default
Function: hashmap-update!/default m key updater default

[SRFI-146] {srfi-146.hash}

Function: hashmap-pop m :optional failure
Function: hashmap-pop! m :optional failure

[SRFI-146] {srfi-146.hash}

Function: hashmap-search m k failure success
Function: hashmap-search! m k failure success

[SRFI-146] {srfi-146.hash}

The whole hashmap

Function: hashmap-size m

[SRFI-146] {srfi-146.hash}

Function: hashmap-find pred m failure

[SRFI-146] {srfi-146.hash}

Function: hashmap-count pred m

[SRFI-146] {srfi-146.hash}

Function: hashmap-any? pred m
Function: hashmap-every? pred m

[SRFI-146] {srfi-146.hash}

Function: hashmap-keys m
Function: hashmap-values m

[SRFI-146] {srfi-146.hash}

Function: hashmap-entries m

[SRFI-146] {srfi-146.hash}

11.31.2.1 Mapping and folding

Function: hashmap-map proc comparator m

[SRFI-146] {srfi-146.hash}

Function: hashmap-for-each proc m

[SRFI-146] {srfi-146.hash}

Function: hashmap-fold kons knil m

[SRFI-146] {srfi-146.hash}

Function: hashmap-map->list proc m

[SRFI-146] {srfi-146.hash}

Function: hashmap-filter pred m
Function: hashmap-filter! pred m

[SRFI-146] {srfi-146.hash}

Function: hashmap-remove pred m
Function: hashmap-remove! pred m

[SRFI-146] {srfi-146.hash}

Function: hashmap-partition pred m
Function: hashmap-partition! pred m

[SRFI-146] {srfi-146.hash}

Copying and conversion

Function: hashmap-copy m

[SRFI-146] {srfi-146.hash}

Function: hashmap->alist m

[SRFI-146] {srfi-146.hash}

Function: alist->hashmap comparator alist

[SRFI-146] {srfi-146.hash}

Function: alist->hashmap! m alist

[SRFI-146] {srfi-146.hash}

Subhashmaps

Function: hashmap=? comparator m1 m2 …

[SRFI-146] {srfi-146.hash}

Function: hashmap<? comparator m1 m2 …
Function: hashmap<=? comparator m1 m2 …
Function: hashmap>? comparator m1 m2 …
Function: hashmap>=? comparator m1 m2 …

[SRFI-146] {srfi-146.hash}

Set operations

Function: hashmap-union m1 m2 …
Function: hashmap-union! m1 m2 …

[SRFI-146] {srfi-146.hash}

Function: hashmap-intersection m1 m2 …
Function: hashmap-intersection! m1 m2 …

[SRFI-146] {srfi-146.hash}

Function: hashmap-difference m1 m2 …
Function: hashmap-difference! m1 m2 …

[SRFI-146] {srfi-146.hash}

Function: hashmap-xor m1 m2 …
Function: hashmap-xor! m1 m2 …

[SRFI-146] {srfi-146.hash}

Comparators

Function: make-hashmap-comparator comparator

[SRFI-146] {srfi-146.hash}

Variable: hashmap-comparator

[SRFI-146] {srfi-146.hash}


Previous: , Up: Mappings and hashmaps   [Contents][Index]