9

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

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

但它不起作用。

4

4 回答 4

10

切口的使用

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 的初学者,您应该尽量避免使用 cut。只要您不了解递归和逻辑编程的其他基础知识,它只会增加您的误解。

序言递归

除了那个小注释,你的问题是你还没有正确理解 Prolog 递归。请参阅已解决此问题的答案的第一部分。

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

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

它应该是:

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

好吧,这并没有真正的错误,它只是非常不理想。它不是尾递归和 uses append/3,这会将您的线性谓词变成二次谓词。另外,正如您所注意到的,由于它不是尾递归的,因此在某些情况下更难获得终止。

然后,要删除 cut 的使用!/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]).会循环。

我希望它有用。

于 2012-08-29T10:29:23.203 回答
4

让我们重新措辞一下:由于您想在多个实例化模式中使用谓词“一个给定值和列表的过程,它会删除列表中该值的所有出现”并没有定义它应该如何表现在其他情况下。因此,我们可能想要类似“如果第二个和第三个参数是列表 L1、L2 和 L1 与 L2 相同的列表,如果我们忽略第一个参数的所有出现,则谓词为真”

现在,有两种方法可以编写具有多个可能实例化的谓词;您可以使用元逻辑谓词,例如var/1andground/1并为每个谓词编写代码(这可能允许您编写针对特定实例优化的代码)或编写逻辑定义属性的代码(这可能更具挑战性)。

在这种情况下,我们可以这样做:

    del(_, [], []).
    del(X, [X|L1], L2):-
        del(X,L1,L2).
    del(X, [H|L1], [H|L2]):-
        X\==H,
        del(X,L1,L2).

它具有以下行为:

19 ?- del(1, [1,2,3], X).
X = [2, 3] ;
false.
1,2,3,
20 ?- del(1, [1,2,3], [2,3]).
true ;
false.

21 ?- del(X, [1,2,3], [2,3]).
X = 1 ;
false.

22 ?- del(X, [1,2,3], Y).
X = 1,
Y = [2, 3] ;
X = 2,
Y = [1, 3] ;
X = 3,
Y = [1, 2] ;
Y = [1, 2, 3] ;
false.

23 ?- del(X, P, Y).
P = Y, Y = [] ;
P = [X],
Y = [] ;
P = [X, X],
Y = [] ;
P = [X, X, X],
Y = [] ;
P = [X, X, X, X],
Y = [] ;
P = [X, X, X, X, X],
Y = [] ;
P = [X, X, X, X, X, X],
Y = [] .

关于最后一次通话;prolog 返回一个由于使用深度优先算法而增长的 X 列表;通过使用length/2我们可以得到广度优先的结果(_G 表示变量没有被实例化(它可以是任何东西)):

24 ?- length(P,N), del(X, P, Y).
P = [],
N = 0,
Y = [] ;
P = [X],
N = 1,
Y = [] ;
P = [_G548],
N = 1,
Y = [_G548] ;
P = [X, X],
N = 2,
Y = [] ;
P = [X, _G551],
N = 2,
Y = [_G551] ;
P = [_G548, X],
N = 2,
Y = [_G548] ;
P = [_G548, _G551],
N = 2,
Y = [_G548, _G551] ;
P = [X, X, X],

编辑:正如@chac 指出的那样,如果第一个列表(至少)有一个重复元素,则上述谓词的行为不正确:

?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ;                  <----- wrong
Y = [1, 2, 1].

这是因为实际上\==/2\=/2没有对变量施加限制。这可以通过切换第三条中的规则顺序来解决:

    del(_, [], []).
    del(X, [X|L1], L2):-
        del(X,L1,L2).
    del(X, [H|L1], [H|L2]):-
        del(X,L1,L2),
        X\==H.


4 ?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
Y = [1, 2, 1] ;
false.

然而,这意味着谓词不再是尾递归的。为了解决这个问题,我们可以保留 X 不应该是的值的列表:

del(X,L1,L2):-
    del(X,L1,L2,[]).

