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)，但它是基於簡單列表的。