序言列表和遞歸

Question

我在理解Prolog中的設計遞歸時遇到了問題。

一些輔助謂詞只是附加到開始分別結束：

add_number(Numbers, N, NewNumbers). 
add_letter(Letters, L, NewLetters). 

我的目標是把字母和數字列表，並返回兩個名單：號碼列表中出現的順序，遞增減1;和出現相反順序的字母表。這裏是我的推理：

foo([], [], [], [], []). 

foo([X|Xs], Nums, NewNums, Letters, Letters) :- 
    number(X), 
    X1 is X+1, 
    add_number(Nums, X1, NewNums), 
    foo(Xs, ???, ???, Letters, Letters). 

foo([X|Xs], Nums, Nums, Letters, NewLetters) :- 
    letter(X), 
    add_letter(Letters, X, NewLetters), 
    foo(Xs, Nums, Nums, ???, ???). 

第二個和第四個參數是蓄電池。

然後，它應該叫這樣的：

realfoo(Xs, Nums, Letters) :- foo(Xs, [], Nums, [], Letters). 

我怎樣寫代碼？

Answer 1

使用累加器以相反的順序建立列表。不要使用add_number或者你會得到一個二次時間算法，而你可以在線性時間內解決這個問題。

foo([], NumsR, Nums, Letters, Letters) :- 
    reverse(NumsR, Nums). 
foo([X|Xs], NumsR, Nums, LettersR, Letters) :- 
    % the following is the Prolog syntax for if-then-else; 
    % you could also do this with two recursive clauses, 
    % but this option is faster because of first-argument indexing 
    (number(X) -> 
     X1 is X+1, 
     foo(Xs, [X1|NumsR], Nums, LettersR, Letters) 
    ; 
     foo(Xs, NumsR, Nums, [X|LettersR], Letters) 
    ). 

Answer 2

foo（[]，Nums，Nums，Letters，Letters）。

FOO（[X |兩個X]，Nums_1，訂購數量，Letters_1，書信）： - 數（X）， X1是X + 1， add_number（Nums_1，X1，Nums_2） FOO（XS， Nums_2，Nums，Letters_1，Letters）。

FOO（[X |兩個X]，Nums_1，訂購數量，Letters_1，書信）： - 字母（X）， add_letter（Letters_1，X，Letters_2） FOO（XS，Nums_1，訂購數量，Letters_2，信件）。

add_number（Nums_1，X，Nums_2）： - append（Numbs_1，[X]，nums_2）。 （Letters_1，X，Letters_2）： - append（Letters_1，[X]，Letters_2）。

Answer 3

我會做這樣的事情：

foo(List , Numbers , Letters) :- 
    worker(List , [] , Numbers , [] , Letters). 

worker([]  , Numbers   , Numbers , Letters   , Letters). 
worker([X|Xs] , NumberAccumulator , Numbers , LetterAccumulator , Letters) :- 
    digit(X), 
    X1 is X+1 , 
    append(NumberAccumulator , [X1] , NumberAccumulator1) , 
    worker(Xs , NumberAccumulator1 , Numbers , LetterAccumulator , Letters). 
worker([X|Xs] , NumberAccumulator , Numbers , LetterAccumulator , Letters) :- 
    letter(X) , 
    worker(Xs , NumberAccumulator , Numbers , [X|LetterAccumulator] , Letters). 
worker([X|Xs] , NumberAccumulator , Numbers , LetterAccumulator , Letters) :- 
    not letter(X) , 
    not digit(X) , 
    worker(Xs , NumberAccumulator , Numbers , LetterAccumulator , Letters). 

letter(a). letter(b). letter(c). ... letter(z). 
letter('A'). letter('B'). letter('C'). ... letter('Z'). 

digit('0'). digit('1'). digit('2'). ... digit('9'). 

由於這是一個學習鍛鍊，我不推遲列表的逆轉：我會做明顯的，並建立在反向列表序列，儘管性能受到影響。我相信練習的要點是你需要學習如何構建列表。