Prolog遞歸追加列表

Question

下面是遞歸添加元素X到列表末尾的代碼。

app(X, [], [X]). 
app(X, [Y | S], [Y | S2]) :- app(X, S, S2). 

任何人都可以解釋我是如何工作的？退貨聲明在哪裏，究竟是什麼app(X, S, S2)[Y | S], [Y | S2]？

Answer 1

你不需要return語句都被統一（簡單模式匹配）來完成。子句：

app(X, [Y | S], [Y | S2]) 

指出第二個參數是頭部Y和尾部S的列表，第三個參數是頭部Y和尾部S2的列表。所以它強制（通過使用統一）兩個列表的頭部是一樣的。遞歸地，除了第三個參數列表在結尾處有一個元素（元素X）並且由第一個子句定義的事實之外，這兩個列表變得完全相同。請注意，第二個子句僅適用於具有一個或多個元素的列表。所以，當我們檢查空列表（第二個參數）遞歸然後榜第三的是由於第一條基本只包含一個多元素的元素X.

Answer 2

Prolog的程序被定義的事實和規則作出。您可以定義事實和規則，Prolog解釋器會嘗試提出解決方案以使其成爲現實。除了這個基本概念，您還需要了解Prolog程序員廣泛使用的另外兩個重要概念。 這些是：

1. 輸入和輸出參數：在Prolog中沒有返回語句。一些變量將會是結果（輸出），而另一些則是輸入。在你的程序中，第一個和第二個參數是輸入的，最後一個是輸出。
2. 模式匹配：如果列表表示爲[Head|Tail]。 Head是第一個元素，Tail是剩餘元素的列表。

當你調用app，例如，作爲app(5, [1, 2, 3, 4], L).，Prolog的解釋試圖拿出值L這樣app是真實的。

Prolog的解釋是解決問題的步驟如下：

1. 爲了使app(X, [Y | S], [Y | S2])真正的，最後一個參數的第一個元素需要變得Y。所以，在我的例子中，L變成[1，S2]。
2. 然後它會嘗試匹配規則app(X, S, S2)。這裏S是[2,3,4]，S2是下一次運行的輸出參數。然後第1步重複，但app(5, [2, 3, 4], S2)和S2後變成[2，S2]。因此，L現在變成[1,2，S2]。
3. 同樣的事情會重複（遞歸），並且L被填充爲[1,2,3,4，S2]。
4. 現在，第二個參數是空的。所以，第一個事實app(X, [], [X])是匹配的。爲了做到這一點，最後一個參數變成一個只包含X（在這種情況下爲5）的列表，其結果是L爲[1,2,3,4,5]。