Next: lib-atts, Previous: lib-aggregate, Up: The Prolog Library [Contents][Index]

`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(`

is that`N`,`Term`,`Element`)`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,

Send feedback on this subject.