Prolog/关联映射

Prolog 的内置列表很方便，但有时简单的线性列表不够用。当您想要维护一组元素（“键”）与另一组元素（“值”）之间的关联时，您需要一个关联映射数据结构。以下是使用二叉搜索树 (BST) 在 Prolog 中实现此类结构的方法。

首先，我们需要一个 Prolog 术语中的搜索树表示形式。请记住，BST 是一棵二叉树，键值对存储在节点中。因此，我们可以将节点表示为谓词t(Key,Value,LeftChild,RightChild). 空树将由原子表示nil.

但我们不想直接对这种表示形式进行编程：通过提供适当的谓词，我们可以指定一个抽象数据结构 (ADT)。这样做的原因是我们以后可以更改我们的实现以使用平衡二叉树或其他更复杂的数据结构。我们将此 ADT 称为有序映射，或ordmap. 以下是 ordmap 上的基本操作

empty_map(-Map): 与Map进行统一，使它成为空映射。
lookup_ordmap(+Key, +Map, -Value): 查找与Value相关联的Key在Map.
insert_ordmap(+Key, +Value, +Map0, -Map): 将对Key, Value插入映射Map0中，产生Map. 注意，之后，两者Map0和Map都是有效的有序映射，它们最多只有一个元素不同。如果Key已经存在于Map0.
update_ordmap(+Key, +Value, +Map0, -Map): 与insert_ordmap类似，但会删除与Key相关联的任何先前值（并始终成功）。
remove_ordmap(+Key, +Map0, -Map, -Value): 从Key中删除Map0中，产生Map. 与Key相关联的值将返回到Value中。如果Key不在Map0.
member_ordmap(+Map, -Key, -Value): 按键顺序回溯Map中的所有键值对。
rmember_ordmap(+Map, -Key, -Value): 按键顺序回溯Map按键的逆序回溯。
size_ordmap(+Map, -Size): 确定Map.

中元素的数量。出于稍后会变得清晰的原因，我们有序映射中的键应始终是接地项。

实现empty_map很简单

empty_map(nil).

我们的下一个谓词lookup_map, 遵循 BST 操作的常用递归模式

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)
    ).

注意使用==/2而不是统一。这样做的原因在于使用了@</2，它根据术语的标准顺序比较术语。在此排序中，对于任意两个不同的术语 $T_{1}$ 和 $T_{2}$ ，要么 $T_{1}$ == $T_{2}$ ， $T_{1}$ @< $T_{2}$ ，或 $T_{2}$ @< $T_{1}$ . 例如，a @< b, X @< Y和X @< foo. 事实上，自由变量始终是@<接地项。但是，当两个变量，或一个变量和一个接地项被统一时，排序会发生变化：在X=Y, X==Y之后也是真的。这就是为什么键原则上始终应该是接地项的原因：这样，排序始终保持（但我们将相应的检查留给我们有序映射数据结构的用户）。请注意，对值没有这种限制，因为它们不需要排序。

还要注意，我们没有针对nil的情况，因为在空树中查找任何东西始终会失败。

从二叉搜索树中删除元素的实现可能有点棘手；以下代码使用其中序前驱替换具有两个子节点的节点，该前驱是左子树中的最大元素。它使用rm_max辅助谓词从子树中删除最大元素。

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).

现在很容易编写其余谓词

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.

练习：实现rmember_ordmap和update_ordmap.

库

关联映射数据结构内置在各种 Prolog 实现的库中（尽管通常方式不兼容）

SICStus 提供了 library(avl)
SWI-Prolog 提供了 library(assoc)

这两个库都基于 AVL 树；请注意，SICStus 还提供了一个 library(assoc)，但它是基于简单列表的。