Обработка списков и строк символов

Список в Прологе представляется множеством элементов, разделенных запятой и ограниченных квадратными скобками.

Так, X=[a,b,c,d] является списком из четырех элементов.

Для разделения списка на части используется предикат "|" (вертикальная черта). Этот предикат разделяет список на голову и хвост. Головой списка может быть его первый элемент, тогда хвост списка есть подсписок, состоящий из всего списка за исключением его первого элемента. Так, если X=[a,b,c,d] и X=[Y|Z], то Y=a и Z=[b,c,d]. Заметим, что в случае списка, состоящего из одного элемента, Х=[а] и X=[Y|Z], тогда Y=a и Z=[ ]-пустой список, который обозначают открывающей и закрывающей квадратными скобками. Поскольку список делится на части, то его можно составлять из отдельных частей. Так, например, из одного элемента и списка можно получить новый список.

Пусть: 1) Х=а, Y=[b,c,d] и Z=[X|Y], тогда Z=[a,b,c,d] и 2) Х=а, Y=b, тогда Z=[a|b], а не Z=[a,b]. В первом случае Y - список, а во втором Y - элемент. Таким образом, соединение двух элементов дает список, состоящий из элемента и подсписка, а не из двух элементов.

Далее в этом параграфе рассмотрим процедуры работы со списками. Во многих случаях, чтобы упростить изложение, будем приводить только часть clauses Пролог-программ.

Принадлежность элемента списку. Предположим, что имеется список наименований деталей велосипеда: руль, рама, колесо, седло, и нужно определить, содержится ли некоторая деталь, например "седло", в данном списке.

Очевидно, что если элемент принадлежит списку, то он либо совпадает с головой списка, либо находится в его хвосте. Следовательно, прежде всего необходимо сравнить искомый элемент с головой заданного списка. В случае несовпадения аналогичные действия рекурсивно повторяются для списка-хвоста. Поиск завершается неудачей, если достигнут конец исходного списка.

Принадлежность элемента X списку Y можно записать в виде предиката "принадлежит(Х,У)". Для определения истинности этого предиката требуется проверить два условия. Первое состоит в проверке совпадения X с головой списка X, что записывается на языке Пролог следующим образом:

принадлежит(Х,[Х|_]).

Для обозначения хвоста списка здесь используется анонимная переменная "_". Данный факт можно записать в виде правила:

принадлежит(Х,[Y|_]) :- X=Y.

Для определения принадлежности элемента X хвосту списка будем использовать тот же предикат "принадлежит", в чем и заключается суть рекурсии. На Прологе это записывается правилом

принадлежит(Х,[_|Y]) :- принадлежит(Х,Y).

что означает: "X является элементом списка, если X является элементом хвоста списка". В качестве головы списка применялась анонимная переменная, так как ее имя значения не имеет.

При определении рекурсивного предиката следует найти граничные условия и способ использования рекурсии. Первое граничное условие указывает на совпадение элемента X с головой списка и успешное прекращение поиска, что и определяется первым правилом. Второе граничное условие встречается, когда второй аргумент предиката "принадлежит" является пустым списком. Каждый раз при поиске происходит рекурсивное обращение к предикату "принадлежит" и новая цель формируется для хвоста, т.е. всегда более короткого списка.

Теперь можно написать программу:

принадлежит(Х,[Х|_]).

