`var(A)`和执行顺序

Question

本页上的练习09 http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/要求创建一个谓词,将重复的元素打包到子列表中.

一个直截了当的解决方案很简单

pack([], []).
pack([H|T], [I|U]) :-
    split(H, T, I, P),
    pack(P, U).

split split(Head, Tail, HeadGroup, Rest)的定义为

split(A, [], [A], []).
split(A, [B|T], [A], [B|T]) :- A \= B.
split(A, [A|T], [A|U], B) :- split(A, T, U, B).

工作正常,几乎与上述网页上提供的示例解决方案一致.

这个解决方案失败的地方是查询pack(X, [[a], [b, b]])..2个解集之间的对应关系是双射(对于每个A在pack(A, B)有一个且只有一个B),所以必须有一个更好的解决方案.

解决它的一种方法是改变评估的顺序,帮助prolog根据参数的类型选择非无限分支,如下所示

pack([], []).
pack(A, B) :-
  ( var(A) ->
    A = [H|T],
    B = [I|U],
    pack(P, U),
    split(H, T, I, P)
  ; A = [H|T],                                                                                                                                                                                                                                
    B = [I|U],
    split(H, T, I, P),
    pack(P, U)
  ).

这方面有两个问题.

首先,这是令人难以置信的丑陋,所以根据参数类型选择规则顺序可能有更好的方法吗？

其次,可能是更复杂的问题,有没有办法重写解决方案var(A),如果不是为什么？

Answer 1

从声明性的角度来看，非单调结构如var/1和 (\=)/2是非常有问题的。

为什么？一探究竟：

?- var(A), A=a.
A = a.

?- A=a, var(A).
false.

因此，这打破了合取交换律，这是我们在实际推理逻辑程序时所依赖的核心属性之一。

怎么样(\=)/2，您认为它可以表达两个术语不同？一探究竟：

?- X \= Y.
假。

不存在两个不同的术语，是吗？至少可以说，对我来说似乎有点奇怪，所以显然这个谓词确实意味着别的东西。

幸运的是，就您的情况而言，解决方案非常简单。只需使用纯约束dif/2来表示两个项是不同的。有关详细信息，请参阅prolog-dif 。您只需更改一行代码即可使您的解决方案更加通用。代替：

split(A, [B|T], [A], [B|T]) :- A \= B.

只需使用dif/2：

split(A, [B|T], [A], [B|T]) :- diff(A, B)。

通过此更改，您的示例完全按预期工作：

?- pack(X, [[a], [b, b]]).
X = [a, b, b] ;
false.

请注意，现有的 Prolog 文献已经过时了dif/2，并且大多数此类解决方案都来自大多数 Prolog 系统中甚至不可用的时代，当然在免费系统中也不可用。