An association list as implemented by this library is a
collection of unique keys that are associated to values.
Keys must be ground, values need not be.
An association list can be used to fetch elements via their
keys and to enumerate its elements in ascending order of their
keys.
This library uses AVL trees to implement association lists.
This means that
- inserting a key
- changing an association
- fetching a single element
are all O(log(N)) worst-case (and
expected) time operations, where
N denotes the number of elements in the association list.
The logarithmic overhead is often acceptable in practice. Notable
advantages of association lists over several other methods are:
library(assoc) is written entirely in Prolog, making it
portable to other systems- the interface predicates fit the declarative nature of Prolog,
avoiding destructive updates to terms
- AVL trees scale very predictably and can be used to represent sparse
arrays efficiently.
