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

Question

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?

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

Answer 2

Следующий ответ не имеет прямого отношения к исходному вопросу о memberchk/2; вместо этого, это продолжение этого предыдущего ответа, который определил мета-предикат 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 и пролог лямбда, мы можем определить tmemberX/2 вот так:

: - use_module ( библиотека (лямбда)).

tmemberX (P_2, Xs): -
   t_non_empty_suffix (P_2 + \ _ ^ call (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 Пролог лямбда, (=)/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]).
  Х = 2% [1, 2, 3, 2, 3,4,3,4,5] (2 встречается дважды); Х = 3% [1, 2, 3, 2, 3, 4, 3, 4,5] (3 встречается трижды); Х = 4% [1,2,3,2,3, 4, 3, 4, 5] (4 встречается дважды); ложный.

Answer 3

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

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

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

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

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

Вот пример в 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,

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

до свидания