Подтвердить что ты не робот

Другое/2 - существует ли чистое, детерминированное определение?

different(Xs, Ys) :-
   member(X, Xs),
   non_member(X, Ys).
different(Xs, Ys) :-
   member(Y, Ys),
   non_member(Y, Xs).

Хотя это определение с использованием member/2 и non_member/2 почти 1 совершенный с декларативной точки зрения, он создает избыточные решения для определенных запросов и оставляет все точки выбора.

Что такое определение, которое улучшает это (в чистом виде, вероятно, используя if_/3 и (=)/3), так что точно такой же набор решений описывается different/2, но определяется по крайней мере для наземных запросов (таким образом, не оставляет бесполезных точек выбора открытым) и опускает (если возможно) любой избыточный ответ?

1 <суб > Фактически, different([a|nonlist],[]), different([],[b|nonlist]) преуспевает. Это может также потерпеть неудачу. Таким образом, решение, которое не подходит для обоих, прекрасно (возможно, даже более тонкое). Суб >

4b9b3361

ОТВЕТЫ

Ответ 1

Допустим это с помощью list_nonmember_t/3, exists_in_t/3, и or_/2!

some_absent_t(Xs,Ys,Truth) :-
   exists_in_t(list_nonmember_t(Ys),Xs,Truth).

different(Xs,Ys) :-
   or_(some_absent_t(Xs,Ys),
       some_absent_t(Ys,Xs)).

Ответ 2

Сначала попробуй!

Следующий код основан на мета-предикаты tfilter/3 и tpartition/4, монотонная конструкция if-then-else if_/3, овеществленная унарная логическая связь not_t/3 и предикат равенства терминов терминов (=)/3:

different([],[_|_]).
different([X|Xs0],Ys0) :-
   tpartition(=(X),Ys0,Es,Ys1),
   if_(Es=[], true, (tfilter(not_t(=(X)),Xs0,Xs1),different(Xs1,Ys1))).

Пример запроса:

?- different([A,B],[X,Y]).
                A=Y ,           dif(B,Y),     X=Y
;     A=X           ,     B=X           , dif(X,Y)
;     A=X           , dif(B,X), dif(B,Y), dif(X,Y)
;               A=Y ,               B=Y , dif(X,Y)
;               A=Y , dif(B,X), dif(B,Y), dif(X,Y)
; dif(A,X), dif(A,Y).

Наблюдайте детерминизм при работе с наземными данными:

?- different([5,4],[1,2]).
true.

Вышеприведенный подход кажется шагом в правильном направлении... Но, как есть, я бы не назвал его совершенным.

Ответ 3

Вот еще одна попытка! Мы используем монотонную конструкцию управления if-then-else if_/3 в сочетании с предикатом членства в reified list memberd_t/3 и индексацию первого аргумента, чтобы избежать создания бесполезных точек выбора.

different(Xs,Ys) :-
   different_aux(Xs,Ys,Xs,Ys).

different_aux([],[_|_],Xs0,Ys0) :-
   different_aux(Ys0,[],Ys0,Xs0).     % swap Xs/Ys pair
different_aux([X|Xs],Ys,Xs0,Ys0) :-
   if_(memberd_t(X,Ys0),
       different_aux(Ys,Xs,Ys0,Xs0),  % variant: different_aux(Xs,Ys,Xs0,Ys0)
       true).

Сначала мы запускаем запрос, который мы ожидаем сбой:

?- different([1,2,3],[2,3,1]).
false.

Следующие запросы аналогичны запросу, указанному выше; каждый из них имеет один "другой" элемент x, расположенный с разными индексами в первом [1,2,3] или во втором списке [2,3,1]:

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                 % all subgoals succeed deterministically

OK!. Запустите другой (довольно общий) запрос, который я использовал в моем предыдущий ответ:

?- different([A,B],[X,Y]).
      A=X ,               B=X , dif(Y,X)
;     A=X ,           dif(B,X), dif(Y,B)
;               A=Y , dif(B,X), dif(Y,X)
; dif(A,X), dif(A,Y).

Компактный. Большое улучшение по сравнению с тем, что я представил ранее!

Ответ 4

Вернемся к корням! Этот вариант очень близок к коду, данному ОП в вопросе.

Ниже приведено if_/3 и memberd_t/3.

different(Xs,Ys) :-
   if_(some_absent_t(Xs,Ys),
       true,
       some_absent_t(Ys,Xs,true)).

