persistent-hash-map

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

persistent-hash-map

A persistent associative data structure.

This egg provides a (mostly) direct port of ClojureScript's PersistentHashMap which is an implementation of Phil Bagwell's Hash Array Mapped Trie (HAMT). As an extension to the original HAMT, this implementation provides a persistent map data structure which means that update operations yield a new version without modifying the old one. In order to preserve space and time efficieny it employs structural sharing between different versions by means of path copying.

A persistent map can be converted to a transient map which can be mutated and later be turned back into a persistent map. This allows for more efficient modifications than the persistent map does at the expense of having to coordinate concurrent updates.

Preliminary benchmarks indicate that key lookup times are comparable but slightly worse than those of SRFI 69 hash tables whereas transient maps insertion times are about on par.

Implementation notes

The data structures provided by this egg (persistent and transient maps) use the equal?-hash function from the srfi-69 unit for hashing keys and thus equal? for comparing keys on hash collision.

Compatibility

Currently a few compatibility constraints apply to this extension.

Chicken version requirement

The current release only works with Chicken versions >= 4.7.5 as it makes heavy use of the type declaration system which was introduced with that version. Future releases are planned to be compatible with older Chicken versions, as well.

Compiler __builtin_popcount requirement

The current release requires a C compiler with support for __builtin_popcount. This applies at least to GCC since version 3.4 and LLVM / clang since version 1.5. If your processor supports a native popcount instruction you can enable it by passing -C -mpopcnt via the CSC_OPTIONS environment variable when installing this extension.

API

Persistent maps

The following procedures all operate on persistent maps. Updating procedures (such as map-add) always return a new map instead of mutating the passed map(s).

(persistent-map [key value ...])procedure

Returns a persistent map, optionally populated with the given key value pairs.

Example:

(persistent-map 'foo 1 'bar 2)
=> #<persistent-hash-map (bar . 2) (foo . 1)>

alist->map alistprocedure

Constructs a persistent map from alist.

Example:

(alist->map '((foo . 1) (bar . 2)))
=> #<persistent-hash-map (bar . 2) (foo . 1)>

map->alist mapprocedure

Constructs an alist from map.

Example:

(map->alist (persistent-map 'foo 1 'bar 2))
=> ((bar . 2) (foo . 1))

map? xprocedure: Checks whether x is a persistent map.

map-size mapprocedure: Returns the number of entries in map.

(map-add map key value [key value ...])procedure

Returns map with the given key value pairs added. Existing keys will be overridden.

Example:

(map-add (persistent-map 'foo 1) 'foo 2 'bar 3)
=> #<persistent-hash-map (bar . 3) (foo . 2)>

map-contains? map keyprocedure: Checks whether map contains an entry for key.

(map-delete map key [key ...])procedure

Returns map without the given keys. Non-existing keys will be ignored.

Example:

(map-delete (persistent-map 'foo 1 'bar 2) 'foo 'qux)
=> #<persistent-hash-map (bar . 2)>

map-ref map key #!optional not-foundprocedure

Returns the value associated with key in map or not-found (default #f) if key does not exist.

Example:

(define m (persistent-map 'foo 1))

(map-ref m 'foo 2) => 1
(map-ref m 'bar)   => #f
(map-ref m 'bar 2) => 2

map-ref-in map keys #!optional not-foundprocedure

Recursively looks up the list of keys in the nested map and returns the value associated with the innermost key or not-found (default #f) if one of the keys does not exist.

Example:

(define m (persistent-map 'foo (persistent-map 'bar (persistent-map 'qux 123))))

(map-ref-in m '(foo bar qux)) => 123
(map-ref-in m '(foo qux))     => #f

map-update-in map keys proc #!rest argsprocedure

Recursively looks up the keys in the nested map like map-ref-in but applies proc to the existing value of the innermost key (or #f if it doesn't exist, yet) and the given args. For non-existing intermediate keys new persistent maps will be added.

Example:

(define m (persistent-map 'foo (persistent-map 'bar 1)))

(map-update-in m '(foo bar) + 1)
=> #<persistent-hash-map (foo . #<persistent-hash-map (bar . 2)>)>

(map-update-in m '(foo qux) (lambda (x) (or x 9)))
=> #<persistent-hash-map (foo . #<persistent-hash-map (bar . 1) (qux . 9)>)>

map-equal? x yprocedure: Checks whether the given maps x and y are equal?. Values which are maps themselves will be recursively compared with map-equal?.

map-keys mapprocedure: Returns a list of the keys contained in map.

map-values mapprocedure: Returns a list of the values contained in map.

map-merge map1 map2procedure: Returns a new map with the entries of map2 merged into map1. Entries which are present in both maps will be overridden by those in map2.

map-reduce f init mapprocedure

Reduces the entries of map by applying them to f together with the current reduction value, starting with init.

Example:

(define m (persistent-map 'foo 1 'bar 2))

(map-reduce cons* '() m) => (bar 2 foo 1)

map-collect proc mapprocedure

Applies proc to each entry of map and collects the return values in a list as the final result.

Example:

(map-collect cons (persistent-map 1 2 3 4))
=> ((1 . 2) (3 . 4))

map-each proc mapprocedure

Applies proc to each entry of map for its side-effects. The return value is undefined.

Example:

(map-each (lambda (key value)
            (pp (list key: key value: value)))
          (persistent-map 'foo 1 'bar 2))

Output:

(key: foo value: 1)
(key: bar value: 2)

Transient maps

The following procedures all operate on transient maps which are mutable versions of persistent maps. A transient map can be turned into a persistent map and cannot be modified afterwards anymore.

map->transient-map mapprocedure: Returns a transient copy of the persistent map.

transient-map? xprocedure: Checks whether x is a transient map.

persist-map! mapprocedure: Marks map as persistent and returns a persistent version of it. After persist-map! has been called on a transient map it can't be mutated anymore. Calling persist-map! twice on the same transient map is an error.

(map-add! map key value [key value ...])procedure

Adds the given key value pairs to map and returns it.

Example:

(define m (map->transient-map (persistent-map)))

(for-each
 (lambda (k v) (map-add! m k v))
 '(foo bar)
 '(1 2))

(persist-map! m)
=> #<persistent-hash-map (bar . 2) (foo . 1)>

(map-delete! map key [key ...])procedure

Deletes the given keys from map and returns it. Non-existing keys are ignored.

Example:

(define m
  (map->transient-map (persistent-map 'foo 1 'bar 2)))

(map-delete! m 'bar)
(persist-map! m)
=> #<persistent-hash-map (foo . 1)>

0.0.4: Fix transient maps to not modify the original persistent map
0.0.3: Actual 32 bit compatibility
0.0.2: 32 bit compatibility (broken)
0.0.1: Initial release

License

The use and distribution terms for this software are covered by the Eclipse Public License 1.0.

chickadee » persistent-hash-map

Identifier search

Outdated egg!