Создание предикатов пролога детерминированным

Я написал предикат, shuffle/3, который генерирует "перетасовки" из двух списков. Когда второй и третий аргументы создаются, первый аргумент становится списком, который имеет все элементы как слева, так и справа, в том же порядке, в котором они отображаются слева и справа.

Например:

?- 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, мне интересно, есть ли у кого-нибудь совет, почему я буду заботиться о детерминизме. Это важно для реальных пролог программ?

Ответ 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 баунти на это ~~как можно скорее,~~ но никакого ответа. И снова я пробую другой.

Ответ 2

Чтобы сделать более det версию shuffle, используйте if_/3 из 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..)

Здесь два случая, отмеченные * фактически совпадают, когда 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 два pull_twice. Так или иначе должен быть только один, который решит, делать ли другой или нет...