10.2 Association Lists—library(assoc)

This library provides a binary tree implementation of "association lists". The binary tree is not kept balanced, as opposed to library(avl), which provides similar functionality based on balanced AVL trees.

Exported predicates:

empty_assoc(?Assoc)

is true when Assoc is an empty assoc.

assoc_to_list(+Assoc, -List)

assumes that Assoc is a proper "assoc" tree, and is true when List is a list of Key-Value pairs in ascending order with no duplicate Keys specifying the same finite function as Assoc. Use this to convert an assoc to a list.

gen_assoc(?Key, +Assoc, ?Value)

assumes that Assoc is a proper "assoc" tree, and is true when Key is associated with Value in Assoc. Use this to enumerate Keys and Values in the Assoc, or to find Keys associated with a particular Value. If you want to look up a particular Key, you should use get_assoc/3. Note that this predicate is not determinate. If you want to maintain a finite bijection, it is better to maintain two assocs than to drive one both ways. The Keys and Values are enumerated in ascending order of Keys.

get_assoc(+Key, +Assoc, -Value)

assumes that Assoc is a proper "assoc" tree. It is true when Key is identical to (==) one of the keys in Assoc, and Value unifies with the associated value. Note that since we use the term ordering to identify keys, we obtain logarithmic access, at the price that it is not enough for the Key to unify with a key in Assoc, it must be identical. This predicate is determinate. The argument order follows the pattern established by the built-in predicate arg/3 (called the arg/3, or selector, rule):

    predicate(indices, structure, element).

The analogy with arg(N, Term, Element) is that

    Key:N :: Assoc:Term :: Value:Element.

get_next_assoc(+Key, +Assoc, -Knext, -Vnext)

is true when Knext is the smallest key in Assoc such that Knext@>Key, and Vnext is the value associated with Knext. If there is no such Knext, get_next_assoc/4 naturally fails. It assumes that Assoc is a proper assoc. Key should normally be ground. Note that there is no need for Key to be in the association at all. You can use this predicate in combination with min_assoc/3 to traverse an association tree; but if there are N pairs in the tree the cost will be O(N lg N). If you want to traverse all the pairs, calling assoc_to_list/2 and walking down the list will take O(N) time.

get_prev_assoc(+Key, +Assoc, -Kprev, -Vprev)

is true when Kprev is the largest key in Assoc such that Kprev@<Key, and Vprev is the value associated with Kprev. You can use this predicate in combination with max_assoc/3 to traverse an assoc. See the notes on get_next_assoc/4.

is_assoc(+Thing)

is true when Thing is a (proper) association tree. If you use the routines in this file, you have no way of constructing a tree with an unbound tip, and the heading of this file explicitly warns against using variables as keys, so such structures are NOT recognised as being association trees. Note that the code relies on variables (to be precise, the first anonymous variable in is_assoc/1) being @< than any non-variable.

list_to_assoc(+List, -Assoc)

is true when List is a proper list of Key-Val pairs (in any order) and Assoc is an association tree specifying the same finite function from Keys to Values. Note that the list should not contain any duplicate keys. In this release, list_to_assoc/2 doesn’t check for duplicate keys, but the association tree which gets built won’t work.

ord_list_to_assoc(+List, -Assoc)

is a version of list_to_assoc/2 which trusts you to have sorted the list already. If you pair up an ordered set with suitable values, calling this instead will save the sort.

map_assoc(:Pred, +Assoc)

is true when Assoc is a proper association tree, and for each Key->Val pair in Assoc, the proposition Pred(Val) is true. Pred must be a closure, and Assoc should be proper. There should be a version of this predicate which passes Key to Pred as well as Val, but there isn’t.

map_assoc(:Pred, ?OldAssoc, ?NewAssoc)

is true when OldAssoc and NewAssoc are association trees of the same shape (at least one of them should be provided as a proper assoc, or map_assoc/3 may not terminate), and for each Key, if Key is associated with Old in OldAssoc and with New in NewAssoc, the proposition Pred(Old,New) is true. Normally we assume that Pred is a function from Old to New, but the code does not require that. There should be a version of this predicate which passes Key to Pred as well as Old and New, but there isn’t. If you’d have a use for it, please tell us.

max_assoc(+Assoc, -Key, -Val)

is true when Key is the largest Key in Assoc, and Val is the associated value. It assumes that Assoc is a proper assoc. This predicate is determinate. If Assoc is empty, it just fails quietly; an empty set can have no largest element!

min_assoc(+Assoc, -Key, -Val)

is true when Key is the smallest Key in Assoc, and Val is the associated value. It assumes that Assoc is a proper assoc. This predicate is determinate. If Assoc is empty, it just fails quietly; an empty set can have no smallest element!

portray_assoc(+Assoc)

writes an association tree to the current output stream in a pretty form so that you can easily see what it is. Note that an association tree written out this way can NOT be read back in. For that, use writeq/1. The point of this predicate is to get association trees displayed nicely by print/1.

put_assoc(+Key, +OldAssoc, +Val, -NewAssoc)

is true when OldAssoc and NewAssoc define the same finite function, except that NewAssoc associates Val with Key. OldAssoc need not have associated any value at all with Key,