При определении рекурсивного предиката следует найти граничные условия и способ использования рекурсии. Первое граничное условие указывает на совпадение элемента Х с головой списка и успешное прекращение поиска, что и определяется первым правилом. Второе граничное условие встречается, когда второй аргумент предиката "принадлежит" является пустым списком. Каждый раз при поиске происходит рекурсивное обращение к предикату "принадлежит" и новая цель формируется для хвоста, т.е. всегда более короткого списка.
Теперь можно написать программу:
принадлежит(Х,[Х|_]).
принадпежит(Х,[_|Z) :- принадлежит(Х,Z).
На запрос
принадлежит(седло,[руль,рама,колесо,седло])
следует утвердительный ответ
Анализ списка неизвестной длины. Воспользуемся предикатом "принадлежит" для анализа принадлежности деталей, узлов велосипеда заданным узлам. Пусть имеется следующая БД:
узел([велосипед, рама, руль, седло, колесо]).
узел([колесо, обод, покрышка, камера, спицы,
втулка]).
детали(Х,Y) :- узел([Х|Z]), принадлежит(Y,Z).
принадлежит(Х,[Х]_|).
принадлежит(Х,|_Z) :- принадлежит(Х,Z).
Правило "детали" позволяет анализировать одну за другой детали узла, наименование которого задано первым в списке.
Выбор общих элементов в двух списках. Для выполнения этой процедуры достаточно потребовать, чтобы некоторый элемент принадлежал разным спискам, т.е.
общий(Х,Y,Z) :- принадлежит(Z,Х), принадлежит(Z,Y).
Выбор n-го элемента списка. Для выбора n-го элемента списка достаточно указать, что первый элемент списка имеет номер 1, т.е. на языке Пролог это выглядит следующим образом:
n(1 ,Элемент,[Элемент|_]).
Затем нужно определить рекурсивное правило, которое расчленяет список на элементы,. параллельно вычитая из заданного номера единицу до тех пор, пока не выполнится граничное условие, т.е. счетчик станет равным единице (первое правило). Сказанное описывается следующим правилом:
n(М, Элемент, [_|Список]) :- Счетчик = N - 1, n(Счетчик, Элемент, Список).
На запрос
n(3,X,[a,b,c,d,e])
получаем
Х=с
Приведем полную программу:
n(l, E, [E|_]).
n(N,E,[_|L]) :- C = N – 1, n(C, E, L).
Рассмотрим последовательность действий, выполняемых интерпретатором с целью получения решения. Здесь 3 - запрос, Н - найдено правило, У - унификация.
З n(З,E,[a,b,c,d]).
Н n(l,E,[E|_]). ошибка унификации
З n(З,E,[a,b.c,d]).
Н n(N,E,[_|L]) :- C = N - l, n(C,E,L).
У n(З,E,[a|b,c,d] :- 2 = З - l, n(2,E,[b,c,d])).
З n(2,E,[b,c,d]).
H n(l ,E,[E|_]). ошибка унификации: 2 !¹
З n(2,E,[b,c,d]).
H n(N,E,[_|L]) :- С = N - 1, n(С,Е, L).
У n(2,E,[b,c,d]) :- 1 = 2 - 1 ,n(1 ,E,[c,d]).
З n(l,E,[c,d]).
H n(l,E,[E|_]). успех: 1=1
У n(l,c,[c|d]).
следовательно, n(l, c,[c,d])
следовательно, n(2,c,[b,c,d])
следовательно, n(3,c,[a,b,c,d])
solution: E = c
Соединение двух списков. Как отмечалось выше, соединение двух списков с целью получения третьего осуществляется с помощью предиката " | ". Так, если
Х = [а,b,с], Y = [d,e,f] и Z = [X]Y], то Z=[a,b,c,d,e,f].
Процедуру присоединения списка Х к списку Y для получения списка Z интерпретатор рассматривает следующим образом:
присоединить [а, b, с] к [d, e, f], чтобы иметь [a,b,c,d,e,f]
это значит
присоединить [b,с] к [d,e,f], чтобы иметь [b,c,d,e,f]
это значит
присоединить [с] к [d,e,f], чтобы иметь [c,d,e,f]
это значит
присоединить [] к [d,e,f], чтобы иметь [d,e,f] (A)
значит присоединить [ ] к [d,e,f], получая [d,e,f|
значит присоединить [с] к [d,e,f|, получая [c,d,e,f]
значит присоединить [b,с] к [d,e,f], получая [b,c,d,e,f]
значит присоединить [а,b,с] к [d,e,f], получая [a,b,c,d,e,f]
Строка (А) выражает факт соединения пустого списка с некоторым списком L, в результате чего получается список L. Это записывается так:
присоединить ([ ],L,L).
В строках, предшествующих строке А, удаляют голову первого списка и присоединяют ко второму, чтобы получить третий список:
присоединить ([X|L1],L2, [X|L3]) :- присоединить(L1,L2,L3).
Функция присоединения является важной и в Прологе называется append. Напишем программу:
append([ ], L, L).
append([X|Ll], L2, [X|L3]) :- append(Ll,L2,L3).
На запрос append([a,b,c], [d,e,f], L) получим L = [a,b,c,d,e,f].
На запрос append([a,b,c], L, [a,b,c,d,e,f]) получим L = [d,e,f].
Другими словами, функция append позволяет составлять и расчленять список. Так, на запрос append(Ll, L2, [a,b,c,d])
получим
L1 |
L2 |
|
[ ] |
[a,b,c,d] |
|
[a] |
[b,c,d] |
|
[a,b] |
[c,d] |
|
[a,b,c] |
[d] |
|
[a,b,c,d] |
[ ] |
Здесь находятся все возможные списки, с помощью которых можно сформировать третий список.
Выбор наименьшего и наибольшего элементов списка. Можно сказать, что наименьший элемент списка, состоящего из одного элемента, является этим элементом, т.е.
меньший([Х], X).
Проанализируем список на каждом цикле, сравнивая два первых элемента и помещая наименьший на первое место. Программа имеет следующий вид:
меньший([Х], X).
меньший([Х,
Y|Z], R) :-
X <= Y, меньший([Х|Z], R);
X > Y, меньший([Y|Z], R).
Здесь сравниваются два первых элемента списка и меньший из элементов добавляется к оставшемуся подсписку.
На запрос меньший([b,c,a,e], X) получим Х=[а].
Выбор наибольшего элемента списка производится аналогично, только нужно заменить знак ">" знаком "<" и наоборот.
Перевод одного списка термов в другой. Предположим, требуется перевести (дословно) предложение с английского языка на русский. Заданы два списка слов с английскими и соответствующими им русскими словами. Чтобы остановить перевод предложения, воспользуемся тем, что пустой список переводится в пустой:
перевести([],[]).
очевидно, что этот факт действителен для всех языков. Далее запишем следующее правило:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.