使prolog谓词具有确定性

Question

我写了一个谓词,shuffle/3它生成了两个列表的"shuffles".当第二个和第三个参数被实例化时,第一个参数变为一个列表,其中包含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程序很重要吗？

Answer 1

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

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

这有两个答案.为什么？最好不要使用调试器来理解这一点,而是使用通用查询:

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

所以在这里你可以看到参数之间的"真实"联系!现在我们的特定查询是这个更通用查询的一个实例.因此,无法删除这两个答案.

但是,你可以以纯粹的方式使用剪切,只要它受到保护,结果总是纯净的.像测试一样,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赏金,但没有回应.我再次尝试另一个.

Answer 2

制作更多det版本的方法shuffle是使用if_/3from library 模块reif：

shuffle_det1( A,B,C):-
  if_( B=[], A=C,
   if_( C=[], A=B, 
        ( B=[BH|BT], C=[CH|CT], A=[AH|AT], (
                 AH=BH, shuffle_det1( AT, BT, C)
                 ;
                 AH=CH, shuffle_det1( AT, B, CT) ) ))).

按位置工作，没关系，确实消除了一些（大多数？）虚假选择点：

40 ?- shuffle_det1(X, [1, 2], [3, 4]).
X = [1, 2, 3, 4] ;
X = [1, 3, 2, 4] ;
X = [1, 3, 4, 2] ;
X = [3, 1, 2, 4] ;
X = [3, 1, 4, 2] ;
X = [3, 4, 1, 2].

41 ?- shuffle_det1(X, [11,12], [11,22]).
X = [11, 12, 11, 22] ;
X = [11, 11, 12, 22] ;
X = [11, 11, 22, 12] ;
X = [11, 11, 12, 22] ;
X = [11, 11, 22, 12] ;
X = [11, 22, 11, 12].

81 ?- shuffle_det1([1,2,3,4], [3, 4], [1, 2]).
true.

但：

82 ?- shuffle_det1([1,2,3,4], [1, 2], [3, 4]).
true ;
false.

此外，正如 [user: false ] 指出的那样，如果两个列表的头部元素相等，则答案中有一些冗余：

  11 12 13 ..       B
  21 22 23 ..       C

  11 (12.. + 21..)        |    21 (11.. + 22..)
      12 (13.. + 21..)             11 (12.. + 22..) *
    | 21 (12.. + 22..) *         | 22 (11.. + 23..)

这里标有 的两种情况*实际上是 conflate when 11 == 21。为了解决这个问题，我们在这种情况下通过连续进行两次来“展开”采摘：

shuffle_det( A,B,C):-
  if_( B=[], A=C,
   if_( C=[], A=B, 
        ( B=[BH|BT], C=[CH|CT], A=[AH|AT],
          if_( \X^(dif(BH,CH),X=true ; BH=CH,X=false),
               (
                 AH=BH, shuffle_det( AT, BT, C)
                 ;
                 AH=CH, shuffle_det( AT, B, CT) ),
               (
                 AH=BH, AT=[CH|A2], shuffle_det( A2, BT, CT)     % **
                 ;
                 pull_twice( A,B,C)
                 ;
                 pull_twice( A,C,B)
                ))))).

pull_twice([BH|AT],[BH|BT],C):- % B,C guaranteed to be non-empty
    if_( BT=[], AT=C,
         ( BT=[BH2|B2], AT=[BH2|A2], shuffle_det(A2,B2,C) )).

测试：

35 ?- shuffle_det(A, [11,12], [11,22]).
A = [11, 11, 12, 22] ;
A = [11, 11, 22, 12] ;
A = [11, 12, 11, 22] ;
A = [11, 22, 11, 12].

这已经比shuffle_det1. 但这还不完全正确：

38 ?- shuffle_det(A, [1], [1]).
A = [1, 1] ;
A = [1, 1] ;
A = [1, 1].

这两个pull_twice电话可能是罪魁祸首。不知何故必须只有一个，这将决定是否做另一个......