Making prolog predicates deterministic

Question

I've written a predicate, shuffle/3, which generates "shuffles" of two lists. When the second and third argument are instantiated, the first argument becomes a list which has all the elements of both Left and Right, in the same order that they appear in Left and Right.

For example:

?- 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.

Here's the code I've come up with to implement it:

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

This works well, and even generates reasonable results for "the most general query", but it fails to be deterministic for any query, even one where all arguments are fully instantiated: shuffle([1, 2, 3, 4], [1, 2], [3, 4]).

My real question is: is there anything I can do, while maintaining purity (so, no cuts), which makes this predicate deterministic when all arguments are fully instantiated?

And while I'm here, I'm new to Prolog, I wonder if anyone has advice on why I would care about determinism. Is it important for real prolog programs?

Answer 1

No, there is no way to make this predicate deterministic while still maintaining pure code. To see this, consider:

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

There are two answers to this. Why? The best is not to use a debugger to understand this, but rather to use a generalized query:

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

So here you can see the "true" connection between the arguments! And now our specific query is an instance of this more general query. Thus, no way to remove the two answers.

However, you might use cut in a pure way, provided it is guarded such that the result will always be pure. Like testing ground(shuffe(Xs, Ys, Zs)) but all of this is quite ad hoc.

---

On second thought, there might be a pure, determinate answer, but only if the answers to shuffle([X1, X2], [Y1], [Y2]). are changed somehow. The answer actually should be:

?- 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.

So that might be a possibility... I will had put a 500 bounty on this ASAP, but no response. And again I try another one.

Answer 2

The way to make the more det version of shuffle is using if_/3 from library module 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) ) ))).

Working positionally, it's OK, and indeed eliminates some (most?) spurious choice points:

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.

But:

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

Also, as [user:false] points out, if two lists' head elements are equal, there's some redundancy in the answers:

  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..)

Here the two cases marked with * actually conflate when 11 == 21. To combat that, we "unroll" the picking by doing two in a row in such cases:

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) )).

Testing:

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].

This is already much better than shuffle_det1. But it's not fully right yet:

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

The two pull_twice calls are probably the culprit. Somehow there must be only one, which would decide whether to do the other one or not...

Answer 3

I only want to remark that OPs shuffle/3 is a strange shuffle:

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

The shuffle from the logic programming wiki page is rather, moveing the last argument to the front. So Left and Right are not switched in the tail:

shuffle([], [], []).
shuffle([First | ShortMerge], [First | Rest], Right) :-
    shuffle(ShortMerge, Rest, Right).
shuffle( [First | ShortMerge], Left, [First | Rest]) :-
    shuffle(ShortMerge, Left, Rest).

I dont know whether it really matters, but just for the record.