尺寸過程語言

Question

我是新來的Prolog，當它涉及到遞歸算法是不是偉大的，因爲是，所以我很困惑與以下兩個條款：

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

我無法追查這問題爲：

?- size([a,b,c,d], N). 

這將與第二條統一到形式：

size([a,b,c,d], N) :- size([b,c,d], N1), N is N1+1. 

但我與N混淆是因爲N1+1這些變量永遠不會統一。這些變量的值是什麼？

任何關於這個問題，或者這個算法的一個簡單的跟蹤幫助，將不勝感激。

Answer 1

N爲N1 + 1，因爲這些變量從不統一。

我認爲你的意思是說他們永遠不會實例化，即他們永遠不會獲得價值。統一兩個變量可以實例化它們，但不是必需的。例如，你可以在一個序言REPL運行此：

?- N = N1. 
N = N1. 

而N和N1沒有任何價值（還），他們都是統一;如果N1稍後被實例化，則N將被實例化爲具有相同的值。另一個不那麼瑣碎，例如：

?- [H|T] = L, L = [1|M], writeln(H). 
1 
H = 1, 
T = M, 
L = [1|M]. 

但是，這是事實，N不會與N1+1統一！ is將評估N1+1和這值將與N統一。後內size([b,c,d],N1)進行了評估，因此N1變量將被實例會發生這種情況。

從本質上講，執行將是這樣的：

size([a,b,c,d],N). 
      size([b,c,d],N1) 
       size([c,d],N1) 
        size([d],N1) 
         size([],0) 
         N is 0+1. 
        N is 1+1. 
       N is 2+1. 
      N is 3+1. 

這是一個有點低效的，因爲我們需要保留所有的函數調用內存;看看尾部遞歸和累加器來解決這個問題。

還要注意的是N1需要，只是因爲is是要計算表達式被實例化。你可以寫這樣的事情：

size([],0). 
size([_|T], 1+ N1):-size(T,N1). 

，如果你把它叫做：

?- size([1,2],N). 
N = 0+1+1. 

樂趣，不是嗎？您可能需要評估最後一個N，例如將其稱爲size([1,2],N), Result is N。但是，一個問題是，我們在內存中保留了一個可以變得非常快的0+1+1+1+1+......鏈。所以最好將這個技巧用於不會增長的事物，例如表達模板。