Блог

Мне нужен предикат для определения того, есть ли элемент в списке. Я пытался использовать member / 2, но заметил странное поведение.

Когда я вызываю что-то вроде member(1, [1, 2, 3]). SWI-prolog выводит true и ждет, пока я нажму enter, прежде чем выполнение завершится. Этого не происходит, когда элемента нет в списке.

У меня есть два вопроса:

1. Почему это происходит?
2. Каким будет код для member / 2, который вернется немедленно?

1. Почему это происходит?

Определение member/2 позволяет выполнить несколько раз, даже если найдено одно и то же решение. В вашем списке все элементы были разными. Но рассмотрим случай с двумя дополнительными вхождениями 1 в конце:

 ?- member(1,[1,2,3,1,1]).
   true
;  true
;  true.
  

2. Каким будет код для member / 2, который вернется немедленно?

Это обычно вызывается memberd/2 .

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

?- memberd(X,[1,2,3,1,1]).
   X = 1
;  X = 2
;  X = 3
;  false.
  

Разницу легко понять. member/2 по существу определяется как:

 member(X, [X|_Xs]).
member(E, [_X|Xs]) :-
   member(E, Xs).
  

Обратите внимание, что эти два предложения не являются взаимоисключающими! Это причина, по которой он ищет альтернативные решения, даже если решение уже найдено. В правиле the E и the _X могут быть идентичными.

Убедившись, что E и X отличаются в правиле, мы получаем первое определение memberd/2 :

 memberd(X, [X|_Xs]).
memberd(E, [X|Xs]) :-
   dif(E, X),
   memberd(E, Xs).
  

Благодаря этому dif/2 правило учитывается только в том случае, если текущий элемент отличается от E . Однако здесь не хватает того, что Prolog все равно придется рассмотреть оба, прежде чем сделать вывод, что они не пересекаются.

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

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

При использовании library(reif)
для
SICSTU и
SWI это расширяется до:

 memberd(X, [E|Es]) :-
    (   X=E
    ->  memberd(X, Es)
    ;   X==E
    ->  true
    ;   X=E,
        true
    ;   dif(X, E),
        memberd(X, Es)
    ).
  

Это альтернативный ответ на второй вопрос.

2. Каким будет код для member / 2, который вернется немедленно?

Если вы хотите только проверить, является ли X это членом Es , и оба являются основаниями, вы можете использовать

 memberchk(X, Es).
  

memberchk/2 является встроенным в SWI-Prolog, но если бы это было не так, вы могли бы определить его как

 memberchk(X, Es) :-
    member(X, Es),
    !.
  

Cut ( ! ) после member/2 вызова сообщает Prolog забыть о любых других вариантах, которые вызов мог бы еще попробовать.

Ваш пример выполняется детерминированно (немедленно):

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

Но обратите внимание, что memberchk/2 это сильно отличается от member/2 . Например:

 ?- findall(X, member(X, [1, 2, 3]), Xs).
Xs = [1, 2, 3].

?- findall(X, memberchk(X, [1, 2, 3]), Xs).
Xs = [1].