如何在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，则意味着这是最后一个元素，因此将其从原始列表中删除。

但是这对我来说似乎不清晰，也不太好。我想知道是否有一个声明性良好的解决方案来解决这个问题。

- AndreaNobili

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.

- Daniel Lyons

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]
⋯

- repeat

Answer 3

如果您编写了一个递归过程，该过程会遍历输入列表中的每个元素，那么基本情况将在找到最后一个元素并将其与空列表统一时停止。然后，在从递归调用返回时，只需将其他项添加到结果列表即可。

不使用“cut”：

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

第一个子句（基本情况）将第二个参数与空列表统一，当第一个参数列表中只有一个元素时。

第二个子句说明当第一个参数是至少有两个元素的列表时，您需要递归地调用它本身（不包括头部），并将头部添加到该调用返回的第二个参数中。

实际上，在第二个子句中不需要显式指出列表至少需要有两个元素。

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

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

append(WithoutLast, [_], List).

- gusbro

Answer 4

@repeat的实现是目前Prolog处理器中最高效的，但我喜欢使用DCGs来完成这个任务 - 暗自希望有一天实现技术足够好，可以以相当的（空间）效率运行它。

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

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

- false

Answer 5

这是一个老问题，但我找到了另外两种方法：

• 不创建无用的选择点。
• 不需要额外的谓词。

findall(X ,append(X, [_], List), [X]).

length(List, N), nth1(N, List, _, X).

- Miguel

Answer 6

从列表中删除最后一个元素的最简单方法是：

• 反转列表
• 现在删除第一个元素
• 反转剩余的列表

您应该使用的代码：

delete_last(X,Y):-
    reverse(X,[_|X1]), reverse(X1,Y).

- Dilpreet