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

Question

我写了一个谓词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的新手，我想知道是否有人对我为什么关心确定性有任何建议。对于真正的序言程序重要吗？

Answer 1

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

?- 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美元，但没有回应。再一次，我尝试另一个。