2

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

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

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

4

2 回答 2

3

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

你“只”需要扩展它。

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]).
%       ^^^^^         ^^^^^
...

所以，我们有一个通用的列表前缀。我们可以说：

每当我们有一个列表及其已删除的列表时，我们可以得出结论，通过在两侧添加一个元素，我们会得到一个更长的那种列表。

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

请注意，:-实际上是一个箭头。它的意思是：如果右边的东西是真的，那么左边的东西也是真的。

……等一下！真的是这样吗？如何测试这个？（如果您只针对阳性案例进行测试，您将始终得到“是”。）我们没有时间想出一些测试案例，是吗？所以让我们让Prolog为我们做艰苦的工作吧！所以，Prolog，填空！

消除（[]，[]）。
删除（[X]，[X]）。
删除（[_，X]，[X]）。
删除（[X|Xs]，[X|Ys]）：-
   删除（Xs，Ys）。

| ?- 删除（Xs，Ys）。% 最普遍的目标

Xs = []，Ys = []；

Xs = [A]，Ys = [A]；

Xs = [_,A], Ys = [A] ;

Xs = [A]，Ys = [A]；% 冗余，但可以

Xs = [A,B], Ys = [A,B] ; %错误

Xs = [A,_,B], Ys = [A,B] ;

Xs = [A,B], Ys = [A,B] ; %又错了！

Xs = [A,B,C], Ys = [A,B,C] ; %错误

Xs = [A,B,_,C], Ys = [A,B,C] ...

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

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

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

甚至以下程序切片/片段也成功。

消除（[]，[]）。
删除（[X]，[X]）：-假。
删除（[_，X]，[X]）：-假。
删除（[X|Xs]，[X|Ys]）：-
   删除（Xs，Ys）。

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

删除（[1,2]，[1,2]）：-
   删除（[2]，[2]）。
删除（[2]，[2]）：-
   消除（[]， []）。

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

删除([X|Xs], [Y|Ys]) :-
    Xs = [_,_|_] ,
   删除（Xs，Ys）。

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

每当我们有一个列表及其已删除的列表时，...

"删除名单"一词含糊不清。这可能意味着我们在这里指的是关系 remove/2（这是不正确的，因为remove([],[])成立，但仍然没有删除任何内容），或者我们在这里指的是删除了一个元素的列表。这样的错误不可避免地发生在编程中，因为你想通过使用比 Prolog 本身更不正式的语言来保持你的直觉。

作为参考，这里再次（并与其他定义进行比较）是最终定义：

消除（[]，[]）。
删除（[X]，[X]）。
删除（[_，X]，[X]）。
删除（[X|Xs]，[X|Ys]）：-
   Xs = [_,_|_],
   删除（Xs，Ys）。

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

于 2013-10-29T22:19:14.077 回答
1

如果您只考虑“倒数第二个元素”的含义，我将尝试提供另一种更易于构建的解决方案，并明确描述每种可能的情况：

rem_2nd_last([], [])。
rem_2nd_last([First|Rest], R) :-
    rem_2nd_last_2（休息，第一，R）。% “滞后”列表一次

rem_2nd_last_2（[]，第一，[第一]）。
rem_2nd_last_2([Second|Rest], First, R) :-
    rem_2nd_last_3（休息，第二，第一，R）。% “滞后”列表两次

rem_2nd_last_3（[]，最后一个，_SecondLast，[最后一个]）。%列表结尾：倒数第二
rem_2nd_last_3([This|Rest], Prev, PrevPrev, [PrevPrev|R]) :-
    rem_2nd_last_3（休息，这个，上一个，R）。%列表的其余部分

解释隐藏在三个谓词的定义中。

“滞后”是一种从列表末尾返回但始终保持谓词确定性的方法。您只需抓取一个元素并将列表的其余部分作为辅助谓词的第一个参数传递。例如，定义 的一种方法last/2是：

最后（[H | T]，最后）：-
    last_1（T，H，最后）。

最后_1（[]，最后，最后）。
最后_1（[H | T]，_，最后）：-
    last_1（T，H，最后）。
于 2013-10-30T12:37:44.850 回答