6

此页面上的练习 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).

其中 splitsplit(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]]).. 两个解集之间的对应是双射的（其中每一个只有一个） 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)，如果没有，为什么？

4

1 回答 1

4

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

为什么？一探究竟：

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

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

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

怎么样(\=)/2，你认为这会表达两个术语是不同的？一探究竟：

?- X \= Y.
错误。

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

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

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

只需使用dif/2：

拆分（A，[B|T]，[A]，[B|T]）：-差异（A，B）。

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

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

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

于 2016-07-22T13:45:42.783 回答