从列表中删除所有出现的元素 [英] Deleting all occurrences of an element from a list

问题描述

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

Trying to write a procedure that given a value and a list, it deletes all the occurence of that value in the list a wrote:

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 这段代码不能正确回答如下查询:

Since the cut this code cannot answer correctly queries like:

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

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

(returns true , when the correct answer is false).

如何让它在两种情况下都能正常工作?

How can I make it works in both situations?

也许我可以在第三行代码中检查 X is not T ，我试过:

Maybe I can check that X is not T in the third line of code, I tried:

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

但它不起作用.

推荐答案

剪辑的使用

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 记住从左到右和从上到下的选择点)，因此剪切(删除选择)不会做任何有用的事情，因为您已经在列表的底部的选择.

Here, you can see that you use !/0 in the last clause of your predicate. It's not necessary. After the last clause, there's no choice left (Prolog remembers choice points from left to right and top to bottom), so a cut (that removes choices), won't do anything useful since you're already at the bottom of your list of choices.

为了说明，请参阅

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

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

Here, to prove a, Prolog will first try b, then c, then d (left to right, then top to bottom).

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

BTW, as a beginner in Prolog, you should go as far as totally avoid the use of the cut. It will just add to your misunderstandings as long as you don't get recursion and the other basics of logic programming.

撇开这个小问题，你的问题是你还没有正确理解 Prolog 递归.请参阅此答案的第一部分，该部分已经解决了这一问题.

That little note aside, your problem is that you've not properly understood Prolog recursion yet. Please see the first part of this answer that already adresses this concern.

你的第三个条款是错误的:

Your third clause is wrong:

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，这会将您的线性谓词变成二次谓词.另外，正如您所注意到的，由于它不是尾递归的，因此在某些情况下更难获得终止.

Well, it's not really wrong, it's just really suboptimal. It's not tail-recursive and uses append/3, which would turn your linear predicate into a quadratic one. Plus, as you noticed, since it's not tail-recursive, termination is tougher to obtain in some cases.

那么，为了去掉!/0的使用，你可以考虑在最后一个子句中添加一个guard:

Then, to remove the use of the cut !/0, you can consider adding a guard to the last clause:

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 cannot在这里与 T 统一.

The guard, dif(X, T), specifies that if we're in the third case we cannot be in the second at the same time : X cannot be unified with T here.

注意，还有一种方式我们不能使用谓词，那就是，+, -, +, as cTI 告诉我们.所以像 ?- delMember(1, R, [2, 3]). 这样的查询将循环使用我的版本.

Note, there's still one way we can't use the predicate, this is, +, -, +, as cTI tells us. So queries like ?- delMember(1, R, [2, 3]). will loop with my version.

我希望它有用.

这篇关于从列表中删除所有出现的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！