Prolog中的列表長度

我是Prolog編程的初學者。我編寫了這個程序來計算列表的長度。爲什麼下面的程序錯了？Prolog中的列表長度

length(0, []). 
length(L+l, H|T) :- length(L, T).

我寫下面的程序，它工作正常。

length([], 0). 
length([H|T], N) :- length(T, N1), N is N1+1.

當我改變了順序，我得到了一個錯誤。爲什麼？

length([], 0). 
length([H|T], N) :- N is N1+1, length(T, N1).

來源

2013-10-07 Fery

這個代碼

length_1(0,[]). 
length_1(L+1, [H|T]) :- length_1(L,T).

工程（注意添加的方括號），但意想不到的方式。它將構建一個表達式樹，這可能是後來評價：

?- length_1(X, [1,2,3]), L is X. 
X = 0+1+1+1, 
L = 3.

在你重寫代碼（第二版），你會得到一個錯誤，因爲N1還沒有在調用時實例爲/ 2。

來源

2013-10-07 17:19:14 CapelliC

正如卡羅的回答暗示，L+1是Prolog項有兩個參數，L和1，其仿函數是+。 Prolog不是一種功能性語言，因此您無法輸入L+1，並期望對它進行評估。嘗試遵循卡羅的建議並使用謂詞來強制進行算術評估。例如，調用目標X is 3 + 4將評估右操作數，並嘗試將結果與左操作數統一。如果左操作數X是一個變量，它將與7統一。還要注意的是，在Prolog中，變量是單個賦值（但是如果賦值的術語包含變量，則可以進一步實例化）。即你只能給變量分配一個詞。當您完成作業的目標回溯時，此作業會被撤消。

來源

2013-10-07 18:21:26

您需要使用累加器。雖然你可以做這樣的事情：

list_length([]  , 0). 
list_length([_|Xs] , L) :- list_length(Xs,N) , L is N+1 .

這將遞歸一路下跌到列表的末尾，然後，因爲每個調用返回，添加一個長度，直到它回來到頂級以正確的結果。

這種方法的問題是每次遞歸都會在堆棧上推送一個新的堆棧幀。這意味着，如果給出足夠長的列表，您將[最終]耗盡堆棧空間。

相反，使用尾遞歸中介，像這樣：

list_length(Xs,L) :- list_length(Xs,0,L) . 

list_length([]  , L , L) . 
list_length([_|Xs] , T , L) :- 
    T1 is T+1 , 
    list_length(Xs,T1,L) 
    .

此代碼種子工人謂詞攜帶一個累加器，以0接種在每一遞歸它創建一個新累加器，其值是當前值+1。到達列表末尾時，累加器的值與所需結果統一。

prolog引擎足夠智能（TRO /尾遞歸優化）看到它可以在每次調用時重用堆棧幀（因爲遞歸調用後沒有使用局部變量），因此整齊地將遞歸轉換爲迭代。

來源

2013-10-07 20:28:57

len([], LenResult):- 
    LenResult is 0. 

len([X|Y], LenResult):- 
    len(Y, L), 
    LenResult is L + 1.

來源

2016-05-13 11:10:42 garciparedes

儘管這段代碼可以回答這個問題，提供附加的上下文有關_why_和/或_how_它回答問題將顯著改善其長期值。請[編輯]你的答案，添加一些解釋。 –

Prolog中的列表長度

回答

相關問題