使用示例(Prolog语言)理解Cut(!)运算符的问题



我有以下规则:

noRepetition([]).
noRepetition([Elem|Rest]):- not(member(Elem,Rest)), !, noRepetition(Rest).

此规则用于决定列表中是否没有重复元素,成员规则则决定特定元素是否属于列表。我的问题与此规则中的切割运算符有关,因为我不确定它的作用。

我为?-noRepetition([a,b,b,c,d])绘制了以下跟踪,并遇到了一个问题(可能与我对切割运算符缺乏了解有关):

?-noRepetition([a,b,b,c,d])
Unfies with the second noRepetion rule and instantiates variables to:
noRepetition([a|b,b,c,d] :- not(member(a,[b,b,c,d])), !, noRepetition([b,b,c,d]).

现在我被卡住了,因为在这种情况下,非成员返回true,因此剪切被证明是真的,但我不确定这个剪切是否阻止了程序进入noRepetition(第三个目标),或者它是否做了其他事情。如果它确实阻止了程序进入noRepetition,那么该规则将被评估为true,但事实并非如此,因为列表中存在重复。

回答您的问题。我的看法是:削减是没有必要的。你可能想刷新一下你对切割的记忆;这是一个简短的总结。一个好的经验法则是看看切球前的最后一个进球,看看它是否留下了选择点。如果是这样,那么它们都会被丢弃(以及本条款正文中早期目标的所有选择点),您只剩下第一个解决方案。所以我们看一下:

+ member(Elem, Rest) % just another way to say not...

这什么时候才能留下一个选择点?如果Goal为false,则+ Goal为true,否则为false。据我所知,+ Goal永远不可能是真的,也不可能是假的。那你为什么要剪?在这种情况下,它是多余的,实际上什么也没做。

(我仍然想知道你为什么一开始就把cut放在那里。有没有类似的谓词在member/2上没有使用否定?)

提供更好的解决方案不受询问者的欢迎,但至少有两种其他方法可以解决这个问题。您甚至可以将它们混合在一起,以获得以下定义:

all_dif_list(L) :-
(   ground(L)
->  sort(L, S),
length(L, N),
length(S, N)
;   all_dif_list_nonground(L)
).
all_dif_list_nonground([]).
all_dif_list_nonground([X|Xs]) :-
maplist(dif(X), Xs),
all_dif_list_nonground(Xs).

如果您知道列表已经完全实例化,那么您可以对其进行排序,并比较长度。sort/2会删除重复项,因此如果存在重复项,则排序列表会更短。

如果列表中包含变量,那么安全的做法就是说列表中的每一对元素都是(并且永远是)不同的。

请记住,member/2比其简单的名称和直接的定义更复杂。如果我想从中受益的话,我可以很容易地写一篇1000字的关于member/2行为的文章。

noRepetition([]).
noRepetition([Item|Rest]) :- member(Item,Rest), !, fail.
noRepetition([_|Rest]) :- noRepetition(Rest).

注:若Item不是一个接地项,结果可能会出乎意料。例如:

noRepetition([X,a,b]).

将失败。。。

最新更新