recursion - 如何创建删除倒数第二个元素的 Prolog 谓词？

Question

我需要帮助创建一个谓词，该谓词删除列表中倒数第二个元素并返回用 Prolog 编写的列表。到目前为止我已经

remove([],[]).
remove([X],[X]).
remove([X,Y],[Y]).

这就是我所了解到的。我需要找出一种方法来递归地遍历列表，直到它只有两个元素长，然后重新组装要返回的列表。如果可以的话帮忙解释一下。

Answer 1

到目前为止你的定义是完美的!它有点太专业了，所以我们必须扩展它。但你的程序是一个坚实的基础。

您“仅”需要扩展它。

remove([],[]).
remove([X],[X]).
remove([_,X],[X]).
remove([X,_,Y], [X,Y]).
remove([X,Y,_,Z], [X,Y,Z]).
remove([X,Y,Z,_,Z2], [X,Y,Z,Z2]).
...

好的，您知道如何继续了。现在，让我们识别常见情况:

...
remove([X,Y,_,Z], [X,Y,Z]).
%       ^^^        ^^^  
remove([X,Y,Z,_,Z2], [X,Y,Z,Z2]).
%       ^^^^^         ^^^^^
...

所以，我们有一个共同的列表前缀。我们可以说:

Whenever we have a list and its removed list, we can conclude that by adding one element on both sides, we get a longer list of that kind.

remove([X|Xs], [X|Ys]) :-
   remove(Xs,Ys).

请注意，:- 实际上是一个箭头。这意味着:只要右侧为真，左侧也为真。

等一下!事实真的如此吗？如何测试这个？ (如果您只测试阳性案例，您总是会得到"is"。)我们没有时间想出一些测试案例，不是吗？因此，让 Prolog 为我们完成这项艰苦的工作吧!所以，Prolog，填空吧!

remove([],[]).
remove([X],[X]).
remove([_,X],[X]).
remove([X|Xs], [X|Ys]) :-
   remove(Xs,Ys).

?- remove(Xs,Ys).                         % most general goal
   Xs = [], Ys = []
;  Xs = [A], Ys = [A]
;  Xs = [_,A], Ys = [A]
;  Xs = [A], Ys = [A]                     % redundant, but OK
;  Xs = [A,B], Ys = [A,B], unexpected     % WRONG
;  Xs = [A,_,B], Ys = [A,B]
;  Xs = [A,B], Ys = [A,B], unexpected     % WRONG again!
;  Xs = [A,B,C], Ys = [A,B,C], unexpected % WRONG
;  Xs = [A,B,_,C], Ys = [A,B,C]
;  ... .

人们很容易拒绝一切并从头开始。 但在 Prolog 中你可以做得更好，所以让我们冷静下来估计一下实际的损害: 有些答案是不正确的。有些答案是正确的。

我们当前的定义可能有点过于笼统。

为了更好地了解情况，我将详细查看意外成功 remove([1,2],[1,2])。谁是罪魁祸首？

即使下面的程序切片/片段也会成功。

remove([],[]).
remove([X],[X]) :- false.
remove([_,X],[X]) :- false.
remove([X|Xs], [X|Ys]) :-
   remove(Xs,Ys).

虽然这是我们程序的专门化，但它的内容是:remove/2 适用于所有相同的列表。这不可能是真的!为了解决这个问题，我们必须在剩余的可见部分做一些事情。我们必须将其特化。这里的问题是递归规则也适用:

remove([1,2], [1,2]) :-
   remove([2], [2]).
remove([2], [2]) :-
   remove([], []).

必须避免得出这样的结论。我们需要通过添加另一个目标 (=)/2 将规则限制为列表中至少有两个元素的情况。

remove([X|Xs], [Y|Ys]) :-
   Xs = [_,_|_],
   remove(Xs, Ys).

那么我们的错误是什么？在非正式场合

Whenever we have a list and its removed list, ...

术语“已删除列表”含糊不清。这可能意味着我们在这里引用关系remove/2(这是不正确的，因为 remove([],[]) 成立，但仍然没有删除任何内容)，或者我们在这里引用删除了元素的列表。此类错误在编程中不可避免地会发生，因为您希望通过使用比 Prolog 本身不太正式的语言来保持直觉。

作为引用，这里再次(并与其他定义进行比较)是最终定义:

remove([],[]).
remove([X],[X]).
remove([_,X],[X]).
remove([X|Xs], [X|Ys]) :-
   Xs = [_,_|_],
   remove(Xs,Ys).

有更有效的方法可以做到这一点，但这是最直接的方法。