时间戳

首页 > 解决方案 > 使序言谓词具有确定性

prolog - 使序言谓词具有确定性

问题描述

我写了一个谓词 ，shuffle/3它生成两个列表的“洗牌”。当实例化第二个和第三个参数时，第一个参数变成一个列表，其中包含 Left 和 Right 的所有元素，其顺序与它们在 Left 和 Right 中出现的顺序相同。

例如：

?- shuffle(X, [1, 2], [3, 4]).
X = [1, 3, 2, 4] ;
X = [1, 3, 4, 2] ;
X = [1, 2, 3, 4] ;
X = [3, 4, 1, 2] ;
X = [3, 1, 2, 4] ;
X = [3, 1, 4, 2] ;
false.

这是我想出的实现它的代码：

shuffle([], [], []).
shuffle([H|R], [H|Left], Right) :- shuffle(R, Right, Left).
shuffle([H|R], Left, [H|Right]) :- shuffle(R, Right, Left).

这很好用，甚至可以为“最一般的查询”生成合理的结果，但它对于任何查询都不是确定性的，即使是所有参数都被完全实例化的查询：shuffle([1, 2, 3, 4], [1, 2], [3, 4]).

我真正的问题是：有什么我可以做的，同时保持纯度（所以，没有削减），当所有参数都被完全实例化时，这使得这个谓词具有确定性？

当我在这里时，我是 Prolog 的新手，我想知道是否有人对我为什么要关心确定性提出建议。它对真正的序言程序很重要吗？

标签： prolog

解决方案

不，没有办法在保持纯代码的同时使这个谓词具有确定性。要看到这一点，请考虑：

?- shuffle([1, 1], [1], [1]).
      true
   ;  true.

对此有两个答案。为什么？最好不要使用调试器来理解这一点，而是使用通用查询：

?- shuffle([X1, X2], [Y1], [Y2]).
      X1 = Y1, X2 = Y2
   ;  X1 = Y2, X2 = Y1.

所以在这里你可以看到论点之间的“真实”联系！现在我们的特定查询是这个更一般查询的一个实例。因此，没有办法删除这两个答案。

但是，您可以以纯方式使用 cut ，前提是对其进行保护以使结果始终是纯的。就像测试一样ground(shuffe(Xs, Ys, Zs))，但所有这些都是临时性的。

再想一想，可能会有一个纯粹的、确定的答案，但前提是答案会以shuffle([X1, X2], [Y1], [Y2]).某种方式改变。答案实际上应该是：

?- shuffledet([X1, X2], [Y1], [Y2]).
      X1 = X2, X2 = Y1, Y1 = Y2      % all equal
   ;  dif(X1, X2), X1 = Y1, X2 = Y2
   ;  dif(X1, X2), X1 = Y2, X2 = Y1.

所以这可能是一种可能性......我会尽快给这个 500 赏金，但没有回应。我再次尝试另一个。

推荐阅读