Prolog - 計算旅行的總時間

Question

我試圖計算出所有地方的出發時間和到達時間，我花在旅行上的總時間。

我想要使用此功能只計算到時候我會等待下一次運輸：

time_out([(_,Hf1),(Hi2,Hf2)|R],To):- 
    diff_t(Hi2,Hf1,To_I), 
    time_out([(Hi2,Hf2)|R],To_R), 
    To is To_R + To_I. 

diff_t(Hi,Hf,D):-Hf>Hi, D is Hf - Hi. 
diff_t(Hi,Hf,D):-Hf=<Hi,HCA is Hf + 2400, D is HCA - Hi. 

當我測試它：

?- time_out([(_,1300),(1400,1600)],T). 
false. 

爲什麼沒有按它給我我想要的總時間嗎？

Answer 1

正如保羅已經說了，你需要一個基地子句遞歸：

time_out([_], 0). 
time_out([(_, Hf1), (Hi2, Hf2)|R], To) :- 
       diff_t(Hi2, Hf1, To_I), 
       time_out([(Hi2, Hf2)|R], To_R), 
       To is To_R + To_I. 

Answer 2

time_out/2謂詞只有一個遞歸子句。基本條款在哪裏？這個遞歸子句遍歷列表。假設謂詞是用一個封閉列表調用的，那麼你最終會用一個空列表作爲第一個參數來調用謂詞。由於沒有一個頭腦與這個目標相統一的條款，所以通話失敗。

另請注意，您的子句不是尾遞歸的。即在這種情況下，在遞歸調用之後有一個目標。這意味着這個目標必須保存在一個棧中（對於每次遞歸調用），直到找到一個基本案例。這個浪費空間（線性和遞歸調用的數量）。在這種情況下（通常情況下）將謂詞轉換爲尾遞歸謂詞的解決方案是使用一個累加器來計算您計算的距離。當你到達（丟失基本情況）時，累加器的值將是你計算的距離：

time_out(Stops, Distance) :- 
    % the initial value of the accumulator is zero 
    % as we're computing the sum of distances 
    time_out(Stops, 0, Distance). 

time_out([], Distance, Distance). 
time_out([(_, End1), (Start2, End2)| Stops], Distance0, Distance) :- 
    diff_t(Start2, End1, Leg), 
    Distance1 is Leg + Distance0, 
    time_out([(Start2, End2)| Stops], Distance1, Distance). 

但是這個定義是不正確的。你能發現問題嗎？當列表包含單個起始端對時會發生什麼？你能糾正這個定義嗎？也許我們有錯誤基本情況？

大多數的Prolog系統提供跟蹤特點，那就是在理解Prolog的計算通常會有所幫助：

?- trace. 
true. 

[trace] ?- time_out([(_,1300),(1400,1600)],T). 
    Call: (7) time_out([ (_G2156, 1300), (1400, 1600)], _G2169) ? creep 
    Call: (8) time_out([ (_G2156, 1300), (1400, 1600)], 0, _G2169) ? creep 
    Call: (9) diff_t(1400, 1300, _G2261) ? creep 
    Call: (10) 1300>1400 ? creep 
    Fail: (10) 1300>1400 ? creep 
    Redo: (9) diff_t(1400, 1300, _G2261) ? creep 
    Call: (10) 1300=<1400 ? creep 
    Exit: (10) 1300=<1400 ? creep 
    Call: (10) _G2262 is 1300+2400 ? creep 
    Exit: (10) 3700 is 1300+2400 ? creep 
    Call: (10) _G2265 is 3700-1400 ? creep 
    Exit: (10) 2300 is 3700-1400 ? creep 
    Exit: (9) diff_t(1400, 1300, 2300) ? creep 
    Call: (9) _G2268 is 2300+0 ? creep 
    Exit: (9) 2300 is 2300+0 ? creep 
    Call: (9) time_out([ (1400, 1600)], 2300, _G2169) ? creep 
    Fail: (9) time_out([ (1400, 1600)], 2300, _G2169) ? creep 
    Fail: (8) time_out([ (_G2156, 1300), (1400, 1600)], 0, _G2169) ? creep 
    Fail: (7) time_out([ (_G2156, 1300), (1400, 1600)], _G2169) ? creep 
false. 

仔細查看通話(9)。我會在明天之前給你，讓你找到解決這個問題的方法。快樂黑客！

UPDATE

現在的OP發現了一個可行的解決方案是時間來解決這一個。例如，通過寫：

time_out([(_, End1)| Stops], Distance) :- 
    % the initial value of the accumulator is zero 
    % as we're computing the sum of distances 
    time_out(Stops, End1, 0, Distance). 

time_out([], _, Distance, Distance). 
time_out([(Start2, End2)| Stops], End1, Distance0, Distance) :- 
    diff_t(Start2, End1, Leg), 
    Distance1 is Leg + Distance0, 
    time_out(Stops, End2, Distance1, Distance). 

注意，大多數的Prolog系統實現了所謂的第一參數索引優化，允許嘗試，可能能夠解決目前的目標條款。這種優化通常通過考慮類型以及對於原子項來實現，在某些情況下，第一個參數的值（如果綁定）。在兩個子句爲time_out/4謂詞的第一個參數是，對於第一個，原子[]（空列表是不列表），和用於第二個的列表與一種或多種元素。因此，假設這種優化，每次調用謂詞時都會選擇正確的子句（當然，其第一個參數被實例化），從而避免虛假的選擇點。但是，對於您的解決方案，同樣的優化不適用於您的time_out/2謂詞的兩個子句，第一個參數是一個列表。