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
|
## Introduction {#assoc-introduction}
An _association list_ as implemented by this library is a collection
of unique _keys_ that are associated to _values_. Keys must 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.
This library uses **AVL trees** to implement association lists. This means that
- inserting a key
- changing an association
- fetching a single element
are all _O(log(N))_ _worst-case_ (and expected) time operations, where
_N_ denotes the number of elements in the association list.
The logarithmic overhead is often acceptable in practice. Notable
advantages of association lists over several other methods are:
- `library(assoc)` is written entirely in Prolog, making it portable to
other systems
- the interface predicates fit the declarative nature of Prolog, avoiding
destructive updates to terms
- AVL trees scale very predictably and can be used to represent sparse arrays
efficiently.
## Creating association lists {#assoc-creation}
An association list is _created_ with one of the following predicates:
* [[empty_assoc/1]]
* [[list_to_assoc/2]]
* [[ord_list_to_assoc/2]]
## Querying association lists {#assoc-querying}
An association list can be _queried_ with:
* [[get_assoc/3]]
* [[get_assoc/5]]
* [[max_assoc/3]]
* [[min_assoc/3]]
* [[gen_assoc/3]]
## Modifying association lists {#assoc-modifications}
Elements of an association list can be changed and inserted with:
* [[put_assoc/4]]
* [[del_assoc/4]]
* [[del_min_assoc/4]]
* [[del_max_assoc/4]]
## Conversion predicates {#assoc-conversion}
Conversion of (parts of) an association list to _lists_ is possible
with:
* [[assoc_to_list/2]]
* [[assoc_to_keys/2]]
* [[assoc_to_values/2]]
## Reasoning about association lists and their elements {#assoc-reasoning}
Further inspection predicates of an association list and its elements
are:
* [[is_assoc/1]]
* [[map_assoc/2]]
* [[map_assoc/3]]
|
