12.17 data.imap - Immutable map

Module: data.imap ¶

This module provides a immutable data structure with O(log n) access and update operations (here, update means to return a new structure with requested changes). The current implementation is based on the functional red-black tree.

Although lists and alists are useful for stack-like immutable operations, where you can add and remove items to the head of existing data without modifying them, they require O(n) access time and sometimes you need better one. The <imap> object provides O(log n) access, in exchange of O(log n) insertion and deletion.

Class: <imap-meta> ¶

{data.imap} Metaclass of <imap>.

Class: <imap> ¶

{data.imap} Immutable map class. An instance of <imap-meta>.

Inherits <ordered-dictionary>, conforms dictionary protocol except mutating operators (see gauche.dictionary - Dictionary framework). As a sequence, you can access key-value pairs in increasing order of keys.

Function: make-imap ¶

Function: make-imap comparator ¶

Function: make-imap key=? key<? ¶

{data.imap} Creates a new empty immutable map. Without arguments, default-comparator is used to compare keys. To give a specific comparator, use the second form; the comparator argument should have comparison procedure. For the details of comparators, see Basic comparators. The third form creates a key comparator from a equality predicate key=? and less-than predicate key<?, both must accept two keys. This interface is consistent with tree-map (see Treemaps).

Function: alist->imap alist ¶

Function: alist->imap alist comparator ¶

Function: alist->imap alist key=? key<? ¶

{data.imap} Creates and returns an immutable map containing key-value associations given by an assoc-list alist. This may be a bit more efficient than creating an empty map with make-imap and populates it with imap-put one by one.

The comparator argument specifies how to compare the keys. It must have comparison procedure. If omitted, default-comparator is used. See Basic comparators, for the details.

The third form creates a key comparator from a equality predicate key=? and less-than predicate key<?, both must accept two keys.

(define m (alist->imap '((a . 1) (b . 2))))

(imap-get m 'a) ⇒ 1
(imap-get m 'b) ⇒ 2

Function: tree-map->imap tree-map ¶

{data.imap} Returns a new immutable map with the same content (and the same comparator) as tree-map.

Function: imap? obj ¶

{data.imap} Returns #t if obj is an immutable map, #f otherwise.

Function: imap-empty? immap ¶

{data.imap} Returns #t if an immutable map immap is empty, #f otherwise.

Function: imap-exists? immap key ¶

{data.imap} Returns #t if key exists in an immutable map immap.

Function: imap-get immap key :optional default ¶

{data.imap} Returns the value associated with key in an immutable map immap. If immap doesn’t have key, default is returned when provided, otherwise an error is signalled.

Function: imap-put immap key val ¶

{data.imap} Returns a new immutable map where association of key to val is added to (or replaced in) an immutable map immap. This operation is O(log n).

(define m1 (alist->imap '((a . 1) (b . 2))))

(define m2 (imap-put m1 'a 3))

(imap-get m2 'a)  ⇒ 3
(imap-get m1 'a)  ⇒ 1  ; not affected

Function: imap-delete immap key ¶

{data.imap} Returns a new immutable map where key is removed from immap. If immap doesn’t have key, returned map has the same content as immap.

(define m1 (alist->imap '((a . 1) (b . 2))))

(define m2 (imap-delete m1 'a))

(imap-get m2 'a #f)  ⇒ #f
(imap-get m1 'a)     ⇒ 1  ; not affected

Function: imap-min immap ¶

Function: imap-max immap ¶

{data.imap} Returns a pair of key and value with the minimum or maximum key in immap, respectively. If immap is empty, #f is returned.