`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(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]]). 这样的查询。两个解集之间的对应关系是双射的（对于pack(A, B)中的每个A，只有一个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.
false.

不存在两个不同的术语，是吗？ 我觉得有点奇怪，至少可以这么说，所以显然谓词确实有别的意思。

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

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

只需使用dif/2:

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

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

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

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

`var(A)` 和执行顺序

`var(A)` and order of execution

list

prolog

prolog-dif

logical-purity