Давайте сначала подумаем логически о том, что значит быть «соседями» в списке: в каких случаях A и B являются соседними элементами в списке?
Ответ. Если список имеет форму [...,X,Y,...] и выполняется хотя бы одно из следующих условий:
A = X и B = YA = Y и B = X.
Логически: ( A = X B = Y) (A = Y B = X).
Мы хотим сформулировать противоположное этому, то есть формулу отрицательного:
( ( A = X B = Y) (A = Y B = X))
( A = X B = Y) (A = Y B = X)
( A = X B = Y) ( A = Y B = X)
(A X B Y) (A Y B X)
Кто бы мог подумать, что законы Де Моргана имеют практическое применение, верно?
Чтобы указать X Y в Прологе, мы используем мощное ограничение dif/2, как уже предложил @CapelliC. dif/2 истинно, если и только если его аргументы являются другими терминами. Это чистый предикат, который корректно работает во всех направлениях. Если ваша система Prolog еще не предоставляет его, обязательно сообщите своему поставщику, что он вам нужен! До тех пор вы можете аппроксимировать его с помощью iso_dif/2, если это необходимо.
Таким образом, в Прологе приведенное выше становится:
( dif(A, X) ; dif(B, Y) ), ( dif(A, Y) ; dif(B, X) )
потому что (',')/2 обозначает союз, а (;)/2 обозначает дизъюнкт.
Итак, у нас есть:
not_neighbours(_, _, []).
not_neighbours(_, _, [_]).
not_neighbours(A, B, [X,Y|Rest]) :-
( dif(A, X) ; dif(B, Y) ),
( dif(A, Y) ; dif(B, X) ),
not_neighbours(A, B, [Y|Rest]).
Несколько тестовых случаев делают нас более уверенными в правильности предиката:
?- not_neighbours(a, b, [a,b]).
false.
?- not_neighbours(A, B, [A,B]).
false.
?- not_neighbours(A, B, [_,A,B|_]).
false.
?- not_neighbours(A, B, [_,B,A|_]).
false.
?- not_neighbours(a, b, [_,a,c,_]).
true .
Обратите внимание, что это определение работает правильно и в том случае, если все аргументы являются переменными, что мы называем наиболее общим случаем.
Недостатком этого решения является то, что (;)/2 создает множество альтернатив, и многие из них вообще не имеют значения. Мы можем сделать это значительно более эффективным с помощью другой алгебраической эквивалентности, которая позволяет нам избавиться от ненужных альтернатив:
А Б А Б
Итак, в нашем случае мы можем написать (A = X B = Y) как A = X BY.
Мы можем выразить применение в Прологе с помощью мощного if_/3 метапредикат:
impl(A, B) :- if_(A, B, true).
И поэтому мы можем декларативно эквивалентно записать наше решение как:
not_neighbours(_, _, []).
not_neighbours(_, _, [_]).
not_neighbours(A, B, [X,Y|Rest]) :-
impl(A=X, dif(B, Y)),
impl(B=X, dif(A, Y)),
not_neighbours(A, B, [Y|Rest]).
Пример запроса:
?- not_neighbours(a, b, [x,y]).
true ;
false.
И более общий случай:
?- not_neighbours(a, b, [X,Y]).
X = a,
dif(Y, b) ;
X = b,
dif(Y, a) ;
dif(X, b),
dif(X, a) ;
false.
Вы можете использовать этот предикат для проверки и генерации ответов. Попробуйте, например, итеративное углубление, чтобы справедливо перечислить все ответы:
?- length(Ls, _), not_neighbours(A, B, Ls).
Примечательно, что чисто логические рассуждения привели нас к общей и эффективной программе на Прологе.
dif/2 может сначала показаться вам необычным, потому что он появился в самой первой системе Prolog, а затем какое-то время игнорировался некоторыми производителями. В настоящее время dif/2 становится доступным (снова) во все большем количестве реализаций в качестве важного встроенного предиката, который позволяет вам декларативно заявить, что два термина различны. Массивной путаницы, которую его нечистые альтернативы обычно вызывают в курсах Пролога, можно избежать с помощью dif/2.
person
mat
schedule
05.09.2016
