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

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

(true当正确的答案是时,返回false).

如何使它在两种情况下都能正常工作？

也许我可以X is not 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的递归.请参阅此答案的第一部分已经解决了这个问题.

你的第三个条款错了:

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,您可以考虑在最后一个子句中添加一个警卫:

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]).将循环我的版本.

我希望它有用.