Making prolog predicates deterministic

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

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.