принадлежит(Х,[_|Z) :-

принадлежит(Х,Z).

На запрос

принадлежит(седло,[руль,рама,колесо,седло])

следует утвердительный ответ.

Анализ списка неизвестной длины. Воспользуемся предикатом "принадлежит" для анализа принадлежности деталей, узлов велосипеда заданным узлам. Пусть имеется следующая БД:

узел([велосипед,рама,руль,седло,колесо]). узел([колесо,обод,покрышка,камера,спицы, втулка]).

детали(Х,У) :-

узел([Х|Z]),

принадлежит(Y,Z).

принадлежит(Х,[Х|_]).

принадлежит(Х,[_|Z]) :-

принадлежит(Х,Z).

Правило "детали" позволяет анализировать одну за другой детали узла, наименование которого задано первым в списке.

Выбор общих элементов в двух списках. Для выполнения этой процедуры достаточно потребовать, чтобы некоторый элемент принадлежал разным спискам, т.е.

общий(Х,Y,Z) :-

принадлежит(Z,Х),

принадлежит(Z,Y).

Выбор n-го элемента списка. Для выбора n-го элемента списка достаточно указать, что первый элемент списка имеет номер 1, т.е. на языке Пролог это выглядит следующим образом:

n(1,Элемент,[Элемент|_]).

Затем нужно определить рекурсивное правило, которое расчленяет список на элементы, параллельно вычитая из заданного номера единицу до тех пор, пока не выполнится граничное условие, т.е. счетчик станет равным единице (первое правило). Сказанное описывается следующим правилом:

n(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(3,E,[a,b,c,d]).

Н n(1,Е,[Е|_]). ошибка унификации: 3≠1

З n(3,E,[a,b,c,d]).

Н n(N,E,[_|L]) :- C=N-1,n(C,E,L).

У n(3,E,[a|b,c,d] :- 2=3-1,n(2,E,[b,c,d])).

З n(2,E,[b,c,d]).

H n(1,E,[E|_]). ошибка унификации: 2≠1

З n(2,E,[b,c,d]).

Н n(N,E,[_|L]) :- C=N-1,n(C,E,L).

У n(2,E,[b,c,d]) :- 1 =2-1,n(1,E,[c,d]).

З n(1,E,[c,d]).

H n(1,E,[E|_]). успех: 1=1

У n(1,c,[c|d]).

следовательно, n(l,c,[c,d])

следовательно, n(2,c,[b,c,d])

следовательно, n(3,c,[a,b,c,d])

solution: E=c

Выбор наименьшего и наибольшего элементов списка. Можно сказать, что наименьший элемент списка, состоящего из одного элемента, является этим элементом, т.е.

меньший([Х], X).

Проанализируем список на каждом цикле, сравнивая два первых элемента и помещая наименьший на первое место. Программа имеет следующий вид:

меньший([Х], X).

меньший([Х,Y|Z], R) :-

X<=Y,

меньший([Х|Z], R);

X>Y,

меньший([У|Z], R).

Здесь сравниваются два первых элемента списка и меньший из элементов добавляется к оставшемуся подсписку.

На запрос

меньший([b,с,а,е], X)

получим

Х=[а].

Выбор наибольшего элемента списка производится аналогично, только нужно заменить знак ">" знаком "<" и наоборот.

Перевод одного списка термов в другой. Предположим, требуется перевести (дословно) предложение с английского языка на русский. Заданы два списка слов с английскими и соответствующими им русскими словами. Чтобы остановить перевод предложения, воспользуемся тем, что пустой список переводится в пустой:

перевести([], []).

Очевидно, что этот факт действителен для всех языков. Далее запишем следующее правило:

перевести([С_А|Ф_А], [С_Р|Ф_Р]) :-

словарь(С_А, С_Р),

перевести(Ф_А, Ф_Р).

Это правило интерпретируется следующим образом: чтобы перевести фразу с английского на русский, выбирают ее первый элемент (слово С_А), находят в словаре соответствующее русское слово (С_Р), которое добавляют в начало русской фразы.

Далее с помощью рекурсии осуществляют перевод оставшейся части фразы. Естественно, что для работы программы требуется создать англо-русский словарь. Полная программа имеет следующий вид:

domains

список=symbol*

predicates

перевести (список, список)

словарь (symbol, symbol)

clauses

перевести ([], []).

перевести ([С_А|Ф_А], [С_Р|Ф_Р]):-

словарь (С_А, С_Р),

перевести (Ф_А, Ф_Р).

словарь ("I',"я").

словарь ("study","изучаю").

словарь ("language","язык").

словарь ("PROLOG","Пролог").

словарь ("in","в").

словарь ("the university","университете").

На запрос

перевести (["I","study","language","PROLOG","in","the university"],P)

получим

Р=["Я","изучаю","язык","Пролог","в","университете"]

Можно также задать обратный запрос:

перевести(Р,["Я","изучаю","язык","Пролог","в","университете"])

и на экране получим соответствующую английскую фразу.

Вполне понятно, что такой перевод не является совершенным. Пополняя словарь, можно получить множество русских фраз, соответствующих английской фразе. Для выбора правильной фразы требуется использовать правила грамматики, семантический анализ полученных фраз. Следует напомнить, что язык Пролог появился как средство исследования естественных языков.

Удаление заданного элемента из списка. Для выполнения этой операции достаточно соблюдать два правила:

1) если удаляемый элемент совпадает с головой списка, то надо оставить хвост списка. Это записывается так:

удалить (Е, [E|Y], Y).

В первом правиле если Е – элемент для удаления и Е – голова списка, то сохраняется хвост списка Y;

2) если удаляемый элемент не совпадает с головой списка, то надо найти его в хвосте списка и удалить. Это можно записать таким образом:

удалить(Е, [X|Y], [X|Z]): -

удалить(Е,Y,Z).

Из второго правила следует, что если Е – элемент для удаления и [X|Y] – исходный список, то нужно анализировать подсписок Y на предмет наличия в нем искомого элемента.

Программа имеет следующий вид:

удалить(Е, [Е|Y], Y).

удалить(E,[E,Y],[X|Z]) :-

удалить(Е, Y, Z).

Сортировка элементов списка. Рассмотрим простую сортировку элементов с помощью метода последовательного сравнения смежных элементов. По данному методу в списке находят наименьший элемент, если сортировка по возрастанию (или наибольший, если по убыванию), добавляют его в голову другого списка и удаляют из первого списка. Далее этот процесс продолжают с оставшимся первым списком до исчезновения в нем элементов.

Таким образом, окончание сортировки можно представить в виде

сортировать([ ], [ ]).

Выбор наименьшего М в исходном списке L, удаление М из L, сортировка оставшегося списка Q и получение результата в списке R можно представить следующим правилом:

сортировать(L,[M|R]) :-

меньший(L,М),

удалить(М,L,Q),

сортировать(Q,R),

!.

На запрос

сортировать([е, t, r, a, b], S)

получим

S=[“a”, “b”, “e”, “r”, “t”]