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

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

我觉得你的分析有点过于复杂.让我们从基础案例开始:

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 2

要防止创建无用的选择点,请使用滞后来从第一个参数索引中获益:

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([], Xs).
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 3

如果您开发了一个递归过程,该过程遍历输入列表的每个元素,当您找到最后一个元素将结果列表与空列表统一时,您的基本案例将停止.然后,从递归调用返回,您只需将所有其他项添加到结果列表中:

不使用切割:

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

当第一个参数列表中只有一个元素时,第一个子句(基本情况)将第二个参数与空列表统一起来.

第二个子句指出,当第一个参数是一个至少包含两个元素的列表时,则递归调用自身(没有头部),将Head添加到该调用返回的第二个参数.

实际上你不需要在第二个子句中明确表明列表需要至少有两个元素,

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

当然,您也可以使用append/3从列表中删除最后一项:

append(WithoutLast, [_], List).

Answer 4

@ repeat的实现肯定是当前Prolog处理器中最有效的实现,我仍然喜欢将DCG用于此目的 - 暗地希望有一天实现技术能够以相当的(空间)效率运行它.

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

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