SWI-Prolog中的交集

Question

我是Prolog的新手，我對理解遞歸有點麻煩。我正在嘗試編寫一個關係式，它可以在不使用SWI的內置交叉點的情況下查找兩個排序列表的交集。我使用trace來查看發生了什麼，它的行爲與我期望的一樣，直到我希望它終止並返回包含交集的新列表。這讓我認爲我的基本情況是錯誤的。我用幾種不同的方式來構建基本案例，但它並沒有取得豐碩成果。我一直使用列表[1,2,3,4和[2,4,6]作爲測試用例，它們具有以下關係（頂部的基本情況只是我作爲佔位符投入的一個...它根本不起作用）：

intersectS([], [], []). 
intersectS([A | B], [C | D], Z) :- A < C, intersectS(B, [C | D], Z). 
intersectS([A | B], [C | D], Z) :- A > C, intersectS([A | B], D, Z). 
intersectS([A | B], [C | D], Z) :- A = C, append(Z, [A], Y), intersectS(B, D, Y). 

任何幫助表示讚賞。我已經看到了切割（！）操作符與成員/非成員一起使用的示例，但我應該利用列表已排序的事實，所以我認爲我會嘗試這種方法。提前致謝。

Answer 1

總體而言，你有解決的辦法是中途有（如你觀察到的）。我認爲有兩個方面需要解決。正如你所指出的那樣，一個是「基本案例」。我會這樣做：

intersectS([], _, []). 
intersectS(_, [], []). 

換句話說，任何與空列表相交的東西都是空的。

第二個問題點是A = C的子句。您有：

intersectS([A | B], [C | D], Z) :- A = C, append(Z, [A], Y), intersectS(B, D, Y). 

這表示，如果兩個列表的頭相匹配，然後用[A]（匹配頭）附加的交點（Z）是兩個列表的尾部的交集。這看起來不正確。我想你想說的交點（Z）是附加到[A]尾部B和D的交集，就像這樣：

intersectS([A | B], [C | D], Z) :- A = C, append([A], Y, Z), intersectS(B, D, Y). 

所以整個事情是這樣的：

intersectS([], _, []). 
intersectS(_, [], []). 
intersectS([A | B], [C | D], Z) :- A < C, intersectS(B, [C | D], Z). 
intersectS([A | B], [C | D], Z) :- A > C, intersectS([A | B], D, Z). 
intersectS([A | B], [C | D], Z) :- A = C, append([A], Y, Z), intersectS(B, D, Y). 

您可以更進一步，擺脫append，因爲您只是處理一個元素。 append([A], Y, Z)與Z = [A|Y]相同。所以，你可以簡單地取代最後一句：

intersectS([A | B], [C | D], [A | Y]) :- A = C, intersectS(B, D, Y). 

運行測試案例：

?- intersectS([1, 2, 3, 4], [2,4,6], L). 
L = [2, 4] ; 
false. 

?-