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

Question

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 почти совершенных с декларативной точки зрения, это создает избыточные решения для определенных запросов и оставляет выбор точек вокруг.

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

---

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

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

Answer 2

В первую очередь!

Следующий код основан на мета-сказуемых tfilter/3 и tpartition/4, монотонной, если-то-иначе управление построить 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. 

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

Answer 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! Бежим другой (довольно общий) запрос, который я использовал в своей previous answer:

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

Compact! Большое улучшение по сравнению с тем, что я представил earlier!

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

Answer 5

(Большая вдохновленный @ повтор-х last answer, то имена по-прежнему слишком неуклюжи)

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

Answer 6

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

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

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 в качестве дополнительного бонуса!

Answer 7

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

^{Идиоматического ответ до сих пор не хватает здесь. Например, or_t/3 должно быть (;)/3. Это еще не все.}

Решение принято! Этот ответ является продолжением до this previous answer.

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

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

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

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

3. Использование (;)/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. 

Одинаковые запросы, одни и те же ответы ... Выглядит Хорошо для меня!

Answer 8

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

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

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

Если интерпретатор Пролога также встроенным подтекстом (=>)/2, кроме конструктивного отрицания, можно было бы в качестве альтернативы определит декларативным, если-то-иначе, как следует, позволяет называть этот оператор (~=>)/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 */ 

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

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

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

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

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

Bye