如何从序言中删除列表中的最后一个元素？

问题描述：

我在下面的情况：我有一个名单，我就从它只有最后一个元素删除。如何从序言中删除列表中的最后一个元素？

我有实现以下规则（不很好地工作）：

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仍保留为空列表。

这是不好的。

我想实现它执行以下操作：

计算列表元素的数量调用删除最后一个元素的谓词之前。
迭代通过递归每一次
如果这是真的，元素的数量为0则表示，这是最后一个元素，所以我从原来的名单

删除递减元素数量的值

但这似乎对我不太清楚，并没有那么好，我想知道是否有此问题的声明很好的解决方案。

答

为了防止无用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] 
...

答

如果你开发一个递归过程，其经过输入列表中的每一个元素，当你找到的最后一个元素统一与空列表结果列表中你的基本情况将停止。然后，从循环回骂你只是所有其他项目添加到结果列表：

不使用切：

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

的第一条（基本情况）统一用空列表时，第二个参数第一个参数列表中只有一个元素。

第二条规定，当第一个参数是至少有两个元素的列表，那么你递归调用本身（不包括头），一个头添加到由调用返回的第二个参数。

其实你并不需要做的是，名单需要有至少两种元素的第二条款中明确，

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

，当然，你也可以使用了append/3去除列表中的最后一项：

append(WithoutLast, [_], List).

+1 for'append（WithoutLast，[_]，List）'trick。 – 2013-04-23 17:07:23

答

我发现你的分析有点过于复杂。我们从基本情况开始：

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.

答

@重复的实现无疑是最有效的一个与当前的Prolog的处理器，还是我喜欢用DCG中用于此目的 - 偷偷希望有一天实现技术将是不够好，具有可比性（空间）运行此效率。

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

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

如何从序言中删除列表中的最后一个元素？

相关推荐