Dictionary structures

Dictionaries map values to unique keys.Common Lispstandard already contains such structures (hash tables, alists, plists) and therefore idea should not be alien to a Lisp programmer. CL-DATA-STRUCTURES offers both functional and mutable dictionaries, with HAMT being the prime example of complete, feature rich implementation of the protocol. In practice, containers present in this module are either ordered containers (for instance binary search trees) or some sort of unordered hash table (either classiscal hashtable or some sort of hashing tree). In each case, overview of data structure is present in this document.

API

To obtain value under key use following functions:

  • AT

To change mapping use following purely functional functions:

  • INSERT
  • ADD
  • UPDATE
  • UPDATE-IF
  • ERASE
  • ERASE-IF

To change mapping in destructive way, use following functions:

  • (SETF AT)
  • ADD!
  • UPDATE!
  • UPDATE-IF!
  • ERASE!
  • ERASE-IF!

This package adds another set of trait classes, specific to dictionaries.

FUNDAMENTAL-DICTIONARY
Inheritance
Description: Container that provides location to value mapping. Either ordered or unordered.
FUNDAMENTAL-HASHING-DICTIONARY
Inheritance
Description: Dictionary that uses hashing function. Hashing function is assumed to return fixnum.
FUNCTIONAL-DICTIONARY
Inheritance
Description: Functional variant of a dictionary.
MUTABLE-DICTIONARY
Inheritance
Description: Mutable variant of a dictionary.
TRANSACTIONAL-DICTIONARY
Inheritance
Description: Transactional variant of a dictionary.
LAZY-DICTIONARY
Inheritance
Description: Lazy variant of a dictionary.
FUNCTIONAL-HASHING-DICTIONARY
Inheritance
Description: Functional variant of hashing a dictionary.
MUTABLE-HASHING-DICTIONARY
Inheritance
Description: Mutable variant of hashing a dictionary.
TRANSACTIONAL-HASHING-DICTIONARY
Inheritance
Description: Transactional variant of hashing a dictionary.
LAZY-HASHING-DICTIONARY
Inheritance
Description: Lazy variant of a hashing dictionary.

HAMT

HAMT stands from hash array mapped trie. This data structure is used the most commonly as functional dictionary in standard libraries of few recent languages (including Clojure and Scala). Cl-data-structures implementation offers also mutable and transactional variant of this structure. Although this container is not optimized for destructive modification, it is still faster then copy-on-write whole path from root to the bottom (conflict) node.

Dictionary implementation of HAMT is present in the system as a class.

HAMT-DICTIONARY
Inheritance
Description: Root HAMT dictionary class.
FUNCTIONAL-HAMT-DICTIONARY
Inheritance
Description: HAMT dictionary that implements functional api.
MUTABLE-HAMT-DICTIONARY
Inheritance
Description: HAMT dictionary that implements mutable api.

As you can see, it inherits DICTIONARY trait class as well as lower level FUNDAMENTAL-HAMT-CONTAINER class. All instances of this class can be used with following functions:

HAMT-DICTIONARY-AT
Lambda List: ()
Implementation of AT
HAMT-DICTIONARY-SIZE
Lambda List: (CONTAINER)
Implementation of SIZE

Functional dictionary is represented by the following class:

There is no lazy-hamt-dictionary class, because lazy hamt dictionary is nothing more then a TRANSACTIONAL-HAMT-DICTIONARY inside LAZY-BOX.

Constructing

To construct HAMT dictionary, use following functions.

Symbols in the package CL-DATA-STRUCTURES.DICTS.HAMT:
MAKE-FUNCTIONAL-HAMT-DICTIONARY
Lambda List: (HASH-FN EQUAL-FN)
Syntax: make-functional-hamt-dictionary hash-fn equal-fn &key max-depth => functional-hamt-dictionary
Description: Constructs and return new functional-hamt-dictionary
Returns: new instance of functional-hamt-dictionary.
Notes: In theory HAMT can use infinite length of hash but this implementation uses 60 oldest bits at most.
MAKE-MUTABLE-HAMT-DICTIONARY
Lambda List: (HASH-FN EQUAL-FN)
Syntax: make-mutable-hamt-dictionary hash-fn equal-fn &key max-depth => mutable-hamt-dictionary
Description: Constructs and returns a new mutable-hamt-dictionary
Returns: new instance of mutable-hamt-dictionary.
Notes: In theory HAMT can use infinite length of hash but this implementation uses 60 oldest bits at most.
MAKE-TRANSACTIONAL-HAMT-DICTIONARY
Lambda List: (HASH-FN EQUAL-FN)
Syntax: make-transactional-hamt-dictionary hash-fn equal-fn &key max-depth => mutable-hamt-dictionary
Description: Constructs and returns a new mutable-hamt-dictionary
Returns: new instance of transactional-hamt-dictionary.
Notes: In theory HAMT can use infinite length of hash but this implementation uses 60 oldest bits at most.

Sparse RRB Vector

Sparse variant of the RRB vector. Unlike the CL:HASH-TABLE, this container will guarantee that the content is stored in the ascending order. Just like in the case of the RRB vectors, modification of the tail (which includes pushing new elements to the end) is optimized but put functions are not supported.

MUTABLE-SPARSE-RRB-VECTOR
Inheritance
Description: SRRB sparse vector that implements mutable api.
FUNCTIONAL-SPARSE-RRB-VECTOR
Inheritance
Description: SRRB sparse vector that implements mutable api.
TRANSACTIONAL-SPARSE-RRB-VECTOR
Inheritance
Description: Transactional SRRB sparse vector that implements mutable api.

Constructing

To construct SRRB vector, use following functions.

Symbols in the package CL-DATA-STRUCTURES.DICTS.HAMT:
MAKE-FUNCTIONAL-SPARSE-RRB-VECTOR
Lambda List: (&KEY (ELEMENT-TYPE T))
Description: Constructs and returns a functional variant of the sparse rrb vector.
MAKE-MUTABLE-SPARSE-RRB-VECTOR
Lambda List: (&KEY (ELEMENT-TYPE T))
Description: Constructs and returns a mutable variant of the sparse rrb vector.
MAKE-TRANSACTIONAL-SPARSE-RRB-VECTOR
Lambda List: (&KEY (ELEMENT-TYPE T))
Description: Constructs and returns a transactional variant of the sparse rrb vector.