## A.3 library(assoc): Association lists

Authors: Richard A. O'Keefe, L.Damas, V.S.Costa and Markus Triska

Elements of an association list have 2 components: A (unique) key and a value. Keys should 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. The `library(assoc)` module uses AVL trees to implement association lists. This makes inserting, changing and fetching a single element an O(log(N)) (where N denotes the number of elements in the list) expected time (and worst-case time) operation.

assoc_to_list(+Assoc, -List)
  List is a list of Key-Value pairs corresponding to the associations in Assoc in ascending order of keys.
assoc_to_keys(+Assoc, -List)
  List is a list of Keys corresponding to the associations in Assoc in ascending order.
assoc_to_values(+Assoc, -List)
  List is a list of Values corresponding to the associations in Assoc in ascending order of the keys they are associated to.
empty_assoc(-Assoc)
  Assoc is unified with an empty association list.
gen_assoc(?Key, +Assoc, ?Value)
  Enumerate matching elements of Assoc in ascending order of their keys via backtracking.
get_assoc(+Key, +Assoc, ?Value)
  Value is the value associated with Key in the association list Assoc.
get_assoc(+Key, +Assoc, ?Old, ?NewAssoc, ?New)
  NewAssoc is an association list identical to Assoc except that the value associated with Key is New instead of Old.
list_to_assoc(+List, -Assoc)
  Assoc is an association list corresponding to the Key-Value pairs in List. List must not contain duplicate keys.
map_assoc(:Goal, +Assoc)
  Goal(V) is true for every value V in Assoc.
map_assoc(:Goal, +AssocIn, ?AssocOut)
  AssocOut is AssocIn with Goal applied to all corresponding pairs of values.
max_assoc(+Assoc, ?Key, ?Value)
  Key and Value are key and value of the element with the largest key in Assoc.
min_assoc(+Assoc, ?Key, ?Value)
  Key and Value are key and value of the element with the smallest key in Assoc.
ord_list_to_assoc(+List, -Assoc)
  Assoc is an association list correspond to the Key-Value pairs in List, which must occur in strictly ascending order of their keys.
put_assoc(+Key, +Assoc, +Value, ?NewAssoc)
  NewAssoc is an association list identical to Assoc except that Key is associated with Value. This can be used to insert and change associations.
is_assoc(+Assoc)
  True if Assoc is a valid association list. This predicate verifies the validity of each node in the AVL tree.