1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
\libdoc{assoc}{Association lists}
\label{sec:lib:assoc}
\makebox[\linewidth]{\hfill Authors: \emph{Richard A.
O'Keefe, L.Damas, V.S.Costa and Markus Triska}}\vspace{2ex}
\noindent
Elements of an association list have 2 components: A (unique)
\emph{key} and a \emph{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
\pllib{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.
\begin{description}
\predicate{assoc_to_list}{2}{+Assoc, -List}
\arg{List} is a list of Key-Value pairs corresponding to
the associations in \arg{Assoc} in ascending order of keys.
\predicate{assoc_to_keys}{2}{+Assoc, -List}
\arg{List} is a list of Keys corresponding to
the associations in \arg{Assoc} in ascending order.
\predicate{assoc_to_values}{2}{+Assoc, -List}
\arg{List} is a list of Values corresponding to
the associations in \arg{Assoc} in ascending order
of the keys they are associated to.
\predicate{empty_assoc}{1}{?Assoc}
\arg{Assoc} is unified with an empty association list.
\predicate{gen_assoc}{3}{?Key, +Assoc, ?Value}
Enumerate matching elements of \arg{Assoc} in
ascending order of their keys via backtracking.
\predicate{get_assoc}{3}{+Key, +Assoc, ?Value}
\arg{Value} is the value associated with \arg{Key} in the
association list \arg{Assoc}.
\predicate{get_assoc}{5}{+Key, +Assoc, ?Old, ?NewAssoc, ?New}
\arg{NewAssoc} is an association list identical to
\arg{Assoc} except that the value associated with \arg{Key}
is \arg{New} instead of \arg{Old}.
\predicate{list_to_assoc}{2}{+List, -Assoc}
\arg{Assoc} is an association list corresponding to
the Key-Value pairs in \arg{List}. \arg{List} must not
contain duplicate keys.
\predicate{map_assoc}{2}{:Goal, +Assoc}
\arg{Goal(V)} is true for every value V in \arg{Assoc}.
\predicate{map_assoc}{3}{:Goal, +AssocIn, ?AssocOut}
\arg{AssocOut} is \arg{AssocIn} with \arg{Goal} applied
to all corresponding pairs of values.
\predicate{max_assoc}{3}{+Assoc, ?Key, ?Value}
\arg{Key} and \arg{Value} are key and value of the element
with the largest key in \arg{Assoc}.
\predicate{min_assoc}{3}{+Assoc, ?Key, ?Value}
\arg{Key} and \arg{Value} are key and value of the element
with the smallest key in \arg{Assoc}.
\predicate{ord_list_to_assoc}{2}{+List, -Assoc}
\arg{Assoc} is an association list correspond to the Key-Value
pairs in \arg{List}, which must occur in strictly ascending
order of their keys.
\predicate{put_assoc}{4}{+Key, +Assoc, +Value, ?NewAssoc}
\arg{NewAssoc} is an association list identical to
\arg{Assoc} except that \arg{Key} is associated with
\arg{Value}. This can be used to insert and change
associations.
\predicate{is_assoc}{1}{+Assoc}
True if Assoc is a valid association list. This
predicate verifies the validity of each node in the AVL
tree.
\end{description}
%end-of-file
|
