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(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
recognized 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,