Go to the previous, next section.

Association Lists

In this package, finite mappings ("association lists") are represented by AVL trees, i.e. they are subject to the Adelson-Velskii-Landis balance criterion:

A tree is balanced iff for every node the heights of its two subtrees differ by at most 1.

The empty tree is represented as t. A tree with key K, value V, and left and right subtrees L and R is represented as t(K,V,|R|-|L|,L,R), where |T| denotes the height of T.

The advantage of this representation is that lookup, insertion and deletion all become--in the worst case---O(log n) operations.

The algorithms are from [Wirth 76], section 4.4.6--4.4.8.

To load the package, enter the query

| ?- use_module(library(assoc)).

@

Assoc is an empty AVL tree.

@

List is a list of Key-Value pairs in ascending order with no duplicate Keys specifying the same finite function as the association tree Assoc. Use this to convert an association tree to a list.

@

Assoc is a (proper) AVL tree. It checks both that the keys are in ascending order and that Assoc is properly balanced.

@

Key is the smallest key in Assoc and Val is its value.

@

Key is the greatest key in Assoc and Val is its value.

@

Key is associated with Value in the association tree Assoc. Can be used to enumerate all Values by ascending Keys.

@

Key is identical (==) to one of the keys in the association tree Assoc, and Value unifies with the associated value.

@

OldAssoc and NewAssoc are association trees of the same shape having the same elements except that the value for Key in OldAssoc is OldValue and the value for Key in NewAssoc is NewValue.

@

Knext and Vnext is the next key and associated value after Key in Assoc.

@

Kprev and Vprev is the previous key and associated value after Key in Assoc.

@

List is a proper list of Key-Value pairs (in any order) and Assoc is an association tree specifying the same finite function from Keys to Values.

@

List is a proper list of Key-Value pairs (keysorted) and Assoc is an association tree specifying the same finite function from Keys to Values.

@

OldAssoc and NewAssoc are association trees of the same shape, and for each Key, if Key is associated with Value in Assoc, Pred(Value) is true.

@

OldAssoc and NewAssoc are association trees of the same shape, and for each Key, if Key is associated with Old in OldAssoc and with New in NewAssoc, Pred(Old,New) is true.

@

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.

@

OldAssoc and NewAssoc define the same finite function except that OldAssoc associates Key with Val and NewAssoc doesn't associate Key with any value.

@

OldAssoc and NewAssoc define the same finite function except that OldAssoc associates Key with Val and NewAssoc doesn't associate Key with any value and Key precedes all other keys in OldAssoc.

@

OldAssoc and NewAssoc define the same finite function except that OldAssoc associates Key with Val and NewAssoc doesn't associate Key with any value and Key is preceded by all other keys in OldAssoc.

Go to the previous, next section.