9.10.3 Association List Primitives

These predicates implement “association list” primitives. They use a binary tree representation. Thus the time complexity for these predicates is O(lg N), where N is the number of keys. These predicates also illustrate the use of compare/3 for case analysis.

The goal get_assoc(Key, Assoc, Value) is true when Key is identical to one of the keys in Assoc, and Value unifies with the associated value.

     get_assoc(Key, t(K,V,L,R), Val) :-
             compare(Rel, Key, K),
             get_assoc(Rel, Key, V, L, R, Val).
     
     get_assoc(=, _, Val, _, _, Val).
     get_assoc(<, Key, _, Tree, _, Val) :-
             get_assoc(Key, Tree, Val).
     get_assoc(>, Key, _, _, Tree, Val) :-
             get_assoc(Key, Tree, Val).