Prolog/Associative map

Prolog's built-in lists are handy, but sometimes a simple linear list is not enough. When you want to maintain an association between one set of elements ('keys') and another ('values'), you need an associative map data structure. Here's how such a structure can be implemented in Prolog using binary search trees (BSTs).

First we need a representation of search trees in Prolog terms. Remember that a BST is a binary tree with key-value pairs stored in the nodes. We can thus represent nodes as functors t(Key,Value,LeftChild,RightChild). The empty tree will be represented by the atom nil.

But we don't want to program to this representation directly: by providing the appropriate predicates, we can specify an abstract data structure (ADT). The reason for doing so is that we can later change our implementation to use balanced binary trees or some other more sophisticated data structure. We shall call this ADT the ordered map, or ordmap. Here are the basic operations on an ordmap:

empty_map(-Map): unifies Map with the empty map.
lookup_ordmap(+Key, +Map, -Value): lookup the Value associated with Key in Map.
insert_ordmap(+Key, +Value, +Map0, -Map): insert the pair Key, Value in the map Map0, yielding Map. Note that afterwards, both Map0 and Map are valid ordered maps, which differ by at most one element. This predicate fails if Key is already present in Map0.
update_ordmap(+Key, +Value, +Map0, -Map): like insert_ordmap, but removes any previous association of Key with a different value (and always succeeds).
remove_ordmap(+Key, +Map0, -Map, -Value): remove Key from Map0, yielding Map. The value associated with Key is returned in Value. This predicate fails if Key was not in Map0.
member_ordmap(+Map, -Key, -Value): backtracks over all key/value pairs in Map by order of keys.
rmember_ordmap(+Map, -Key, -Value): backtracks over all key/value pairs in Map by reverse order of keys.
size_ordmap(+Map, -Size): determines the number of elements in Map.

For reasons that will become clear later on, keys in our ordered maps should always be ground terms.

The implementation of empty_map is trivial:

empty_map(nil).

Our next predicate, lookup_map, follows the usual recursion patterns for BST operations:

lookup_ordmap(K, t(X,Y,L,R), V) :-
    (K == X ->
        V = Y
    ; K @< X ->
        lookup_ordmap(K,L,V)
    ;
        lookup_ordmap(K,R,V)
    ).

Note the use of ==/2 instead of unification. The reason for doing so lies in the use @</2 which compares terms according to the standard order of terms. In this ordering, for any two distinct terms $T_{1}$ and $T_{2}$ , either $T_{1}$ == $T_{2}$ , $T_{1}$ @< $T_{2}$ , or $T_{2}$ @< $T_{1}$ . For example, a @< b, X @< Y and X @< foo. In fact, a free variable is always @< a ground term. But when two variables, or a variable and a ground term are unified, the ordering changes: after X=Y, X==Y is also true. This is why keys should, in principle, always be ground terms: that way, the ordering is always preserved (but we leave the appropriate check up to the user of our ordered map data structure). Note that there is no such restriction on values, since they don't need to be ordered.

Also note that we have no case for nil, since looking up anything in an empty tree will always fail.

Deletion of an element from a binary search tree can be a bit tricky to implement; the following code replaces a node with two children by its in-order predecessor, which is the maximum element of the left subtree. It uses the rm_max helper predicate to remove the maximum element from a subtree.

remove_ordmap(K, t(X,Y,L0,R), t(X,Y,L,R), V) :-
    K @< X,
    remove_ordmap(K,L0,L,V).
remove_ordmap(K, t(X,Y,L,R0), t(X,Y,L,R), V) :-
    K @> X,
    remove_ordmap(K,R0,R,V).
remove_ordmap(K, t(X,V,L,R), T, V) :-
    K == X,
    (L == nil ->
        T = R
    ; R == nil ->
        T = L
    ;
        rm_max(L,L1,K1,V1),
        T = t(K1,V1,L1,R)
    ).
rm_max(t(K,V,L,nil), L, K, V) :- !.
rm_max(t(X,Y,L,R0), t(X,Y,L,R), K, V) :-
    rm_max(R0,R,K,V).

The rest of the predicates are now easy to write:

insert_ordmap(K, V, nil, t(K,V,nil,nil)).
insert_ordmap(K, V, t(X,Y,L0,R), t(X,Y,L,R)) :-
    K @< X,
    insert_ordmap(K,V,L0,L).
insert_ordmap(K, V, t(X,Y,L,R0), t(X,Y,L,R)) :-
    K @> X,
    insert_ordmap(K,V,R0,R).

member_ordmap(t(X,Y,L,R), K, V) :-
    member_ordmap(L,K,V) ;
    (X=K, Y=V) ;
    member_ordmap(R,K,V).

size_ordmap(nil, 0).
size_ordmap(t(_,_,L,R), N) :-
    size_ordmap(L,NL),
    size_ordmap(R,NR),
    N is NL+NR+1.

Exercise: implement rmember_ordmap and update_ordmap.

Libraries

Associative map data structures are built into the libraries of various Prolog implementations (though often not in compatible ways):

SICStus provides library(avl)
SWI-Prolog provides library(assoc)

Both libraries are based on AVL trees; note that SICStus also provides a library(assoc), but that is based on simple lists.