Prolog的尾遞歸方法來計算列表

未初始化變量我試圖寫一個尾遞歸方法來計算列表中的未初始化變量的數目。我有點卡住了，我哪裏錯了。Prolog的尾遞歸方法來計算列表

我當前的查詢是以下：

count([S,L],N) :- var(S), !, N+1. 
count([L],N).

來源

2011-07-12 General_9

注：這個答案提出了一個解決方案，它是遞歸的，但不是尾遞歸。對於尾遞歸解決方案，您應該使用累加器，這可以從此問題的其他答案中看出。

與任何遞歸過程，你應該添加適當的基本情況。在這種情況下，它應該是與返回與未初始化變量的數目統一0空單的條款：

count([], 0).

檢查你寫的條款。它輸入兩個元素，而不是表現爲頭項和尾單的列表清單，它確實沒有什麼用N：

count([Head|Tail], M):- 
    var(Head), 
    !, 
    count(Tail, N), 
    M is N+1.

最後，你還應該添加一個條款來處理該情況下，當列表的第一個項目是不是一個非實例變量：

count([_|Tail], N):- count(Tail, N).

來源

2011-07-12 19:41:41 gusbro

這不是一個尾遞歸因爲遞歸調用'計數（尾，N）'之後是進一步的目標'M是N + 1'。 – Jiri

@Jini：你是對的！我監督了問題的「尾遞歸」部分，我只是修正了OP代碼。 – gusbro

沒有遞歸在這裏，因爲爲了有遞歸，你必須在本身來定義的東西 - 你會發現代碼右側缺少count/2規則。

% two paths, variable and non-variable 
% and a base case to start the count 
count([S|L], N) :- var(S), !, count(L, N0), N is N0+1. 
count([S|L], N) :- nonvar(S), !, count(L, N). 
count([], 0).

或者，這可以簡單地findall/3完成。

count_alt(L, N) :- findall(S, (member(S, L), var(S)), D), length(D, N).

來源

2011-07-12 20:08:58 Orbling

溶液'計數（...）'是不是一個尾遞歸因爲遞歸調用'計數（L，N0）接着通過'進一步目標'N爲N0 + 1'。 – Jiri

@Jiri：注意到，非常正確。這就是爲什麼我+1你的答案。我認爲這個非累加器版本更簡潔，因爲子句更少。但蓄壓器的版本是大約兩倍的速度（120％較慢 - 我跑一些簡檔）時，'的findall/3'版本比蓄壓器更慢的約50％。 – Orbling

Orbling：非蓄能器無疑是顯而易見的Prolog的解決方案 - 而是一個尾遞歸有人問。感謝您讓我知道您的性能測試和您的投票:)！ – Jiri

這是一個用於計數列表中變量的尾遞歸。它使用累加器技術：

count(L, N) :- count(L, 0, N).  % L=list, N=count, 0=value of the sum accumulator S 
count([], S, S) :- !.    % the innermost call, the accumulator S (2nd arg) "copied" to final result (3rd arg) 
count([H| T], S, N):- var(H), !, S1 is S+1, count(T, S1, N). % increase accumulator if H is var 
count([H| T], S, N):- count(T, S, N). % keep accumulator if H is not var

沒有調用在所有子句中都跟隨最後的遞歸調用。

來源

2011-07-12 20:21:09 Jiri

我在我的非變量規則中包含'nonvar（）'，而你已經離開了它。我認爲這是因爲規則順序總是匹配第一個適合的規則，所以這些規則對我來說是順序敏感的。 'nonvar（）'調用可能會降低速度。 – Orbling

'nonvar（）'調用會減慢速度，如果我們接受規則的順序是不需要的。使用'nonvar（）'不需要剪切。 – Jiri

Prolog的尾遞歸方法來計算列表

回答

相關問題