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

Декларативное использование memberchk/2

memberchk/2 - это обычно определенный предикат, который определен в терминах member/2 следующим образом:

memberchk(X, Xs) :-
   once(member(X, Xs)).

Следовательно, это удается только для первого ответа member/2. Его полное процессуальное значение не вписывается в чистое отношение. В качестве примера для его нереляционного поведения рассмотрим

?- memberchk(b, [X,b]), X = a.
false.

?- X = a, memberchk(b, [X,b]).
X = a.

С другой стороны, во многих случаях memberchk/2 вызывается с достаточно интуитивными аргументами, где его можно рассматривать как эффективное приближение чистого отношения.

Одно из таких чистых отношений - memberd/2 (используя if_/3):

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs) ).

Существуют ли какие-либо другие чистые отношения, которые могут быть аппроксимированы memberchk/2 для достаточно инстанцированных случаев?

Другими словами: memberd/2 полная, декларативная замена для memberchk/2 или существуют ли законные случаи, когда memberchk/2 не может быть заменен на memberd/2?

4b9b3361

ОТВЕТЫ

Ответ 1

Вот пример использования member/2, который не может быть представлен memberd/2: bridge.pl проблема планирования моста предоставленный Паскалем Ван Хентенриком.

На этапе настройки member/2 используется:

setup(K,Ende,Disj):-
    jobs(L),
    make_vars(L,K),
    member([stop,_,Ende],K),
    ....

Таким образом, эффективно первый элемент в списке из трех элементов используется для выбора конкретной задачи, тогда как memberd/2 использует весь элемент для сравнения. Как следствие, это setup/3 оставляет открытым множество точек выбора (на самом деле, 219). Некоторые (например, SICStus) используют memberchk/2 в этой ситуации, тем самым рискуя немонотонностью.

Используя следующую чистую замену, все точки выбора избегают.

member3l([N,D,A], Plan) :-
   tmember(l3_t(N,D,A),  Plan).

l3_t(N,D,A, X, T) :-
   X = [Ni|_],
   if_(N = Ni, ( X=[N,D,A], T = true ), T = false ).

tmember(P_2, [X|Xs]) :-
   if_( call(P_2, X), true, tmember(P_2, Xs) ).

Альтернативно, используя library(lambda):

member3li([N,Nd,Na], Plan) :-
   tmember([N,Nd,Na]+\X^T^
       (  X=[Nk|_],
          if_( Nk = N, ( X=[N,Nd,Na], T = true ), T = false ) ),
      Plan).

Другие использования tmember/2:

old_member(X, Xs) :-
   tmember( X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberd(X, Xs) :-
   tmember(=(X), Xs).

Вот более компактное представление:

member3l([N,D,A], Plan) :-
   tmember({N,D,A}+\[Ni,Di,Ai]^cond_t(N = Ni, [D,A] = [Di,Ai] ), Plan).

Используя library(lambda) и cond_t/3:

cond_t(If_1, Then_0, T) :-
   if_(If_1, ( Then_0, T = true ), T = false ).

Ответ 2

Следующий ответ напрямую не связан с исходным вопросом относительно memberchk/2; вместо этого, это продолжение этого предыдущего ответа, в котором определяется meta-predicate tmember/2.

Мы предлагаем обобщение идиомы tmember/2 следующим образом:

t_non_empty_suffix(P_3, [X|Xs]) :-
   if_(call(P_3,Xs,X), true, t_non_empty_suffix(P_3,Xs)).

Основываясь на t_non_empty_suffix/2 и Prolog lambdas, мы можем определить tmemberX/2 следующим образом:

<Предварительно > : - use_module (библиотека (лямбда)). tmemberX (P_2, Xs): -  t_non_empty_suffix (P_2 +\_ ^ вызов (P_2), Xs).

Следующие old_memberX/2 и old_memberdX/2 используют tmemberX/2 вместо tmember/2:

old_memberX(X, Xs) :-
   tmemberX(X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberdX(X, Xs) :-
   tmemberX(=(X), Xs).

Сравним old_member/2 с old_memberX/2...

?- old_member(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

... и old_memberd/2 до old_memberdX/2!

?- old_memberd(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

ОК! Как определить old_member/old_memberd непосредственно на основе t_non_empty_suffix/2?

old_memberSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^T^( X = E, T = true ; T = false ), Xs).

old_memberdSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^( X = E ), Xs).

Выполняя запросы с этими предикатами, получим:

?- old_memberSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

Хорошо! Те же результаты, что и раньше.

Позвольте копать немного глубже! В качестве витрины для t_non_empty_suffix/2 рассмотрим duplicate_in/2.
Используя t_non_empty_suffix/2, Prolog lambdas, (=)/3, и memberd_t/3 мы определяем:

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

duplicate_in(X, Xs) :-
   t_non_empty_suffix(X+\Es^E^( X = E, memberd_t(E, Es) ), Xs).

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

?- duplicate_in(X, [1,2,3,2,3,4,3,4,5]).
  X = 2         % [1,2,3,2,3,4,3,4,5]    (2 occurs  twice)
; X = 3         % [1,2,3,2,3,4,3,4,5]    (3 occurs thrice)
; X = 4         % [1,2,3,2,3,4,3,4,5]    (4 occurs  twice)
; false.

Ответ 3

memberb/2 - типичный пример из конструктивного отрицания. Вы можете перевернуть требование вверх дном и, например, потребовать:

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

Где ~ будет конструктивное отрицание. Для обсуждения того, как конструктивное отрицание относится к if_ см., Например, здесь.

Недостатком полных декларативных индуктивных определений для члена /2 или того, что дизъюнкция Пролога (;)/2 не может упростить ограничений и что у Prolog нет forall, который также упростил бы ограничения, такие как diff/2.

Итак, в конце, когда вы сделаете это правильно с ограниченным (;)/2 и missig forall, вы получите в наилучшем случае полные решения, которые содержат множество избыточных ограничений, когда вы смотрите на полные решения, что интерпретатор будет производить.

Вот пример в Jekejeke Prolog, для этого требуется расширение Minlog для предиката diff/2:

:- use_module(library(term/diff)).
:- use_module(library(basic/lists)).
test(Y) :- diff(X, a), member(Y, [a,X]).

?- test(X).
X = a ;
diff([X], [a])

В приведенных выше двух ответах в основном говорят X = a или ~(X = a), которые в большинстве логик совпадают с одним ответом true.

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

Bye