- Documentation
- Reference manual
- The SWI-Prolog library
- library(aggregate): Aggregation operators on backtrackable predicates
- library(apply): Apply predicates on a list
- library(assoc): Association lists
- library(broadcast): Broadcast and receive event notifications
- library(charsio): I/O on Lists of Character Codes
- library(check): Consistency checking
- library(clpb): CLP(B): Constraint Logic Programming over Boolean Variables
- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains
- library(clpqr): Constraint Logic Programming over Rationals and Reals
- library(csv): Process CSV (Comma-Separated Values) data
- library(debug): Print debug messages and test assertions
- library(error): Error generating support
- library(gensym): Generate unique identifiers
- library(iostream): Utilities to deal with streams
- library(lists): List Manipulation
- library(main): Provide entry point for scripts
- library(nb_set): Non-backtrackable set
- library(www_browser): Activating your Web-browser
- library(option): Option list processing
- library(optparse): command line parsing
- library(ordsets): Ordered set manipulation
- library(pairs): Operations on key-value lists
- library(persistency): Provide persistent dynamic predicates
- library(pio): Pure I/O
- library(predicate_options): Declare option-processing of predicates
- library(prolog_pack): A package manager for Prolog
- library(prolog_xref): Cross-reference data collection library
- library(quasi_quotations): Define Quasi Quotation syntax
- library(random): Random numbers
- library(readutil): Reading lines, streams and files
- library(record): Access named fields in a term
- library(registry): Manipulating the Windows registry
- library(simplex): Solve linear programming problems
- library(solution_sequences): Modify solution sequences
- library(tabling): Tabled execution (SLG)
- library(thread_pool): Resource bounded thread management
- library(ugraphs): Unweighted Graphs
- library(url): Analysing and constructing URL
- library(varnumbers): Utilities for numbered terms
- library(yall): Lambda expressions

- The SWI-Prolog library
- Packages

- Reference manual

## A.3 library(assoc): Association lists

Authors: *Richard A. O'Keefe, L.Damas, V.S.Costa and Markus
Triska*

### A.3.1 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.

### A.3.2 Creating association lists

An assocation list is *created* with one of the following
predicates:

- [semidet]
**empty_assoc**(`?Assoc`) - Is true if
`Assoc`is the empty association list. - [det]
**list_to_assoc**(`+Pairs, -Assoc`) - Create an association from a list
`Pairs`of Key-Value pairs. List must not contain duplicate keys.- Errors
`domain_error(unique_key_pairs, List)`

if List contains duplicate keys

- [det]
**ord_list_to_assoc**(`+Pairs, -Assoc`) `Assoc`is created from an ordered list`Pairs`of Key-Value pairs. The pairs must occur in strictly ascending order of their keys.- Errors
`domain_error(key_ordered_pairs, List)`

if pairs are not ordered.

### A.3.3 Querying association lists

An association list can be *queried* with:

- [semidet]
**get_assoc**(`+Key, +Assoc, -Value`) - True if
`Key`-`Value`is an association in`Assoc`.- Errors
`type_error(assoc, Assoc)`

if`Assoc`is not an association list.

- [semidet]
**get_assoc**(`+Key, +Assoc0, ?Val0, ?Assoc, ?Val`) - True if
`Key`-`Val0`is in`Assoc0`and`Key`-`Val`is in`Assoc`. - [semidet]
**max_assoc**(`+Assoc, -Key, -Value`) - True if
`Key`-`Value`is in`Assoc`and`Key`is the largest key. - [semidet]
**min_assoc**(`+Assoc, -Key, -Value`) - True if
`Key`-`Value`is in assoc and`Key`is the smallest key. - [nondet]
**gen_assoc**(`?Key, +Assoc, ?Value`) - True if
`Key`-`Value`is an association in`Assoc`. Enumerates keys in ascending order on backtracking.- See also
- get_assoc/3.

### A.3.4 Modifying association lists

Elements of an association list can be changed and inserted with:

- [det]
**put_assoc**(`+Key, +Assoc0, +Value, -Assoc`) `Assoc`is`Assoc0`, except that`Key`is associated with`Value`. This can be used to insert and change associations.- [semidet]
**del_assoc**(`+Key, +Assoc0, ?Value, -Assoc`) - True if
`Key`-`Value`is in`Assoc0`.`Assoc`is`Assoc0`with`Key`-`Value`removed. - [semidet]
**del_min_assoc**(`+Assoc0, ?Key, ?Val, -Assoc`) - True if
`Key`-Value is in`Assoc0`and`Key`is the smallest key.`Assoc`is`Assoc0`with`Key`-Value removed. Warning: This will succeed with*no*bindings for`Key`or`Val`if`Assoc0`is empty. - [semidet]
**del_max_assoc**(`+Assoc0, ?Key, ?Val, -Assoc`) - True if
`Key`-Value is in`Assoc0`and`Key`is the greatest key.`Assoc`is`Assoc0`with`Key`-Value removed. Warning: This will succeed with*no*bindings for`Key`or`Val`if`Assoc0`is empty.

### A.3.5 Conversion predicates

Conversion of (parts of) an association list to *lists* is
possible with:

- [det]
**assoc_to_list**(`+Assoc, -Pairs`) - Translate
`Assoc`to a list`Pairs`of Key-Value pairs. The keys in`Pairs`are sorted in ascending order. - [det]
**assoc_to_keys**(`+Assoc, -Keys`) - True if
`Keys`is the list of keys in`Assoc`. The keys are sorted in ascending order. - [det]
**assoc_to_values**(`+Assoc, -Values`) - True if
`Values`is the list of values in`Assoc`.`Values`are ordered in ascending order of the key to which they were associated.`Values`may contain duplicates.

### A.3.6 Reasoning about association lists and their elements

Further inspection predicates of an association list and its elements are:

- [semidet]
**is_assoc**(`+Assoc`) - True if
`Assoc`is an association list. This predicate checks that the structure is valid, elements are in order, and tree is balanced to the extent guaranteed by AVL trees. I.e., branches of each subtree differ in depth by at most 1. - [semidet]
**map_assoc**(`:Pred, +Assoc`) - True if
`Pred`(Value) is true for all values in`Assoc`. - [semidet]
**map_assoc**(`:Pred, +Assoc0, ?Assoc`) - Map corresponding values. True if
`Assoc`is`Assoc0`with`Pred`applied to all corresponding pairs of of values.