some_absent_t([]    ,_ ,false).
some_absent_t([X|Xs],Ys,Truth) :-
   if_(memberd_t(X,Ys), some_absent_t(Xs,Ys,Truth), Truth=true).

Вот основной запрос:

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                 % all subgoals succeed deterministically

И вот (более общий) запрос, который я использовал в предыдущих ответах:

?- different([A,B],[X,Y]).
      A=X ,               B=X ,           dif(Y,X)
;     A=X ,           dif(B,X), dif(B,Y)
;               A=Y ,               B=Y , dif(Y,X), dif(Y,X)
;               A=Y , dif(B,X), dif(B,Y), dif(Y,X)
; dif(A,X), dif(A,Y).

Ответ 5

(Во многом вдохновленный @repeat последним ответом, имена все еще слишком неуклюжи)

different(Xs, Ys) :-
   if_(tnotexists_inlist_t(list_memberd_t(Ys), Xs),
      true,
      tnotexists_inlist_t(list_memberd_t(Xs), Ys)).

tnotexists_inlist_t(_P_2, [], false).
tnotexists_inlist_t(P_2, [E|Es], T) :-
   if_(call(P_2, E),
      tnotexists_inlist_t(P_2, Es, T),
      T = true).

Ответ 6

Следующий участник конкурса красоты кодов! -)

Этот ответ показывает рефакторизованный вариант кода, показанный в предыдущий ответ. Он использует ринированное соединение и дизъюнкцию:

and_(P_1,Q_1) :-
   and_t(P_1,Q_1,true).

or_(P_1,Q_1) :-
   or_t(P_1,Q_1,true).

and_t(P_1,Q_1,Truth) :-
   if_(P_1, call(Q_1,Truth), Truth=false).

or_t(P_1,Q_1,Truth) :-
   if_(P_1, Truth=true, call(Q_1,Truth)).

Обратите внимание на две версии для "и" и "или"; те, у которых есть суффикс _t, имеют дополнительный аргумент для значения истинности, те, у кого нет суффикса, нет и предполагают, что Truth=true должен иметь место.

На основе and_t/3 и предиката неравенства терминов с термином dif/3 мы определяем nonmember_t/3:

nonmember_t(X,Ys,Truth) :-
   list_nonmember_t(Ys,X,Truth).

list_nonmember_t([]    ,_, true).
list_nonmember_t([Y|Ys],X,Truth) :-
   and_t(dif(X,Y), list_nonmember_t(Ys,X), Truth).

Теперь определим some_absent_t/3, different_t/3 и different/2, например:

some_absent_t([]    ,_ ,false).
some_absent_t([X|Xs],Ys,Truth) :-
   or_t(nonmember_t(X,Ys), some_absent_t(Xs,Ys), Truth).

different_t(Xs,Ys,Truth) :-
   or_t(some_absent_t(Xs,Ys),
        some_absent_t(Ys,Xs),
        Truth).

different(Xs,Ys) :-
   different_t(Xs,Ys,true).

Он все еще работает?

?- different([A,B],[X,Y]).
      A=X ,               B=X ,           dif(Y,X)
;     A=X ,           dif(B,X), dif(B,Y)
;               A=Y ,               B=Y , dif(Y,X), dif(Y,X)
;               A=Y , dif(B,X), dif(B,Y), dif(Y,X)
; dif(A,X), dif(A,Y).                     % same result as before

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                    % same result as before

Выглядит хорошо!

В целом, не огромное улучшение по сравнению с существующими ответами, а IMO несколько более читаемый код, а также обновленная версия different/2 в качестве дополнительного бонуса!

Ответ 7

Не так давно была предложена следующая жирная награда (+500):

Идиоматический ответ по-прежнему отсутствует. Например, or_t/3 должно быть (;)/3. Это еще не все.

Вызов принят! Этот ответ является продолжением этого предыдущего ответа.

  • Мы используем reified логическую связку (;)/3, которая может быть определена следующим образом:

    ';'(P_1,Q_1,T) :- if_(P_1, T=true, call(Q_1,T)).

  • Далее мы определяем meta-predicate call_/1. Это полезно с использованием предикатов, используемых в этом ответе. С его именем и семантикой call_/1 следует за if_/3, and_/2 и or_/2!

    call_(P_1) :- call(P_1,true).

  • Используя (;)/3, call_/1 и some_absent_t/3, мы реализуем different/2:

    different(As,Bs) :- call_((some_absent_t(As,Bs) ; some_absent_t(Bs,As))).

