- Documentation
- Reference manual
- The SWI-Prolog library
- library(aggregate): Aggregation operators on backtrackable predicates
- library(ansi_term): Print decorated text to ANSI consoles
- 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(dcg/basics): Various general DCG utilities
- library(dcg/high_order): High order grammar operations
- library(debug): Print debug messages and test assertions
- library(dicts): Dict utilities
- library(error): Error generating support
- library(fastrw): Fast reading and writing of terms
- library(gensym): Generate unique symbols
- library(heaps): heaps/priority queues
- library(increval): Incremental dynamic predicate modification
- library(intercept): Intercept and signal interface
- library(iostream): Utilities to deal with streams
- library(listing): List programs and pretty print clauses
- library(lists): List Manipulation
- library(macros): Macro expansion
- library(main): Provide entry point for scripts
- library(nb_set): Non-backtrackable set
- library(www_browser): Open a URL in the users browser
- library(occurs): Finding and counting sub-terms
- 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(portray_text): Portray text
- library(predicate_options): Declare option-processing of predicates
- library(prolog_coverage): Coverage analysis tool
- library(prolog_debug): User level debugging tools
- library(prolog_jiti): Just In Time Indexing (JITI) utilities
- library(prolog_trace): Print access to predicates
- library(prolog_versions): Demand specific (Prolog) versions
- library(prolog_xref): Prolog cross-referencer data collection
- library(quasi_quotations): Define Quasi Quotation syntax
- library(random): Random numbers
- library(rbtrees): Red black trees
- library(readutil): Read utilities
- library(record): Access named fields in a term
- library(registry): Manipulating the Windows registry
- library(rwlocks): Read/write locks
- library(settings): Setting management
- library(statistics): Get information about resource usage
- library(strings): String utilities
- library(simplex): Solve linear programming problems
- library(solution_sequences): Modify solution sequences
- library(tables): XSB interface to tables
- library(terms): Term manipulation
- library(thread): High level thread primitives
- library(thread_pool): Resource bounded thread management
- library(ugraphs): Graph manipulation library
- library(url): Analysing and constructing URL
- library(varnumbers): Utilities for numbered terms
- library(yall): Lambda expressions
- The SWI-Prolog library
- Packages
- Reference manual
A.4 library(assoc): Association lists
Authors: Richard A. O'Keefe, L.Damas, V.S.Costa and Markus Triska
A.4.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.4.2 Creating association lists
An association 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.4.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.
- [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.4.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.4.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.4.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. Does not validate that keys are sufficiently instantiated to ensure the tree remains valid if a key is further instantiated.
- [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.