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.
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.
Currently a few compatibility constraints apply to this extension.
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.
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.
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.
(persistent-map 'foo 1 'bar 2) => #<persistent-hash-map (bar . 2) (foo . 1)>
- alist->map alistprocedure
Constructs a persistent map from alist.
(alist->map '((foo . 1) (bar . 2))) => #<persistent-hash-map (bar . 2) (foo . 1)>
- map->alist mapprocedure
Constructs an alist from map.
(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.
(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.
(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.
(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.
(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.
(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.
(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.
(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.
(map-each (lambda (key value) (pp (list key: key value: value))) (persistent-map 'foo 1 'bar 2))
(key: foo value: 1) (key: bar value: 2)
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.
(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.
(define m (map->transient-map (persistent-map 'foo 1 'bar 2))) (map-delete! m 'bar) (persist-map! m) => #<persistent-hash-map (foo . 1)>
The source code is hosted at Bitbucket. Feel free to fork it and send pull requests there.
Moritz Heidkamp, based on the ClojureScript implementation by Rich Hickey (c).
- Fix transient maps to not modify the original persistent map
- Actual 32 bit compatibility
- 32 bit compatibility (broken)
- Initial release
Copyright (c) 2013, Moritz Heidkamp. All rights reserved.
The use and distribution terms for this software are covered by the Eclipse Public License 1.0.