Готово! Что это.

Позвольте повторно запустить запросы, которые мы использовали в предыдущих ответах!

?- different([5,4],[1,2]).
true.

?- different([1,2,3],[2,3,1]).
false.

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

Те же запросы, одинаковые ответы... Мне нравится

Ответ 8

Консервирующие решения, которые используют if_, я бы сказал, что альтернативным подходом было бы использование конструктивного отрицания с самого начала. Конструктивное отрицание было исследовано уже в 80-х годах, пионером был Дэвид Чан, и все же время от времени выскакивает.

Предположим, что у нас есть интерпретатор Prolog, который имеет конструктивное отрицание (~)/2. Это конструктивное отрицание (~)/2 может быть использовано для определения декларативного if-then-else следующим образом: назовем этот оператор (~->)/2:

  (A ~-> B; C) :- (A, B); (~A, C).

Если интерпретатор Prolog также имеет встроенную импликацию (=>)/2, кроме конструктивного отрицания, можно альтернативно определить декларативное if-then-else следующим образом: позвоните этому оператору (~=>)/2:

  (A ~=> B; C) :- (A => B), (~A => C).

Обратите внимание на переключатель от дизъюнкции (;)/2 к соединению (,)/2. Спросите двоичную схему принятия решений (BDD), почему они логически эквивалентны. Процедурно есть нюансы, но через бэкдор встроенной импликации для определенного А второй вариант if-then-else также будет вводить неопределенность.

Но как бы мы пошли и представили, например, конструктивное отрицание в интерпретаторе Prolog. Прямым способом было бы делегировать конструктивное отрицание решателю ограничений. Если решатель ограничений подтвердил отрицание, это можно сделать следующим образом:

 ~ A :- #\ A.

Но вокруг не так много решателей ограничений, что позволило бы разумно использовать такие примеры, как member/2 и т.д. Поскольку часто они предоставляют отрицательное отрицание только для таких доменов, как конечные целые числа, рациональные и т.д. Но для предикат, такой как member/2, нам понадобилось бы повторное отрицание для вселенной Хербранда.

Также обратите внимание, что обычные подходы к конструктивному отрицанию также предполагают, что обычное выражение правила получает другое чтение. Это означает, что обычно при конструктивном отрицании мы можем выбрать обычное определение member/2 и получить результаты запроса, такие как:

?- ~ member(X, [a,b,c]).
dif(X, a),
dif(X, b),
dif(X, c).

Но опять же повторное отрицание вряд ли сработает с определенными предикатами, так что следующий запрос, вероятно, не сработает:

?- #\ member(X, [a,b,c]).
/* typically won't work */

Если вышеприведенное значение преуспевает, чем любое из декларативных if-then-else, таких как (~->)/2 или (~=>)/2, будет использоваться менее часто, поскольку обычные определения предикатов уже будут предоставлять декларативную интерпретацию интерпретатором Prolog. Но почему конструктивное отрицание не широко распространено? Одной из причин может быть большое пространство дизайна такого интерпретатора Prolog. Я заметил, что у нас будут следующие возможности:

Обратная цепочка: Мы в основном переплели бы переводчик ванили solve/1 на два предиката solvep/1 и solven/1. solvep/1 отвечает за решение позитивных целей, а solven/1 отвечает за решение отрицательных целей. Когда мы попробуем это, мы рано или поздно увидим, что нам нужна более тщательная обработка квантификаторов и, вероятно, закончится методом исключения квантификатора для домена Herbrand.

Прямое цепочка:. Мы также заметим, что в обратной цепочке мы столкнемся с проблемами для моделирования предложений с дизъюнкцией или квантором существования в голове. Это связано с тем, что для последовательного исчисления, подходящего для Prolog, есть только одна формула с правой стороны. Таким образом, либо мы идем с несколькими формулами с правой стороны, и теряем paraconsistency, или используем прямую цепочку.

Магические наборы:. Но перетаскивание по цепочке будет бесконтрольным образом распределять пространства решений. Таким образом, нам может понадобиться какая-то комбинация прямого и обратного сцепления. Я не имею в виду только то, что мы должны динамически переключаться между ними во время процесса решения, но я имею в виду, что мы не являемся также средством генерации множеств, которые направляют процесс прямой цепочки.

В этом ответе также упоминаются дополнительные проблемы . Это не означает, что рано или поздно будет найдена формула, чтобы совместить все эти проблемы и пары решений, но это может занять некоторое время.

Bye