Краткие теоретические сведения. 2.1 Турбо-Пролог и списки

2.1 Турбо-Пролог и списки

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

Элементы списка заключаются в квадратные скобки [], а друг от друга отделяются запятыми. Пример:

[ 3, 8, 24, 38, 4, 2, 3, 3 ]

[ 3.14, 3.82, 5.0, 3.14 ]

["RED"; "BLUE", "GRЕЕN"]

Объекты списка называются элементами списка. Длина списка количество элементов в списке. Список может содержать произвольное число элементов, единственным ограничением является лишь объем оперативной памяти.

Список, не содержащий элементов, называется пустым, или нулевым списком, и обозначается [].

Непустой список можно рассматривать как состоящий из двух частей:

- первый элемент списка - голова;

- остальная часть списка - хвост.

Голова является элементом списка, хвост есть список сам по себе. Голова --это отдельное неделимое значение. Наоборот, хвост представляет собой список, составленный из того,что осталось от исходного списка в результате отделения головы. Этот новый список можно делить и дальше.

Примеры разделения списков на голову и хвост приведены в таблице 2

Таблица 2

Список	Тип списка	Голова	Хвост
[1, 2, 3, 19]	Целые числа		[2, 3, 19]
['S', 'J', 'K']	Символы	'S'	['J', 'K']
[''CARS'']	Строки	''CARS''	[]
[]	-	Не определен	Не определен

2.2 Применение списков

В Пролог - программе для использования в программе списка необходимо предварительно описать домен и предикат списка.

Описание домена списка производится в разделе domains с указанием звездочки * после имени типа элемента списка.

domains

num = integer

num_list = num*

или:

domains

num_list = integer*

В разделе описания предикатов predicates требуется присутствие предиката списка. Если одним из его аргументов является список, то за именем этого предиката в круглых скобках указывается имя домена списка на месте соответствующего аргумента

predicates

number(..., num_list, ...).

Работа со списками основана на расщеплении их на голову и хвост. Операция деления списка на голову и хвост обозначается при помощи вертикальной черты '|' : [ Н | Т ] (Голова | Хвост)).

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

2.3 Операции отсечения

Турбо-Пролог имеет встроенную операцию отсечения, которая позволяет управлять механизмом возврата (перебора). Операция записывается с помощью восклицательного знака ('!') Отсечение трактуется как псевдоцель, которая всегда выполняется успешно. Если операция отсечения встречается в одном из предложений процедуры, то после ее выполнения предотвращается возврат к предыдущим подцелям предложении, то есть фиксируются выбранные решения для этих подцелей и остальные альтернативы не рассматриваются. Так, пусть имеется процедура А:

А:-Р, Q, !, S, T.

А:-R.

где А, Р, Q, R, S, Т - предикаты.

Отсечение повлияет на вычисление цели А следующим образом. Перебор будет возможен в списке подцелей Р, Q; однако, как только точка отсечения будет достигнута, найденные решения для подцелей P и Q фиксируются и все альтернативные решения для них не рассматриваются. Альтернативное предложение, входящее в процедуру: А:-R. также не будет учитываться. Тем не менее, возврат(перебор) будет возможен в списке подцелей S, Т.

Отсечение, повышая выразительность языка, дает возможность проще формулировать взаимно исключающие утверждения и повышает эффективность работы программы. Так, фрагмент программы, вычисляющий значение функции

Выглядит следующим образом:

- без использования отсечения

F(X, Y):-X<1, Y=sin(X)

F(X, Y):-1<=X, X<3, Y=cos(X)

F(X, Y):-X>=3, Y=X*X

-с использованием отсечения

F(X, Y):- X<1, !, Y=sin(X)

F(X, Y):- X<3, !, Y=cos(X)

F(X, Y):- Y=X*X

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

2.4 Операция над списками

2.4.1 Поиск элемента в списке

Поиск представляет собой просмотр списка на предмет выявления соответствия между элементом данных и элементами просматриваемого списка. Результатом поиска, также как и результат любой другой операции Турбо-Пролога, базирующейся на унификации, всегда бывает либо успех, либо неуспех. Для сопоставления объекта поиска с элементами просматриваемого списка необходим предикат, аргументами которого являются и объект поиска и список:

rnember( 6, [ 3, 8, 6, 4, 2 ] ).

Для того, чтобы выяснить, является ли какой-либо элемент членом списка, необходимо установить, эквивалентен ли он голове списка, а если нет, то не является ли он членом хвоста списка, то есть для организации поиска необходима проверка двух условий:

- искомый элемент Х совпадает с головой списка:

member(Х, [Х | _ ]). (или member(Х, [Y | _ ]):-X=Y);

- элемент Х принадлежит хвосту этого списка:

member(X, [ _ | Y]):- member(X,Y).

Пример. Установить: существует ли в заданном списке символ 'А'

domains

list = char*

predicates

member(list).

clauses

member(X,[Х | _])

member(X,[ _ | T]):- member(X, T).

goal

member('А',['С','D',Т,'А', 'G']).

Ответом будет 'yes'.

2.4.2 Разделение списка

