Другой /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]) преуспевает. Это может также потерпеть неудачу. Таким образом, решение, которое терпит неудачу для обоих, хорошо (возможно, даже лучше).
8 ответов
Давайте возьмем это к пределу --- с помощью 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)).
Первая попытка!
Следующий код основан на мета-предикатах 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.
Приведенный выше подход выглядит как шаг в правильном направлении... Но, как есть, я бы не назвал его идеальным.
Вот еще одна попытка! Мы используем монотонную управляющую конструкцию if-then-else if_/3 в сочетании с предикатом членства в расширенном списке 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]:
? - разные ([ 4, 2,3], [2,3,1]), разные ([1,2,3], [ 4, 3,1]), разные ([1, 4, 3], [2,3,1]), разные ([1,2,3], [2, 4, 1]), разные ([1,2, 4 ], [2,3,1]), разные ([ 1,2,3], [2,3, 4 ]). правда. % все подцели достигают успеха
ХОРОШО! Давайте запустим еще один (довольно общий) запрос, который я использовал в своем предыдущем ответе:
?- 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).
Компактный! Большое улучшение по сравнению с тем, что я представил ранее!
(Во многом вдохновленный последним ответом@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).
Вернуться к истокам! Этот вариант очень близок к коду, указанному ОП в вопросе.
Следующее основано на 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).
Вот наземный запрос:
? - разные ([ 4, 2,3], [2,3,1]), разные ([1,2,3], [ 4, 3,1]), разные ([1, 4, 3], [2,3,1]), разные ([1,2,3], [2, 4, 1]), разные ([1,2, 4 ], [2,3,1]), разные ([1,2,3], [2,3,4]). правда. % все подцели достигают успеха
И вот (более общий) запрос, который я использовал в предыдущих ответах:
?- 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).
Очередная участница конкурса красоты на конкурс!-)
Этот ответ показывает измененный вариант кода, показанный в предыдущем ответе. Это использует reified соединение и дизъюнкцию:
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),
Истина).
разные (Xs,Ys):-
Different_t (Xs, Ys, true).
Это все еще работает?
?- разные ([A,B],[X,Y]).
A=X, B=X, диф (Y,X); A=X, диф (B,X), диф (B,Y); A=Y, B=Y, диф (Y, X), диф (Y,X); A=Y, диф (B,X), диф (B,Y), диф (Y, X); диф (А, Х), диф (А,Y). % тот же результат, что и раньше?- разные ([ 4, 2,3], [2,3,1]), разные ([1,2,3], [ 4, 3,1]),
разные ([1, 4, 3], [2,3,1]), разные ([1,2,3], [2, 4, 1]),
разные ([1,2, 4 ], [2,3,1]), разные ([1,2,3], [2,3,4]).
правда. % тот же результат, что и раньше
Выглядит хорошо!
В общем, не огромное улучшение по сравнению с существующими ответами, но несколько более читаемый код IMO и усовершенствованная версия different/2 в качестве дополнительного бонуса!
Следующая жирная награда (+500) была предложена не так давно:
Идиоматический ответ все еще здесь отсутствует. Например, or_t/3 должно быть (;)/3. Это еще не все.
Вызов принят! Этот ответ является продолжением этого предыдущего ответа.
Мы используем усовершенствованную логическую связку
(;)/3, который можно определить так:';' (P_1, Q_1, T): - if_ (P_1, T = true, вызов (Q_1,T)).
Далее мы определим мета-предикат
call_/1, Это полезно с уточненными предикатами, используемыми в этом ответе. С его именем и семантикой,call_/1следуетif_/3,and_/2, а такжеor_/2!call_ (P_1): - вызов (P_1, true).
С помощью
(;)/3,call_/1, а такжеsome_absent_t/3мы реализуемdifferent/2:разные (As, Bs): - call_ ((some_absent_t (As, Bs); some_absent_t (Bs, As))).
Готово! Вот и все.
Давайте снова запустим запросы, которые мы использовали в предыдущих ответах!
? - разные ([ 5, 4 ], [ 1, 2 ]).
правда.
? - разные ([1,2,3], [2,3,1]).
ложный.
? - разные ([ 4, 2,3], [2,3,1]), разные ([1, 4, 3], [2,3,1]), разные ([1,2, 4 ], [2,3,1]),
разные ([1,2,3], [ 4, 3,1]), разные ([1,2,3], [2, 4, 1]), разные ([1,2,3], [2, 3, 4 ]).
правда.
Те же самые запросы, те же самые ответы... Выглядит хорошо для меня!
Что касается решений, использующих if_, я бы сказал, что альтернативный подход заключается в использовании конструктивного отрицания с самого начала. Конструктивное отрицание было исследовано уже в 80-х годах, пионером был Дэвид Чан, и до сих пор всплывает время от времени.
Предположим, у нас есть интерпретатор Пролога, который имеет конструктивное отрицание (~)/2, Это конструктивное отрицание (~)/2 может использоваться для определения декларативного if-then-else следующим образом, давайте вызовем этот оператор (~->)/2:
(A ~-> B; C) :- (A, B); (~A, C).
Если интерпретатор Пролога также имеет встроенное значение (=>)/2 кроме конструктивного отрицания, можно альтернативно определить декларативное if-then-else следующим образом: давайте вызовем этот оператор (~=>)/2:
(A ~=> B; C) :- (A => B), (~A => C).
Обратите внимание на переход от дизъюнкции (;)/2 соединяться (,)/2, Спросите людей из Binary Decision Diagram (BDD), почему они логически эквивалентны. С процедурной точки зрения есть нюансы, но через черный ход встроенной импликации для некоторого A второй вариант if-then-else также привнесет недетерминированность.
Но как нам поступить и ввести, например, конструктивное отрицание в интерпретаторе Пролога? Прямой путь - делегировать конструктивное отрицание решателю ограничений. Если в решателе ограничений установлено отрицание, это можно сделать следующим образом:
~ 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. Но почему конструктивное отрицание не так широко распространено? Одной из причин может быть большое пространство для разработки такого интерпретатора Пролога. Я заметил, что у нас будут следующие варианты:
Цепочка в обратном направлении: мы бы в основном плевали ванильным переводчиком solve/1 на два предиката solvep/1 а также solven/1, solvep/1 несет ответственность за решение положительных целей и solven/1 отвечает за решение отрицательных целей. Когда мы попробуем это, мы рано или поздно увидим, что нам нужно более осторожно относиться к кванторам, и, вероятно, в итоге мы получим метод исключения квантификаторов для области Гербранда.
Прямая цепочка: мы также заметим, что при обратной цепочке мы столкнемся с проблемами при моделировании предложений с дизъюнкцией или экзистенциальным квантификатором в голове. Это связано с тем, что подходящее для Пролога исчисление секвенций имеет только одну формулу в правой части. Так что либо мы перейдем к мульти-формуле с правой стороны и потеряем взаимосогласованность, либо используем прямую цепочку.
Магические наборы: Но прямое построение цепей будет растворять пространства решений неконтролируемым образом. Таким образом, нам может потребоваться некоторая форма комбинации прямого и обратного сцепления. Я имею в виду не только это, что мы должны иметь возможность динамически переключаться между ними во время процесса решения, но я имею в виду, что нам также необходимо средство для генерации наборов, которые управляют процессом прямого связывания.
Другие проблемы также отмечены в этом ответе здесь. Это не означает, что рано или поздно будет найдена формула, которая бы соединила все пары "проблема" и "решение", но это может занять больше времени.
до свидания