del(X, [], [], NotX):-
    \+ member(X,NotX).
del(X, [X|L1], L2, NotX):-
    del(X,L1,L2,NotX).
del(X, [H|L1], [H|L2], NotX):-
    X\==H,     % <--- optional; stops the execution earlier (saving time)
    del(X,L1,L2,[H|NotX]).

但是,根据以下内容,尾递归版本实际上更慢:

?-time(forall((between(1,50,N),length(X,N),del2(1,X,[2,3,2,3])),true)).
% 25,600,793 inferences, 5.468 CPU in 5.548 seconds (99% CPU, 4682134 Lips)
true.

?- time(forall((between(1,50,N),length(X,N),del_tr(1,X,[2,3,2,3])),true)).
% 37,346,143 inferences, 6.426 CPU in 6.428 seconds (100% CPU, 5811563 Lips)
true.

仍然, + - + 不起作用(它陷入无限循环)。但为什么?问题在于子句的顺序:del(1, L1, [2]) 将首先应用将 X “添加”到 L1 头部的规则,然后永远应用相同的规则。这可以通过使用 (again) 来解决length/2

?- length(X,2), del(1,X,[2]).
X = [1, 2] ;
X = [2, 1] ;
false.

或者,我们可以更改子句的顺序:

del(_, [], []).
del(X, [H|L1], [H|L2]):-
    X\==H,
    del(X,L1,L2),
    X\==H.
del(X, [X|L1], L2):-
    del(X,L1,L2).

length/2可能再次有用,因为没有它 prolog 会进行深度优先搜索:

?- del(1,X,[2]).
X = [2] ;
X = [2, 1] ;
X = [2, 1, 1] ;
X = [2, 1, 1, 1] ;
X = [2, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1, 1] 

当然length/2可以合并到包装谓词中,因为它不会影响其他实例化模式。

于 2012-08-29T10:39:17.947 回答
4

这不是一个真正的答案,只是对MogthanosQR答案的扩展说明,太长了,无法放入评论中。这样的答案是令人愉快和有启发性的,但需要重新考虑削减削减。考虑:

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

这个定义允许

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,1,2,1,2]).
Y = 3.

由于最后一个原因的守卫,在原始 Mog 代码中失败了。值得注意的是,用X \== T(将测试限制为匹配的实例化状态)替换守卫,也解决了这个查询,正如thanosQR所指出的那样。

但是这些片段都没有解决一般情况:

?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ;
Y = [1, 2, 1].
于 2012-08-29T12:21:41.070 回答
0

这是一个片段,它也适用于未实例化的第一个和第三个参数:

delMember(X, Y, Z):-
  bagof(A, (setof(X, member(X, Y), L), member(X, L), member(A, Y), A\==X), Z).

我将在这里解释这段代码的作用。这个想法是:

  1. 构建输入列表 Y 的不同成员的列表,该列表与输入成员 X 统一
  2. 然后对于基于 1) 构建的列表中的每个 X,从输入列表中丢弃该元素以获得没有成员 X 的输出列表 Z。

第 1 步已完成,setof(X, member(X, Y), L)它以两种方式工作。当参数X已经实例化时,如果包含在输入参数中,则将是L列表,如果不包含在中,它将失败。另一方面,如果未实例化,则将是输入参数的不同元素的集合。[X]XYXYXLY

现在在第 2 步中,我们回溯 的每个元素,并且对于该列表的每个成员,我们从产生结果L的输入列表中过滤该元素。Y我们在输出列表中收集所有这些元素Z

请注意,当调用过程时参数 X 未实例化时,在回溯时,我们将获得输入列表中将用于过滤member(X, Y)的每个成员。Y

测试用例:

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]).
false.

?- delMember(Y, [1,2,3,1,2,3], X).
Y = 1,
X = [2, 3, 2, 3] ;
Y = 2,
X = [1, 3, 1, 3] ;
Y = 3,
X = [1, 2, 1, 2].

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,1,2,1,2]).
Y = 3.

?- delMember(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1].
于 2012-08-29T13:21:23.053 回答