Лекция №6 Операции над списками. Способи подання бази знань
Основные операции работы со списками.
На том занятии мы рассмотрели процедуру предназначенную для вывода на печать всех элементов списка. На этом занятии рассмотрим разные процедуры работы со списками.
Печать списка в обратном порядке
Процедура "обр-печать" почти идентична процедуре "печатать_злементы". Отличие состоит в том, что "обр_печать" выводит элементы списка на печать в обратном порядке. Это достигается за счет изменения Порядка следования подцелей в рекурсивном правиле, так что процедура становится леворекурсивной.
% условие окончания, когда список пуст.
обр_печать ([]). % 1)
% рекурсивное правило.
обр_печать ([Первый | Остаток]) :- 2)
обр_печать (Остаток), % рекурсивный вызов
write (Первый), nl. % вывод первого элемента
На рис. 2.2 изображено дерево доказательства, соответствующее этому запросу.
Примеры процедур, предназначенных для обработки списков
Процедура "элемент" имеет два аргумента. Вторым аргументом процедуры является список. Запрос к процедуре "элемент" даст положительный результат, если в качестве первого аргумента будет задан элемент, входящий в список.
Процедура "элемент"
% исходный случай: X является первым элементом списка.
элемент (X, [X ׀ Остаток] ). 1)
% X не является первым элементом списка, искать X в оставшейся части списка.
элемент (X. [Y ׀ Остаток]) :- 2)
элемент (X, Остаток).
Сделаем запрос: входит ли элемент b в список [а, Ь, с] ?
?- элемент (b, [a, b, с] ).
да
?— элемент (b, b).
нет
% выдать элементы списка:
?- элемент (X, [1,2,3]).
Х=1;
Х=2;
Х=3;
нет
Заметьте, что первым аргументом последнего запроса является переменная, которая поддается унификации со всем, что угодно. Этот запрос к процедуре "элемент" позволяет получить значения всех элементов списка, являющегося вторым аргументом процедуры.
Процедура "найти-слово"
Процедура "найти_слово" похожа на процедуру "элемент". Различие между ними заключается в том, что процедура "найти_слово" заканчивается либо когда список пуст, либо когда атом обнаружен в списке. Обратите внимание, как форма записи аргументов в заголовке каждой фразы используется для указания обстоятельств применения этой фразы.
% исходный случай № 1: список пуст
найти_слово (Слово, [ ]) :- % (1)
write (Слово),
write (' не найдено '), nl.
% исходный случай № 2: переменная Слово унифицируется с первым элементом списка
найти_слово (Слово, [Слово ׀ Остаток] ) %2)
% рекурсия, если переменная Слово не унифицируется с первым элементом списка
найти_слово (Слово, [Слово ׀ Остаток]) :- % 3)
найти-слово (Слово, Остаток).
Примеры запросов к процедуре "найти—слово".
- найти_слово (в, [находится, в, доме]).
да
?- найти_слово (лампа, [находится, в, доме] ).
лампа не найдено
да
?—найти_слово (X, [находится,в,доме]).
X = находится;
Х=в;
Х= доме
Процедура "присоединить"
Все три аргумента процедуры "присоединить" являются списками. Списки, задаваемые в первых двух аргументах, объединяются в один список, возвращаемый через третий аргумент. Процедуру "присоединить" можно также использовать для разбиения списка, представленного четвертым аргументом, на два подсписка. Процедура "присоединить" называется обратимой, так как все три ее аргумента — двунаправленные.
% исходный случай: первый аргумент — пустой список
присоединить ([],Список, Список). % (1)
% Взять элемент 1 из начала первого аргумента и поместить его в начало третьего аргумента, либо выполнить обратное действие:
присоединить ([X׀Список1], Список2, [X ׀ СписокЗ]) :- % (2)
присоединить (Список1, Список2, СписокЗ).
?-присоединить ([а, b, с], [1, 2], Y).
Y=[a,b,c, 1,2]
?- Присоединить ([a], X, [a, z, m, n] ).
X = [z, m, n]
?-присоединить (А, В, [1,2,3]).
A=[]
B =[1,2, 3];
A=[1]
B=[2,3];
A=[1,2]
В=[3],
A=[1,2,3]
B=[]
нет
Процедура "длина"
Первым аргументом процедуры "длина" является список, а через второй аргумент дання процедура возвращает длину этого списка.
% исходный случай - в пустом списке нуль элементов.
длина ([].0). % 1)
длина ([F I R], N) :- % 2)
длина (R, N1),
N is Nl+ 1.
?- длина ([альфа,бета,гамма],Дл).
Дл - 3
?- длина ([[а,b],Х],Дл).
Дл=2