gauche.dictionary- Dictionary framework
A dictionary is an abstract class for objects that can map a key to a value. This module provides some useful generic functions for dictionaries, plus generic dictionary classes built on top of other dictionary classes.
|• Generic functions for dictionaries:|
|• Generic dictionaries:|
These generic functions are useful to implement algorithms common to any dictionary-like objects, a data structure that maps discrete, finite set of keys to values. (Theoretically we can think of continuous and/or infinite set of keys, but implementation-wise it is cleaner to limit the dictionary
Among built-in classes,
implement the dictionary interface. All the
dbm module also implement it.
To make your own class implement the dictionary interface, you have
to provide at least
(You can omit
dict-delete! if the datatype doesn’t allow
Other generic functions
have default behavior built on top of these. You can
implement other methods as well, potentially to gain better performance.
(Note: Dictionaries are also collections, so you can use collection
methods as well; for example, to get the number of entries, just use
<dictionary>) key :optional default
Returns the value corresponding to the key. If the dictionary doesn’t have an entry with key, returns default when it is provided, or raises an error if not.
<dictionary>) key value
Puts the mapping from key to value into the dictionary.
<dictionary>) key value
This works the same as
#t if the dictionary has an entry with key,
#f if not.
Removes an entry with key form the dictionary. If the dictionary doesn’t have such an entry, this function is noop.
Empties the dictionary. Usually this is much faster than looping over keys to delete them one by one.
Should return a comparator used to compare keys.
<dictionary>) proc seed
Calls a procedure proc over each entry in a dictionary dict, passing a seed value. Three arguments are given to proc; an entry’s key, an entry’s value, and a seed value. Initial seed value is seed. The value returned from proc is used for the seed value of the next call of proc. The result of the last call of proc is returned from dict-fold.
If dict is
<ordered-dictionary>, proc is called
in the way to keep the following associative order, where
the key is ordered from K0 (minimum) to Kn (maximum), and
the corresponding values is from V0 to Vn:
(proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed)))
<ordered-dictionary>) proc seed
dict-fold, but the associative order of applying proc
is reversed as follows:
(proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))
This generic function is only defined on
Calls proc with a key and a value of every entry in the dictionary dict. For ordered dictionaries, proc is guaranteed to be called in the increasing order of keys.
Calls proc with a key and a value of every entry in the dictionary dict, and gathers the result into a list and returns it. For ordered dictionaries, the result is in the increasing order of keys (it doesn’t necessarily mean proc is called in that order).
Returns a list of all keys or values of a dictionary dict, respectively. For ordered dictionaries, the returned list is in the increasing order of keys.
Returns a list of pairs of key and value in the dictionary. The order of pairs is undefined.
<dictionary>) key value
A shorthand way to say
(dict-put! dict key (cons value (dict-get dict key '()))). A concrete implementation may be more efficient
(e.g. it may not search key twice.)
<dictionary>) key :optional fallback
(dict-get dict key) is a pair p,
the entry value is replaced with
(cdr p) and the procedure
(car p). If no entry for key is in the table,
or the entry isn’t a a pair, the table isn’t modified, and
fallback is returned if given, or an error is raised.
<dictionary>) key proc :optional fallback
Works like the following code, except that the concrete implementation may be more efficient by looking up key only once.
(rlet1 x (proc (dict-get dict key fallback)) (dict-put! dict key x))
Many dictionary-like datatypes already has their own procedures
that directly corresponds to the generic dictionary API, and adding
dictionary interface tends to become a simple repetition of
define-methods, like this:
(define-method dict-put! ((dict <my-dict>) key value) (my-dict-put! key value))
define-dict-interface macro is a convenient way to
define those methods in a batch. Each method argument is
a keyword that corresponds to
dict-method, and proc
is the name of the datatype-specific procedure. Here’s the definition
of dict interface for
<tree-map> and you’ll get the idea.
You don’t need to provide every dictionary interface.
(define-dict-interface <tree-map> :get tree-map-get :put! tree-map-put! :delete! tree-map-delete! :clear! tree-map-clear! :comparator tree-map-comparator :exists? tree-map-exists? :fold tree-map-fold :fold-right tree-map-fold-right :for-each tree-map-for-each :map tree-map-map :keys tree-map-keys :values tree-map-values :pop! tree-map-pop! :push! tree-map-push! :update! tree-map-update! :->alist tree-map->alist)
Provides a bidirectional map (bimap), a relation between two set of values, of which you can lookup both ways.
Internally, a bimap consists of two dictionaries, left map and right map. Think a bimap as a relation between xs and ys. The left map takes an x as a key and returns corresponding y as its value. The right map takes an y as a key and returns corresponding x as its value.
<bimap> only supports strict one-to-one mapping.
Mutating interface (
modifies both left and right maps to maintain this one-to-one mapping.
(In future, we may provide an option to make many-to-one and
A bimap can be used as a dictionary, with the generic dictionary
functions such as
dict-get. In such cases, the left map takes
precedence; that is, the key given to
dict-get etc. is
regarded as the key to the left map.
Creates a new bimap consists of two dictionaries, left-map and right-map. It is the caller’s responsibility to choose appropriate type of dictionaries; for example, if you want to create a relation between a string and a number, you man want to create it like this:
(make-bimap (make-hash-table 'string=?) ; string -> number (make-hash-table 'eqv?)) ; number -> string
The keyword argument on-conflict specifies what will happen when the added entry would conflict the existing entries. The following values are allowed:
This is the default behavior. Duplicate relations are silently
removed in order to maintain one-to-one mapping. For example,
suppose a bimap between strings and numbers has had
("foo", 1) and
("bar", 2). When you try to
("bar", 2) with this option, the first two entries
are removed. Returns
Raises an error when duplicate relations are found.
When duplicate relations are found, does nothing and returns
Note: At this moment, an attempt to add a relation exactly same as the existing one is regareded as a conflict. This limitation may be lifted in future.
Returns the left or right map of bimap, respectively. Do not mutate the returned map, or you’ll break the consistency of the bimap.
Lookup the value corresponding to the key in the left or right map of bimap. If no entry is found for key, default is returned if provided, otherwise an error is raised.
#f if the left or right map of bimap has an entry of
Put a relation (x, y) into the bimap.
(bimap-left-get x) will return y,
(bimap-left-get y) will return x.
If the bimap already have relations with x and/or y,
the conflict is handled according to the value of on-conflict;
make-bimap for the possible values and their meanings.
The on-conflict keyword argument can override the
bimap’s default setting specified at its creation time.
Deletes an relation with the given left key or right key from bimap. Both left and right maps are modified so that the consistency is maintained. If there’s no relations with given key, these are noop.