Prolog合併兩個列表

Question

我需要在Prolog中合併兩個列表。輸入時應該是謂詞merge/3。

應該像這樣：

?- merge([6,4,b,8], [5,b,s,6], X). 
X = [6, 4, b, 8, 5, s]. 

我曾嘗試：

%rules 
merge(A, B, X):- 
    merge(A, B, B, X). 

merge([], X, _, X). 
merge([Head|L1], [Head|L2], Tmp, [Head|X]) :- 
    merge(L1, L2, Tmp, X), 
    !. 
merge(L1, [_|L2], Tmp, X) :- 
    merge(L1, L2, Tmp, X), 
    !. 
merge([A|L1], [], Tmp, [A|X]) :- 
    merge(L1, Tmp, Tmp, X), 
    !. 

我得到什麼：

?- merge([1,2,a,3], [5,d,a,1], X). 
X = [1, 2, a, 3, 5, d, a, 1]. 

我期待什麼：

?- merge([1,2,a,3], [5,d,a,1], X). 
X = [1, 2, a, 3, 5, d]. 

Answer 1

這可以通過重寫內置謂詞來完成！ e.g：

my_append([], R, R) . 
my_append([H|T], R1, [H|R2]) :- 
    my_append(T, R1, R2). 


my_member(H, [H|_]). 
my_member(H, [_|T]) :- 
    my_member(H, T). 

所以，我可以說，用一個空表合併L，使得這個列表L

merge(L, [], L). 

現在，合併兩個列表，看看我的第二個列表的第一個元素。

如果它在第一個列表中，我忽略它，我將第一個列表和第二個列表合併。

如果不是，我將第一個元素添加到第一個列表的末尾，並將新的第一個列表與第二個列表的剩餘部分合並。我不得不說，它不是非常有效率！

merge(L, [H| T], R) :- 
    ( my_member(H, L) 
    -> merge(L, T, R) 
    ; my_append(L, [H], L1), 
     merge(L1, T, R)). 

Answer 2

如果元素的順序並不某種程度上取決於兩個輸入列表的順序上，這是一個習慣的Prolog解決方案：

?- append([6,4,b,8], [5,b,s,6], A), sort(A, B). 
A = [6, 4, b, 8, 5, b, s, 6], 
B = [4, 5, 6, 8, b, s]. 

如果順序很重要，你需要解釋如何。

還有一些關於你顯示的代碼的評論。您爲謂詞選擇的名稱：「連接」和「合併」都具有明確的含義與您似乎試圖實現的不同（在關係數據庫中爲「join」，「merge」爲「合併兩個有序列表「）。你正在做的是一個"union"（順便說一下，點擊這個鏈接並閱讀代碼！）。

此外，它幾乎總是一個錯誤（不是錯誤，而是錯誤）作爲子句體的最後一個子目標。有一個謂詞的多個子句並不明顯相互排斥（作爲merge/4的4個子句中的最後3個）通常是一個設計缺陷（而不是錯誤）。