`var(A)` 和执行顺序

`var(A)` and order of execution

本页练习 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) 的情况下重写解决方案,如果没有,为什么?

从声明的角度来看,var/1(\=)/2 等非单调结构非常有问题

为什么?看看:

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

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

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

关于 (\=)/2,您 认为 会表示两个术语不同?看看:

?- X \= Y.
false.

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

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

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 系统中甚至不可用的时代,当然不是免费的。