Представление и обработка списков

Изучение представлений списков и пролог программ поиска элемента в списке, разделения и объединения списков, сортировки списка, удаления дубликатов в списке. Разработка пролог-программ обработки списков.

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

Список — упорядоченная последовательность элементов.

Список является набором объектов одного и того же доменного типа.

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

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

Пример.

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

[ 3.14, 3.62, 5.0, 3.14 ].

[ «RED», «BLUE», «GREEN» ].

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

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

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

• — первый элемент списка — голова;
• — остальная часть списка — хвост.

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

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

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

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

domains.

num = integer.

num_list = num*.

или:

domains.

num_list = integer*.

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

predicates.

number (…, num_list,…).

Работа со списками основана на расщеплении их на голову и хвост.

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

• — искомый элемент Х совпадает с головой списка
• — элемент Х принадлежит хвосту этого списка.

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

domains.

list = char*.

predicates.

member (list).

clauses.

member (X,[X|_]).

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

goal.

member ('A',['C','D','T','A','G']).

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

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

Достаточно часто требуется разделить список на несколько частей.

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

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 и 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).

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

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

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

Если исходный список пуст, то выходной тоже пуст. Пустой список по определению упорядочен. Если же входной список не пуст, то он предст…

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 (X, S1, S2).

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

cord (X, Y):-X>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].

Задание на лабораторную работу

• 1. Изучить способы обработки списков в Турбо-Прологе.
• 2. В соответствии с вариантом задания, определенным преподователем разработать и отладить пролог-программу задания.
• 3. Оформить отчет с указанием варианта задания, текстом программы и протоколом ее выполнения.