如何從序言中刪除列表中的最後一個元素？

Question

我在下面的情況：我有一個名單，我就從它只有最後一個元素刪除。

我有實現以下規則（不很好地工作）：

deleteLastElement([Only],WithoutLast) :- 
    !, 
    delete([Only],Only,WithoutLast). 
deleteLastElement([_|Tail],WithoutLast) :- 
    !, 
    deleteLastElement(Tail,WithoutLast). 

的問題是，當我把它稱爲，列表中的所有元素都將被刪除，其實如果我執行下面的語句我獲得：

[debug] ?- deleteLastElement([a,b,c], List). 
List = []. 

在跟蹤尋找我認爲這是明確這個問題的原因：

[trace] ?- deleteLastElement([a,b], List). 
    Call: (7) deleteLastElement([a, b], _G396) ? creep 
    Call: (8) deleteLastElement([b], _G396) ? creep 
    Call: (9) lists:delete([b], b, _G396) ? creep 
    Exit: (9) lists:delete([b], b, []) ? creep 
    Exit: (8) deleteLastElement([b], []) ? creep 
    Exit: (7) deleteLastElement([a, b], []) ? creep 
List = []. 

當達到基本情況時，WithoutLast列表與空列表 []統一，並且在執行回溯時，WithoutLast仍保留爲空列表。

這是不好的。

我想實現它執行以下操作：

1. 計算列表元素的數量調用刪除最後一個元素的謂詞之前。
2. 迭代通過遞歸每一次
3. 如果這是真的，元素的數量爲0則表示，這是最後一個元素，所以我從原來的名單

刪除遞減元素數量的值

但這似乎對我不太清楚，並沒有那麼好，我想知道是否有此問題的聲明很好的解決方案。

Answer 1

爲了防止無用choicepoints的創建，使用落後的，從第一個參數的索引中獲益：

list_butlast([X|Xs], Ys) :-     % use auxiliary predicate ... 
    list_butlast_prev(Xs, Ys, X).   % ... which lags behind by one item 

list_butlast_prev([], [], _). 
list_butlast_prev([X1|Xs], [X0|Ys], X0) :- 
    list_butlast_prev(Xs, Ys, X1).   % lag behind by one 

示例查詢：

?- list_butlast([], _). 
false. 

?- list_butlast([1], Xs). 
Xs = [].         % succeeds deterministically 

?- list_butlast([1,2], Xs). 
Xs = [1].         % succeeds deterministically 

?- list_butlast([1,2,3], Xs). 
Xs = [1,2].         % succeeds deterministically 

如何向另一個方向？

?- list_butlast(Xs, []). 
Xs = [_A]. 

?- list_butlast(Xs, [1,2,3]). 
Xs = [1,2,3,_A]. 

那麼最一般的查詢呢？

?- list_butlast(Xs, Ys). 
    Xs = [_A], Ys = [] 
; Xs = [_A,_B], Ys = [_A] 
; Xs = [_A,_B,_C], Ys = [_A,_B] 
; Xs = [_A,_B,_C,_D], Ys = [_A,_B,_C] 
; Xs = [_A,_B,_C,_D,_E], Ys = [_A,_B,_C,_D] 
... 

Answer 2

如果你開發一個遞歸過程，其經過輸入列表中的每一個元素，當你找到的最後一個元素統一與空列表結果列表中你的基本情況將停止。然後，從循環回罵你只是所有其他項目添加到結果列表：

不使用切：

deleteLastElement([_], []). 
deleteLastElement([Head, Next|Tail], [Head|NTail]):- 
    deleteLastElement([Next|Tail], NTail). 

的第一條（基本情況）統一用空列表時，第二個參數第一個參數列表中只有一個元素。

第二條規定，當第一個參數是至少有兩個元素的列表，那麼你遞歸調用本身（不包括頭），一個頭添加到由調用返回的第二個參數。

其實你並不需要做的是，名單需要有至少兩種元素的第二條款中明確，

deleteLastElement([Head|Tail], [Head|NTail]):- 
    deleteLastElement(Tail, NTail). 

，當然，你也可以使用了append/3去除列表中的最後一項：

append(WithoutLast, [_], List). 

Answer 3

我發現你的分析有點過於複雜。我們從基本情況開始：

without_last([_], []). 

當您在最後一個元素時，結果應該是空列表。

因此，歸納案例必須是我們不是最後一個元素的情況。在我將一些元素附加到任意長列表的情況下，沒有最後一個元素的列表只是列表的尾部，而沒有最後一個具有當前元素的元素。或者：

without_last([X|Xs], [X|WithoutLast]) :- 
    without_last(Xs, WithoutLast). 

這可以在任何方向工作。

?- without_last([1,2,3,4], X). 
X = [1, 2, 3] ; 
false. 

?- without_last([1,2], X). 
X = [1] . 

?- without_last([1], X). 
X = [] ; 
false. 

?- without_last([], X). 
false. 

?- without_last(X, [1,2,3]). 
X = [1, 2, 3, _G294]. 

?- without_last([1,2,3,4], [1,2,3]). 
true. 

?- without_last([1,2,3,X], [1,2,3]). 
true. 

Answer 4

@重複的實現無疑是最有效的一個與當前的Prolog的處理器，還是我喜歡用DCG中用於此目的 - 偷偷希望有一天實現技術將是不夠好，具有可比性（空間）運行此效率。

list_butlast(Xs, Ys) :- 
    phrase((seq(Ys), [_]), Xs). 

seq([]) --> 
    []. 
seq([E|Es]) --> 
    [E], 
    seq(Es).