prolog - 从列表中删除所有出现的元素

Question

尝试编写一个给定值和列表的过程，它会删除所写列表中该值的所有出现:

delMember(X, [], []) :- !.
delMember(X, [X|Xs], Y) :- !, delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- !, delMember(X, Xs, Y2), append([T], Y2, Y).

自从cut之后，此代码无法正确回答如下查询:

delMember(Y, [1,2,3,1,2,3,1,2,3], [1, 2, 1, 2, 1, 2 ]).

如果我删除剪辑:

delMember(X, [], []).
delMember(X, [X|Xs], Y) :- delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- delMember(X, Xs, Y2), append([T], Y2, Y).

它在以下查询中失败:

delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]).

(当正确答案为 false 时，返回 true )。

如何才能使其在这两种情况下都有效？

也许我可以检查第三行代码中的X不是T，我尝试过:

delMember(X, [T|Xs], Y) :- not(X = T), delMember(X, Xs, Y2), append([T], Y2, Y).

但是它不起作用。

Answer 1

剪切的使用

delMember(X, [], []) :- !.
delMember(X, [X|Xs], Y) :- !, delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- !, delMember(X, Xs, Y2), append([T], Y2, Y).

在这里，您可以看到您在谓词的最后一个子句中使用了 !/0。这不是必需的。在最后一个子句之后，就没有任何选择了(Prolog 从左到右、从上到下记住选择点)，因此剪切(删除选择)不会做任何有用的事情，因为您已经位于列表的底部选择。

为了说明这一点，请参阅

a :- b; c.
a :- d.

这里，为了证明a，Prolog将首先尝试b，然后c，然后d(左向右，然后从上到下)。

顺便说一句，作为 Prolog 的初学者，您应该尽可能完全避免使用剪切。只要您不了解递归和逻辑编程的其他基础知识，它只会增加您的误解。

Prolog 递归

撇开这个小注释不谈，你的问题是你还没有正确理解 Prolog 递归。请参阅this answer的第一部分这已经解决了这个问题。

你的第三个子句是错误的:

delMember(X, [T|Xs], Y) :- delMember(X, Xs, Y2), append([T], Y2, Y).

它应该是:

delMember(X, [T|Xs], [T|Y]) :- delMember(X, Xs, Y).

嗯，这并不是真的错误，只是真的不太理想。它不是尾递归并使用 append/3，这会将您的线性谓词变成二次谓词。另外，正如您所注意到的，由于它不是尾递归，因此在某些情况下更难以终止。

然后，要删除 !/0 的使用，您可以考虑在最后一个子句中添加一个 guard:

delMember(_, [], []).
delMember(X, [X|Xs], Y) :-
    delMember(X, Xs, Y).
delMember(X, [T|Xs], [T|Y]) :-
    dif(X, T),
    delMember(X, Xs, Y).

守卫，dif(X, T)，指定如果我们处于第三种情况，我们不能同时处于第二种情况:X 不能此处与T统一。

注意，还有一种方法我们不能使用谓词，即 +, -, +，如 cTI告诉我们。因此像 ?- delMember(1, R, [2, 3]). 这样的查询将与我的版本一起循环。

希望它有用。