|
НАЗАД
Предикат add(X,Y,Z) истинен, если список Z получается добавлением терма Х в начало списка Y. Схема отношения этого предиката имеет вид:
add(<терм>,<список>,<список>).
Декларативное описание предиката add формулируется следующим образом:
«Терм X является головой списка Z, а список Y¾ хвостом списка Z».
Процедура add(X,Y,Z) состоит из факта:
add(X,Y,[X|Y]).
Удаление элемента (предикат delete)
Удаление элемента X из списка L можно запрограммировать в виде отношения
delete( X, L, M)
где M совпадает со списком L, у которого удален элемент X.
Предикат delete(X,L,M) принимает значение “истина”, если список M получается в результате удаления первого вхождения терма Х из списка L. Схема отношения этого предиката имеет вид:
delete(<терм>,<список>,<список>).
Декларативное описание предиката next формулируется следующим образом:
Если X ¾ голова списка L, то предикат delete(X,L, M) истинен и M есть хвост списка L.
Если X принадлежит хвосту списка, то предикат delete необходимо применить к хвосту списка L.
Если X не принадлежит списку L, то предикат delete(X,L, M) ложен.
Процедура delete(X,Y,L) состоит из двух правил:
delete(X,[X|B],B):¾!. %Пр.1
delete(X,[Y|L],[Y|M]):¾ delete(X,L,M). %Пр.2
Рассмотрим пример запроса к процедуре delete(X,Y,L).
? ¾ delete(3,[1,2,3,4],M).
ТР: delete(3,[1,2,3,4],M).
Шаг 1: ТЦ: delete(3,[1,2,3,4],M).
Пр1: delete(3,[1|2,3,4]],M) Þ неуспех (3 не сопоставимо с 1)
Пр2: delete(3,[1|[2,3,4]],[1|M1]):¾ delete(3,[2,3,4],M1).
M=[1|M1]
ТР: delete(3,[2,3,4],M1).
Шаг 2: ТЦ: delete(3,[2,3,4],M2).
Пр1: delete(3,[2|[3,4]],M2) Þ неуспех (3 не сопоставимо с 2)
Пр2: delete(3,[2|[3,4]],[2|M2]):¾ delete(3,[3,4],M2).
M1=[2|M2]
ТР: delete(3,[3,4],M2).
Шаг 3: ТЦ: delete(3,[3,4],M2).
Пр1: delete(3,[3|[4]], M2) Þ успех (3 сопоставимо с 3)
при подстановке M2=[4]
Переход на шаг 2, и конкретизация переменной M1 значением [2|[4]] или [2,4].
Переход на шаг 1, и конкретизация переменной M значением [1|[2,4]] или [1,2,4].
ТР: .
Результат вычисления запроса: delete(3,[1,2,3,4],M). ¾ успех при подстановке {M=[1,2,4]}.
Как и member, отношение delete по природе своей недетерминировано. Если в списке встречается несколько вхождений элемента X, то удалить сможет исключить их все при помощи возвратов. Конечно, вычисление по каждой альтернативе будет удалять лишь одно вхождение X, оставляя остальные в неприкосновенности. Например:
?- delete ( a, [a,b,a,a], L].
L = [b,а,а];
L = [а,b,а];
L = [а,b,а];
по (нет)
При попытке исключить элемент, не содержащийся в списке, отношение удалить потерпит неудачу.
Отношение delete можно использовать в обратном направлении для того, чтобы добавлять элементы в список, вставляя их в произвольные места. Например, если мы хотим во все возможные места списка [1,2,3] вставить атом а, то мы можем это сделать, задав вопрос: «Каким должен быть список L, чтобы после удаления из него элемента а получился список [1,2,3]?»
?- delete ( a, L, [1,2,3] ).
L = [а,1,2,3];
L = [1,а,2,3];
L = [1,2,а,3];
L = [1,2,3,а];
по (нет)
Вообще операция по внесению X в произвольное место некоторого списка Список, дающее в результате БольшийСписок, может быть определена предложением:
внести( X, Список, БольшийСписок) :-удалить( X, БольшийСписок, Список).
В member1 мы изящно реализовали отношение принадлежности через append. Для проверки на принадлежность можно также использовать и delete. Идея простая: некоторый X принадлежит списку Spisok, если X можно из него удалить:
member2(X, Spisok) :- delete ( Х, Spisok, _).
НАЗАД
|
