View source for Prolog/Associative map

[[Image:Binary search tree.svg|thumb|right|Example binary search tree with integer keys only]]
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 [[:w:Binary search tree|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 <tt>t(Key,Value,LeftChild,RightChild)</tt>. The empty tree will be represented by the atom <tt>nil</tt>.

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

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

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

The implementation of <tt>empty_map</tt> is trivial:

<syntaxhighlight lang="prolog">
empty_map(nil).
</syntaxhighlight>

Our next predicate, <tt>lookup_map</tt>, follows the usual recursion patterns for BST operations:

<syntaxhighlight lang="prolog">
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)
    ).
</syntaxhighlight>

Note the use of <tt>==/2</tt> instead of unification. The reason for doing so lies in the use <tt>@</2</tt> which compares terms according to the ''standard order of terms''. In this ordering, for any two distinct terms <math>T_1</math> and <math>T_2</math>, either <math>T_1</math> <tt>==</tt> <math>T_2</math>, <math>T_1</math> <tt>@&lt;</tt> <math>T_2</math>, or <math>T_2</math> <tt>@&lt;</tt> <math>T_1</math>. For example, <tt>a @< b</tt>, <tt>X @< Y</tt> and <tt>X @< foo</tt>. In fact, a free variable is always <tt>@<</tt> a ground term. But when two variables, or a variable and a ground term are unified, the ordering changes: after <tt>X=Y</tt>, <tt>X==Y</tt> 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 <tt>nil</tt>, since looking up anything in an empty tree will always fail.

[[:w:Binary search tree#Deletion|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 <tt>rm_max</tt> helper predicate to remove the maximum element from a subtree.

<syntaxhighlight lang="prolog">
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).
</syntaxhighlight>

The rest of the predicates are now easy to write:

<syntaxhighlight lang="prolog">
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.
</syntaxhighlight>

''Exercise'': implement <tt>rmember_ordmap</tt> and <tt>update_ordmap</tt>.

==Libraries==
Associative map data structures are built into the libraries of various Prolog implementations (though often not in compatible ways):
* SICStus provides [http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html library(avl)]
* SWI-Prolog provides [https://www.swi-prolog.org/pldoc/man?section=assoc library(assoc)]

Both libraries are based on [[:w:AVL tree|AVL trees]]; note that SICStus also provides a [http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002dassoc.html#lib_002dassoc library(assoc)], but that is based on simple lists.

{{BookCat}}