Достаточно часто требуется разделить список на несколько частей. В случае деления исходного списка L на список L1 (например, для которого элементы меньше значения М) и L2 (например, значение элементов больше или равно М) вводится следующий предикат:

del(M, L, L1, L2)

Организуется правило для разделения: очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом сравнивается с M.

Пример. Исходный список разделить на два списка по условию

L1, если X < M

Х принадлежит

L2, если X >= M

domains

list = integer*

predicates

del(integer, list, list, list).

clauses

del(M [H | T], [H | L1], L2):-H<M

del(M, T, L1, L2)

del(M [H | T], L1, [H | L2]):-H>=M

del(M, T, L1, L2)

del(_, [], [], [])

goal

del(8[1, 2, 13, 4, 5, 12, 18, 2, 12] L1, L2)

Результатом будет значения L1=[1, 2, 4, 5, 2] и L2=[13, 12, 18, 12]

2.4.3 Объединение списков

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

Пример. Объединить исходные списки L1 и L2 в выходной список L3.

domains

list = integer*

predicates

append(list, list, list).

clauses

append([],L, L).

append([N | L1], L2, [N | L3]):-append(L1, L2, L3).

goal

append([1,2,3], [3,4,5], L)

Результатом работы программы будет список L=[1, 2, 3, 3, 4, 5].

2.4.4 Сортировка списка

Сортировка представляет собой упорядочивание элементов списка определенным образом

Наиболее удобным для реализации на Турбо-Прологе методом является вставки. Метод реалиэуется при помощи неоднократной вставки элементов в список до тех пор, пока он не будет упорядочен. Предикат сортировки определяется как

sort(S1,S2),

где S1 - исходный (несортированный) список;

S2 - выходной (отсортированный) список.

Если исходный список пуст, то выходной тоже пуст. Пустой список по определению упорядочен, Если же входной список не пуст, то он представляется в виде головы и хвоста списки. Хвост списка сортируется при помощи рекурсивного обращения к sort. Выходной список формируется путем вставки головы списка в отсортированный хвост списка так, чтобы итоговый список был упорядоченным. Вставка осуществляется с помощью предиката:

rel(X, S1,S2).

где Х - вставляемый элемент;

S1 - отсортированный список, в который вставляется элемент Х;

S2 - отсортированный список, в котором уже присутствует элемент Х.

Если S1 не пустой список, то его можно представить в виде головы и хвоста списка. Предполагая, что элемент Х вставляется в начало списка S1, проверяется удовлетворяют ли элемент Х и голова списка условию упорядоченности. Если условие нарушено (в этом случае предикат cord выполняется), то элемент Х вставляется в хвост списка с помощью рекурсивного обращения к предикату rel. Если же условие упорядоченности выполнено (в этом случае предикат cord не выполняется), то происходит переход ко второму предложению процедуры rel, которое осуществляет формирование выходного списка S2 путем вставки элемента Х в начало списка S1. Переход ко второму предложению происходит только тогда, когда предикат cord не выполняется, так как используется операция отсечения ('|') после cord, или же когда список S1 пустой, либо в этом случае выходной список должен состоять из одного вставляемого элемента Х.

Пример. Произвести сортировку списка целых чисел в порядке убывания.

domains

number = integer

list = integer

predicates

sort(list, list).

cord(number, number).

rel(number, list, list).

clauses

sort([], []).

sort(([X | T], S1):=sort(T,S2), rel(X, S2, S1).

rel(X, [Y | S1], [Y | S2]):-cord(X, Y), rel(S1, S2).

rel(X,S1, [ X | S1]).

cord(Х, Y):-Х>Y.

goal

sort([3, 6, 2, 9], S).

Результатом будет список S=[2,3,6,9].

При работе со списками нередко возникают списки с дублирующими элементами. В связи с этим появляется задача удаления дубликатов из списка. Для ее решения можно предложить следующий предикат:

delete(S1,S2),

где S1 - исходный список, возможно, содержащий дубликаты;

S2- выходной список без дублирующих элементов.

Если исходный список пустой, то выходной тоже пуст. Если же исходный список не пустой, то он представляется в виде головы и хвоста списка и проверяется, принадлежит ли голова списка хвосту. Если да, то это значит, что в хвосте есть дубликат головы, и тогда выходной список формируется из хвоста списка. Если же нет, то это значит, что голова дубликатов не имеет. И тогда, и только тогда (ибо использована операция отсечения ('|')) происходит переход ко второму предложению, включающему голову списка в выходной список и формирующему хвост выходного списка из хвоста исходного списка. Для проверки принадлежности элемента хвосту списка используется уже описанный ранее предикат member.

Пример. Удалить из списка. дубликаты элементов.

domains

listsymb=symbol*

predicates

delete(listsymb, listsymb).

member(symbol, listsymb).

clauses

delete([], []).

delete([X | S1], S2):-member(X, S1), !, delete(S1, S2)

delete([X | S1], [X|S2]):-delete(S1, S2)

member(X, [X | _]).

member(X, [_ | T]):-member(X, T)

goal

delete([tom, mary, tom, pat, pat, tom], L)

Результатом будет список L=[mary, pat, tom].