Prolog删除给定列表中的一个元素

Question

你好，我希望能得到关于这个任务的一些建议或指导：

定义一个包含三个参数的语句，其中第一个是列表，第二个是元素（原子或列表），第三个是一个列表，它必须满足与第一个列表相等，但是第一个列表中匹配第二个参数的元素将被删除。

Examples:

> elimina([f, e, d, [a, h], a, d, a], a, L)

L = [f, e, d, [a, h], d]

> elimina([f, e, d, [ a, h], a, [d, a]], [a, h], L)

L = [f, e, d, a, [d, a]]

我尝试过：

elimina([],_,[]).
elimina([X],X,[]).
elimina([X],Y,[X]).
elimina([H|T],H,Result) :-
 elimina([T],H,Result).
elimina([H|T],Y,Result):-
 elimina([T],H,Result).

我有一个疑问，当我在递归调用时应该写什么：

elimina([T],H,Result).

因为我不知道当输入的第二个元素匹配头部而不匹配头部时应该有何不同的行为。所以我使用了相同的调用。 同时，我怀疑这是否真的需要添加基本情况：elimina([X],Y,[X])？ 我认为我们可以通过与实际在列表中的要删除的元素进行匹配来完成练习。

感谢您的时间。

- Yone

---

elimina([a],a,[a]) 不正确地成功了。 - false

Answer 1

有一种非常通用的方法可以测试你自己在Prolog中编写的代码。只需通过最一般的问题询问Prolog来生成所有可能性。

?- elimina([], D, Ys).
   Ys = [].                  % 1: nice!
?- elimina([X], D, Ys).
   D = X, Ys = []            % 1: nice!
;  Ys = [X]                  % 2: lacks dif(X, D)
;  X = [], D = [], Ys = []   % 3: correct but subsumed by 1
;  D = X, Ys = [[]]          % 4: incorrect
;  X = [], D = [], Ys = []   % 5: correct but subsumed by 1
;  X = [], D = [], Ys = [[]] % 6: incorrect
;  X = [], D = [], Ys = []   % 7: correct but subsumed by 1
;  ... .

对于空列表，一切都正常。但对于只有一个元素的列表，会有许多不必要的答案！实际上，应该只有两个答案：

    D = X, Ys = []
;   dif(D, X), Ys = [X].

现在选择您想要改进的某些情况！

也许选择答案＃4并设置D = a，X = a：

?- elimina([a], a, Ys).
   Ys = []        % 1: nice
;  Ys = [a]       % 2: incorrect
;  Ys = [[]]      % 3: incorrect
;  Ys = []        % 4: correct but subsumed by 1
;  Ys = [[]]      % 5: incorrect and subsumed by 3
;  Ys = []        % 6: correct but subsumed by 1
;  ... .

所以我会选择#3，实际上它应该失败，但事实并非如此。

?- elimina([a],a,[[]]).
   true
;  true
;  ... .

缩小嫌疑人范围，通过插入 false 和一些额外的方程式来解决问题：

?- elimina([a],a,[[]]).
   false.

elimina([],_,[]) :- false.
elimina([X],X,[]) :- false.
elimina([X],Y,[X]) :- Y = a, X = [].
elimina([H|T],H,Result) :- false,
   elimina([T],H,Result).
elimina([H|T],Y,Result):- Result =  [[]],
   elimina([T],H,Result).

现在看看剩下的部分，并思考一下。这些剩下的规则是否真的成立？

在剩下的可见部分中必须存在错误！

- false

Answer 2

在描述列表时，通常考虑使用DCGs来完成任务。你可以像这样描述关系：

elimina(L1,X,L2) :-              % L2 is described by
   phrase(elimina_x(L1,X),L2).   % elimina_x//2

elimina_x([],_X) -->             % nothing to delete
   [].                           % from the empty list
elimina_x([X|Xs],X)  -->         % if the head of the list equals X
   elimina_x(Xs,X).              % it's not in the list, same for the tail
elimina_x([X|Xs],Y)  -->         % if the head of the list
   {dif(X,Y)},                   % differs from Y
   [X],                          % it is in the list
   elimina_x(Xs,Y).              % same for the tail

您的示例查询已产生所需的结果。

   ?- elimina([f, e, d, [a, h], a, d, a], a, L).
L = [f,e,d,[a,h],d] ? ;
no
   ?- elimina([f, e, d, [ a, h], a, [d, a]], [a, h], L).
L = [f,e,d,a,[d,a]] ? ;
no

另外，您还可以更加简洁地表达这种关系，使用if_/3、(=)/3 和 tfilter/3：

dif_t(X,Y,T) :-
   if_(X=Y,T=false,T=true).

elimina(L1,X,L2) :-
   tfilter(dif_t(X),L1,L2).

上述查询与此版本的查询结果相同。

- tas