append(n_list,n_list,n_list)
clauses append([],L,L).
append([N|L1], L2, [N|L3]) :- append(L1,L2,L3).
/***** конец программы *****/
____________________________________________________________
Программу "Присоединение списка" можно смело отнести к числу весьма эффективных. Написаны только две строки, однако Турбо-Пролог в своих недрах создает временные списки, перемещает элементы из одного в другой. Таким образом вся кухня определенно остается за сценой. Программисту нет необходимости специфицировать все эти действия.
Правила присоединения списка являются важным инструментом программирования. Способ работы этих правил на первых порах может несколько смутить Вас, поэтому стоит попрактиковаться при помощи приведенных ниже упражнениями.
*Упражнения
5.13.Запустите программу "Присоединение списка" и введите целевое утверждение
append([9,15,3,60,55],[15,2,21],L).
Что получится ?
5.5.4 Сортировка списков
Сортировка представляет собой переупорядочивание элементов списка определенным образом. Назначением сортировки является упрощение доступа к нужным элементам. Сортировка важна как в реальной жизни, так и в применениях вычислительной техники. Сортируются фамилии в телефонном справочнике, сортируется по номерам информация в отчетах по соцобеспечению, почта сортируется по индексу, маршруту доставки, номеру дома.
Сортировка данных при помощи компьютера является рутинной, но важной работой. Гораздо проще и гораздо эффективнее искать что-либо в отсортированном списке, нежели в неотсортированном.
Существует много способов сортировки списков. Рассмотрим, например, список целых чисел:
[51,23,84,17,11]
Элементы этого списка не расположены в каком-то определенном порядке в обычном понимании этого слова. Тот же самый список, но уже отсортированный в порядке возрастания элементов, выглядит так:
[11,17,23,51,84]
Сортирующее правило Турбо-Пролога принимает на вход неотсортированный список, и выдает отсортированный на выходе. Входной список называется исходным, выходной - целевым.
111
Три метода обычно применяются для сортировки списков: метод перестановки, метод вставки и метод выборки. Сортировку можно произвести любым из трех названных методов или их комбинацией. Первый из перечисленных методов заключается в перестановке элементов списка до тех пор, пока они не выстроятся в нужном порядке. Второй осуществляется при помощи неоднократной вставки элементов в список до тех пор, пока он не будет упорядочен. Третий включает в себя многократную выборку и перемещение элементов списка.
Второй из методов, метод вставки, особенно удобен для реализации на Турбо-Прологе. Сейчас мы зададимся целью написать правило, реализующее этот метод.
Рассмотрим список [4,7,3,9], элементы которого расположены случайным образом. Мы хотим получить список [3,4,7,9], упорядоченный по порядку возрастания элементов.
Опишем предикат, производящий нужную сортировку списка методом вставки.
insert_sort(source_list,target_list)
Внешней целью в задаче сортировки списка [4,7,3,9] будет утвержде-
ние
insert_sort([4,7,3,9],S).
В этом утверждении отсортированный список обозначен переменной S. Для того, чтобы воспользоваться преимуществами мощного средства ТурбоПролога - внутренней унификацией, мы проделаем то, что обычно называется сортировкой хвоста. Напомним, что список всегда можно разбить на голову и хвост. Перед тем, как первый элемент списка будет присвоен голове списка, его хвост в действительности содержит весь список целиком. Следовательно, сортировка хвоста есть не что иное, как сортировка самого списка.
Правила, реализующие этот способ сортировки, имеют следующую структуру:
insert_sort([],[]). insert_sort([X|Tail],Sorted_list) :-
insert_sort(Tail,Sorted_Tail), in-sert(X,Sorted_Tail,Sorted_list).
insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :- asc_order(X,Y), !, insert(X,Sorted_list,Sorted_list1). insert(X,Sorted_list,[X|Sorted_list]).
asc_order(X,Y) :- X>Y.
Дальнейшее обсуждение продемонстрирует работу правил на примере списка [4,7,3,9].
Вначале Турбо-Пролог применяет приведенные правила к исходному списку, выходной список в этот момент еще не определен.
insert_sort([4,7,3,9],_).
112
Первая попытка удовлетворить правило insert_sort осуществляется с первым вариантом правила
insert_sort([],[]).
Для удовлетворения правила оба списка должны быть пустыми. Второй вариант правила insert_sort трактует список как комбинацию головы списка и его хвоста. Внутренние унификационные процедуры Турбо-Пролога пытаются сделать пустым исходный список. Устранение элементов списка начинается с головы списка и осуществляется рекурсивно.
Та часть правила, которая производит удаление элементов, выглядит
так:
insert_sort([X|Tail],Sorted_list) : - insert_sort(Tail, Sorted_Tail).
По мере того как Турбо-Пролог пытается удовлетворить первое из правил, происходят рекурсивные вызовы insrt_sort, при этом значениями Х последовательно становятся все элементы исходного списка, которые затем помещаются в стек. В результате применения этой процедуры список становится нулевым. Теперь первый вариант правила insert_sort производит обнуление выходного списка, и таким образом правилу придается форма
insert_sort([],[]).
Далее, после того как удовлетворен первый вариант правила insert_sort, Турбо-Пролог пытается удовлетворить второе правило из тела insert_sort - правило insert. Переменной Х сначала присваивается первое взятое из стека значение, 9, а правило insert принимает форму
insert(9,[],[9]).
Теперь удовлетворено и второе правило из тела insert_sort - правило insert (его второй вариант), поэтому происходит возврат на один круг рекурсии insert_sort. Из стека извлекается следующий элемент, 3, и испытывается первый вариант insert, а значит и правило упорядочивания
asc_order(X,Y) :- X>Y.
Переменная Х здесь имеет значение 3, Y - значение 9, само правило имеет вид
asc_order(3,9) :- 3>9.
Так как оно неуспешно (3 на самом деле не больше, а меньше 9), то вместе с ним неуспешен и первый вариант insert. При помощи второго варианта insert 3 вставляется в выходной список слева от 9:
insert(3,[9],[3,9]).
Происходит возврат к insert_sort, теперь оно имеет форму insert_sort([3,9],[3,9]).
На следующем круге рекурсии происходит вставка очередного элемента из стека, а именно 7. В начале работы на этом круге правило insert имеет вид
insert(7,[3,9],_).
Сначала происходит сравнение 7 и 3, asc_order(7,3):- 7>3.
Так как данное правило успешно, то элемент 3 убирается в стек, и insert вызывается рекурсивно еще раз, но уже с хвостом списка - [9] :
113
insert(7,[9],_).
Так как правило asc_order(7,9):- 7>9.
неуспешно, то испытывается второй вариант insert (успешно), происходит возврат на предыдущие круги рекурсии сначала insert, а потом insert_sort. В результате 7 помещается в выходной список между элементами 3 и 9.
insert(7,[3,9],[3,7,9]).
При возврате еще на один круг рекурсии insert_sort из стека извлекается элемент 4. Правило insert выглядит как
insert(4,[3,7,9],_).
Далее имеем: правило asc_order(4,3) :- 4>3.
успешно, следовательно, следует попытка insert(4,[7,9],_).
Правило же
asc_order(4,7) :- 4>7.
неуспешно. Нетрудно сообразить теперь, что 4 окажется в выходном списке между 3 и 7 :
insert(4,[3,7,9],[3,4,7,9]). insert_sort([4,7,3,9],[3,4,7,9]).
Теперь в стеке больше нет элементов, и все рекурсии insert_sort уже свернуты. Выходной список получил при этом значение [3,4,7,9], удовлетворена цель программы.
Программа "Сортировка списка" (листинг 5.6) реализует правило сортировки при помощи вставок для целочисленных списков. Программа работает в интерактивном режиме.
____________________________________________________________
Листинг 5.6
/* Программа: Coртировка списка |
*/ |
|
/* Назначение: Сортировка списка целых чисел. |
*/ |
|
/* |
в порядке возрастания при помощи |
*/ |
domains |
|
|
number = integer |
|
|
list |
= number * |
|
predicates insert_sort(list,list) insert(number,list,list)
asc_order(number,number)
clauses insert_sort([],[]).
insert_sort([X|Tail],Sorted_list) :- insert_sort(Tail,Sorted_Tail), insert(X,Sorted_Tail,Sorted_list).
114
insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :- asc_order(X,Y), !, insert(X,Sorted_list,Sorted_list1). insert(X,Sorted_list,[X|Sorted_list]). asc_order(X,Y) :- X>Y.
/***** конец программы *****/
____________________________________________________________
Запустите программу на счет с целевыми утверждениями insert_sort([4,7,3,9],S).
и
insert_sort([7,6,5,4,3,2,1],S).
*Упражнения
5.15.Запустите программу "Сортировка списка". Введите цель
insert_sort([53,11,93,77,11],S).
Что получится ?
5.16. Внесите в программу такие изменения, чтобы она могла сортировать целые числа в порядке убывания. Запустите на счет новый вариант программы. Задайте следующее целевое утверждение:
insert_sort([1,2,3,4,5,6,7],S).
Что получится ?
5.6 Компоновка данных в список
Иногда, при программировании определенных задач, возникает необходимость собрать данные из базы данных в список для последующей их обработки. Турбо-Пролог содержит встроенный предикат, позволяющий справиться с этой задачей без каких бы то ни было хлопот. Таким предикатом является предикат findall. Требуемый список представляется означенной переменной, являющейся одним из объектов предиката.
Предописание встроенного предиката findall выглядит следующим образом:
findall(Variable_name,Predicate_expression,List_name).
Variable_name обозначает здесь объект входного предиката Predicate_expression, а List_name является именем переменной выходного списка. Переменная должна относиться к домену списков, объявленному в разделе domains.
Для пояснения только что сказанного рассмотрим предикат базы дан-
ных
football(name,points)
Этот предикат порождает 5 утверждений : ootball("Ohio State",116.0). football("Michigan",121.0). football("Michigan State",114.0). football("Purdue",99.0). football("UCLA",122.0).
115