Лебедева Н.С. Методическое пособие по программированию на Turbo Prolog
Подождите немного. Документ загружается.
31
4. Списки
4.1. Введение
Списки – это упорядоченная последовательность объектов, произ-
вольной длины. Единственное ограничение – объем оперативной
памяти. Признак “упорядоченный” указывает на то, что порядок
элементов является существенным.
Список – это динамическая структура данных. Объекты списка
называются элементами. Элементы списка заключаются в квадратные
скобки [ ] и разделяются запятыми. Те же самые элементы списка,
упорядоченные иным способом, представляют уже совсем другой
список. Порядок играет важную роль в процессе сопоставления списков.
Например, имеем два списка
[a, b, c] и [b, a, c].
Данные списки различны.
Список – последовательность элементов одного и того же доменного
типа. Количество элементов в списке называется длиной списка. Список, не
содержащий элементов называется пустым или нулевым и обозначается [ ].
Турбо-Пролог позволяет работать как со списком в целом, так и с
отдельными элементами списка.
Внутренние унификационные подпрограммы позволяют отделить от
списка первый элемент и обрабатывать его отдельно. Данный метод
работает вне зависимости от длины списка до тех пор, пока список не будет
исчерпан. Этот метод доступа к голове списка называется методом
разделения списка на голову и хвост и является основным методом работы
со списками.
Любой список L есть либо пустой список L = [ ], либо список из 2-х
частей головы и хвоста L = [Head | Tail]. Голова отделяется от хвоста
разделителем ''|'':
''|'' – операция деления списка на голову и хвост;
Голова – первый элемент списка;
Хвост – остальная часть списка, которая может делится и дальше на
голову и хвост.
Например, имеем список L = [a, b, c], где
a – голова списка L,
L1 = [b, c] – хвост списка L, который делится на
b – голова списка L1,
L2 = [c] – хвост списка L1, который делится на
c – голова списка L2
L3 = [] – хвост списка L2.
32
Список задается в разделе domains путем добавления в конец
домена символа ''*''.
Например.
domains
list_int = integer *
задает домен list_int, который является списком целых чисел.
Основной прием построения алгоритмов работы со списками –
составление процедуры, состоящей из двух правил: рекурсивного
правила работы с головой и хвостом списка и правила работы с
пустым списком.
Список – это такая структура данных, которая помогает сделать
программу компактной, эффективной и легко управляемой.
Списки используются для представления множеств, при создании
баз данных, экспертных систем, словарей и т. д.
4.2. Операции над списками
1. Доступ к элементам списка.
2. Поиск элемента в списке.
3. Добавление нового элемента в список.
4. Удаление элемента из списка.
5. Деление списка на подсписки.
6. Объединение двух списков.
7. Сортировка элементов списка по возрастанию и по убыванию.
Рассмотрим программу, которая выводит на печать элементы
заданного списка.
Пример 4.2.1.
domains
list_int = integer *
predicates
print_list(list_int)
goal
print_list([10, 4, 12, 5]). (1)
clauses
print_list([ ]). (2)
print_list([H | T]): – (3)
write(H), nl,
print_list(T).
Рассмотрим процедурный смысл данной программы. Программа
имеет внутреннюю цель (1), которая содержит предикат print_list.
Заданный список является объектом предиката print_list. Печать списка
33
осуществляется рекурсивной процедурой, состоящей из факта (2) и
рекурсивного правила (3).
Целевое утверждение (1) сопоставляется с фактом (2) – неуспех, так
как факт (1) имеет пустой список. Идет дальнейший поиск решения.
Заданный список сопоставляется с головой правила (3). Будем иметь:
H = 10, T = [4, 12, 5]. Система выделила первый элемент списка и с ним
можно обращаться так же как и с любым простым объектом, что и
происходит дальше write(H), nl. Затем происходит рекурсивный вызов
print_list(T), где в качестве объекта передается хвост списка, т. е. [4, 12,
5]. Идет сопоставление print_list([4, 12, 5]) с print_list([ ]) – неуспех.
Когда голова списка будет 5, то хвост – пустой список. Теперь при
рекурсивном вызове значение Т будет сопоставимо с объектом факта (2).
Цель считается удовлетворенной и рекурсия закончится.
Пример 4.2.2.
/*Определение длины списка*/
domains
list_int = integer *
predicates
length_list(list_int, integer) /*второй объект
предиката обозначает количество
элементов списка*/
goal
length_list([10, 4, 12, 5], L). /*L – незначимая
переменная*/
clauses
length_list([ ], 0). (1)
length_list([_|T], L): –
length_list(T, Tlength),
L = Tlength + 1. (2)
При работе данной программы создается стек, в ячейках которого
хранятся неозначенные значения переменной Tlength. Шагов рекурсии
будет столько, сколько элементов в списке и столько же переменных
Tlength будет в стеке. Конец рекурсии – пустой список. При пустом
списке и сопоставлении с фактом (1) неозначенная переменная Tlength
получает значение нуль и последняя ячейка стека равна нулю. Подцель
L = Tlength + 1 начинает работать при обратной раскрутки рекурсии и
определять значения переменной Tlength, и в результате будет получено
значение переменной L. Если в правиле (2) поменять местами подцели:
length_list([_|T], L): –
L = Tlength + 1,
length_list(T, Tlength).
34
декларативный смысл процедур останется неизменным, но процедурный
смысл изменится. Такой вариант правила приведет к неуспеху. При
попытке системы вычислить переменную L, переменная Tlength является
неозначенной. Эта переменная получает значение 0, когда факт (1) будет
иметь успех, т. е. будет достигнуто базовое состояние и начинается
обратная рекурсия.
Так как число элементов списка равно количеству шагов рекурсии,
то вычисление длины списка можно осуществить другим, более
эффективным способом. Количество элементов списка можно
подсчитать непосредственно при выполнении рекурсии.
Пример.
domains
list_int = integer *
predicates
length_list(list_int, integer, integer)
goal
length_list([10, 4, 12, 5], L, 0).
clauses
length_list([ ], Result, Result): – !. (1)
length_list([_ | T], Result, Counter): – (2)
NewCounter = Counter + 1,
length_list(T, Result, NewCounter).
В рекурсивном правиле (2) к счетчику Counter прибавляется 1 и
делается шаг рекурсии, переменная Result не имеет значения. Когда
список станет пустым (1), переменной Result (второй объект) правила (1)
присваивается значение Counter.
4.2.1. Поиск элемента в списке
Операция поиска элемента в списке (принадлежности списку) бази-
руется на сопоставлении термов. Имеется объект поиска (Х) и список (L).
Для выделения элемента из списка и сравнения с объектом поиска
используется метод разделения списка на голову и хвост. Поиск будет
заключаться в рекурсивном выделении головы списка и сравнении с объек-
том поиска. Если Х принадлежит L, то истина и ложь в противном случае.
Декларативный смысл поиска элемента в списке:
1. Х принадлежит списку, если Х совпадает с головой списка.
2. Х принадлежит списку, если Х принадлежит хвосту списка.
Имеем процедуру поиска:
find_elem(X, [X | _]). (1)
find_elem(X, [_ | T]): –
find_elem(X, T). (2)
35
С точки зрения процедурного смысла – это рекурсивная процедура.
Факт (1) отражает случай, когда объект поиска совпадает с головой списка,
анонимная переменная обозначает хвост списка. Если объект поиска и
голова списка сопоставимы, то результатом будет успех. Если нет, то
происходит откат и переход к правилу (2), в котором голова списка –
анонимная переменная, так как значение головы списка нас не интересует.
Хвост списка (Т) представляет собой самостоятельный список, опять
список разделяется на голову и хвост, проверяется факт (1). Процесс
повторяется до тех пор, пока утверждение (1) не даст успеха в случае
установления соответствия на очередном шаге рекурсии, либо неуспех в с
случае исчерпания списка.
4.2.2. Добавление элементов в список
Добавление элемента в начало списка
Добавить элемент в начало списка – это значит вставить его в
самое начало так, чтобы он стал новой головой.
attach_at_head([ ], X, [X]).
attach_at_head(L1, X, L2): – L2 = [X | L1].
где: L1 – исходный список;
L2 – новый список;
Х – новый элемент.
Добавление элемента в конец списка
attach_at_tail ([ ], X, [X]). (1)
attach_at_tail ([H | T], X, [X | T1]): – (2)
attach_at_tail(T, X, T1)
где: первый объект предиката attach_at_tail − исходный список,
второй объект − новый элемент,
третий объект − новый список.
Чтобы добавить элемент в конец списка необходимо список сделать
пустым. Это делает рекурсия правила (2). При пустом списке утверждение (1)
имеет успех, а это значит, что в пустой исходный список добавлен новый
элемент, и новый список имеет вид [X] . Элементы списка были помещены
при работе рекурсии в стек. При выходе из рекурсии (обратной раскрутки) в
итоге будет получен весь список с новым элементом в конце списка.
4.2.3. Деление списка на подсписки
Часто при работе со списками необходимо иметь доступ только к
определенной части исходного списка, т. е. необходимо разделить
список на части.
36
Рассмотрим процедуру, которая делит исходный список целых чисел
на два подсписка: положительные числа и нулевые, и отрицательные числа.
split(_, [ ], [ ], [ ]). (1)
split(K, [H | T], [H | L1], L2): – (2)
Н >= K,
split(K, T, L1, L2).
split(K, [H | T], L1, [H | L2]): –
Н<K,
split(K, T, L1, L2).
Предикат split содержит четыре объекта:
первый – объект, который делит список и называется компаратор;
второй – исходный список (L);
третий – список, содержащий положительный и нулевые числа (L1);
четвертый – список, содержащий отрицательные числа (L2);
K = 0.
Запись[H | L1] или [H | L2] показывает программам унификации
куда необходимо вставить голову списка L в L1 или L2.
Если L = [5, –2, 0, 4, –10, 35], то
L1 = [5, 0, 4, 35] и
L2 = [–2, –10].
4.2.4. Объединение списков
Объединение списков (конкатенация). Одна из распространенных
операций со списками. Особенно часто используется в системах
управления базами данных и базами знаний, в разработке интерфейсов
пользователя.
Процедура для объединения двух списков:
append ([ ], L, L). (1)
append ([X | L1], L2, [X | L3): –
append(L1, L2, L3). (2)
Предикат append имеет три объекта:
первый объект – входной список L1,
второй объект – входной список L2,
третий объект – выходной список L3.
Целевое утверждение:
append ([a, b, c], [d, e], L),
где:
L – выходной список (не означенная переменная);
L = [a, b, c, d, e] – результат работы процедуры.
Рассмотрим процедурный смысл объединения списков. Целевое
утверждение сопоставляется с фактом (1) имеет не успех, т. к. пустой
37
список из (1) не сопоставляется с первым объектом утверждения.
Происходит откат к рекурсивному правилу (2), здесь происходит
рекурсия и элемента списка L1 помещаются в стек (работает метод
отделения головы от хвоста). С элементами списка L2 ничего не
происходит, список L3 не определен. При образовании пустого списка
L1 список L3 становится равным списку L2, на основании факта (1),
дальше идет обратная рекурсия. Элементы извлекаются из стека и один
за другим, помещаются в качестве головы к L1 и L3, значение
извлеченного из стека элемента присваивается переменной Х.
Шаги процедуры для объединения двух списков:
append ([a, b, c ],[d, e ], L).
append ([b, c],[ d,e], L).
append ([c],[d, e], L).
append ([ ],[ d, e], L).
append ([ ],[d, e], [d, e]).
append ([c],[d, e ], [c, d, e]).
append ([b, c],[d, e], [b, c, d, e]).
append ([a, b, c], [d, e], [a, b, c, d, e]).
4.2.5. Сортировка списков
Сортировка – это процесс переупорядочивания элементов списка в
определенном порядке. Назначением сортировки является ускорение
доступа к нужным элементам списка. Турбо-Пролог позволяет
осуществлять сортировку, используя три основных принципа действия
сортировок: принцип перестановки, принцип выборки, принцип вставки,
или их комбинаций. Список можно отсортировать, если между
элементами определено отношение порядка например, order(Х, Y): –
Х > Y. Данное отношение означает, что Х больше Y.
Особенно удобен для реализации на Турбо Прологе принцип
вставки, который осуществляется при помощи неоднократной вставки
элементов в список, до тех пор, пока он не будет упорядочен.
Рассмотрим процедуру, которая осуществляет такую сортировку.
insert_sort([ ], [ ]). (1)
insert_sort([X | Tail], sorted_list):– (2)
insert_sort(Tail, Sorted_Tail),
insert(X, Sorted_Tail, sorted_list).
insert(X, [Y|Sorted_list], [Y | Sorted_list1]):–(3)
order(X, Y), !,
insert(X, Sorted_list, Sorted_list1).
insert(X, Sorted_list, [X | Sorted_list]). (4)
order(X, Y):– X > Y. (5)
Процедура сортировки содержит два предиката :
insert_sort – предикат, производящий сортировку, имеет два объекта:
38
первый объект – исходный список;
второй объект – выходной (отсортированный) список.
insert – предикат, производящий вставку элементов в список. Имеет три
объекта:
первый объект – элемент, который необходимо вставить в
список;
второй элемент – список, в который элемент вставляется;
третий объект – список со вставленном элементом.
Обозначения:
Х, Y – элементы списка, извлеченные из стека;
Х – текущий элемент из стека;
Y – предыдущий элемент из стека.
Процедура insert содержит правило (3) и факт (4) по
упорядочиванию элементов. Правило (3) отражает случай, когда элемент
при сортировке вставляется в хвост списка. Факт (4) отражает случай,
когда элемент при сортировке вставляется в качестве новой головы
списка. Список всегда можно разбить на голову и хвост. Перед тем, как
первый элемент списка будет присвоен голове списка, его хвост в
действительности содержит весь список целиком. Следовательно,
сортировка хвоста есть не что иное, как сортировка самого списка.
Целевым утверждением для данной процедуры может быть:
insert_sort([5, 7, 2, 8], L),
где L – выходной список и на данный момент не определен.
Рассмотрим процедурный смысл процедуры сортировки
Первый шаг сортировки начинается с сопоставления целевого
утверждения с фактом (1) и терпит неуспех, так происходит
сопоставление списка [5, 7, 2, 8] с пустым списком [ ] из (1). Пытаясь
удовлетворить целевое утверждение система переходит на правило (2),
Х
получает значение 5, а Tail = [7, 2, 8]. Затем элементы входного списка
помещаются в стек при выполнении рекурсии и список становится
пустым, и происходит сопоставление с фактов (1). Это значит, что
второй объект предиката insert_sort Sorted_Tail равен пустому списку,
sorted_Tail = [ ]. Затем происходит обратная рекурсия и начинает
работать процедура insert. Переменная Х получает значение 8 (это
первый элемент на выход из стека). Список, в который надо поместить
переменную Х – пустой, поэтому выполняется факт (4). Имеем:
insert(8, [ ], [8]).
Из стека извлекается следующий элемент, Х = 2, программа
унификации Турбо-Пролога определяет место куда поместить
39
переменную Х. Идет попытка удовлетворить правило (3). Первая
подцель
order(2, 8)
имеет неуспех (order (2, 8):– 2 > 8), поэтому выполняется факт (4), т. е.
Х = 2 вставляется вместо головы в список sorted_list = [8] и имеем
insert(2, [8], [2, 8]).
Из стека извлекается следующий элемент Х = 7, начинает работать
правило (3), подцель
order(7, 2): – 7 > 2 имеет успех,
следующая подцель ! успешно выполняется, убрав все точки отката,
подцель
insert(X, Sorted_list, Sorted_list1)
вызывает рекурсию и передает в голову правила (3) хвост списка [2, 8],
а голова равна 2 и помещается в стек. Имеем Х = 7, Y = 8, поэтому
подцель
order(7, 8):– 7 > 8 имеет неуспех
и выполняется факт (4)
Имеем insert(7, [8], [7, 8]).
Идет возврат рекурсии, из стека выбирается значение 2, Х = 2.
Правило (2) имеет неуспех, так как цель order(2,7) неуспешна и
выполняется факт(4).
insert(2, [7, 8], [2, 7, 8]).
Идет возврат рекурсии, из стека выбирается последний элемент
равный 5. Правило (3) имеет успех, а значит голова списка [2, 7, 8]
равная 2 помещается в стек, выполняется факт (4).
insert(5, [7, 8], [5, 7, 8]).
Идет возврат рекурсии, из стека выбирается элемент равный 2.
Правило (3) имеет неуспех, выполняется факт (4) и имеем
insert(2, [5, 7, 8], [2, 5, 7, 8]).
Стек пустой, сортировка элементов списка окончена.
40
4.3. Списки и базы данных
Из утверждений, составляющих базу данных часто возникает
необходимость выбрать определенные объекты для дальнейшей их
обработки. Такую операцию можно осуществить, используя встроенный
предикат сбора findall. Данный предикат позволяет производить сбор
необходимых данных из базы данных в список.
Предикат findall имеет три объекта:
первый объект – имя объекта встроенного предиката;
второй объект – входной предикат с объектами;
третий объект – имя предиката выходного списка.
findall(C, p (_, _, C, _), L).
Рассмотрим использование предиката findall на примере
следующей программы.
Пример 4.3.1.
/* программа: вычисления среднего балла успеваемости студентов по
заданной дисциплине*/
domain
name = symbol
list = integer*
predicates
mark(name, integer)
sum_list(list, integer, integer)
average_mark
gaal
average_mark.
clauses
mark(
'
Иванов
'
, 7).
mark(
'
Петров
'
, 9).
mark(
'
Сидоров
'
, 5).
.............................
average_mark:–
findall(Mark,mark(_, Mark)), Mark_list),
sum_list(Mark_list, SUM, Number),
Average = SUM / Number,
write(
''
Average mark =
''
, Average).
sum_list([ ], 0, 0).
sum_list([H | T], SUM, Number):–
sum_list(T, SUM1, Number1),
SUM = H + SUM1,
Number = Number1 + 1.