Файл: Тематический план.pdf

Пример:
/* Демонстрация работы со списками */ domains bird_list = bird_name * bird_name = symbol number_list = number * number = integer predicates
birds(bird_list) score(number_list)
clauses birds(["sparrow", "robin", "mockingbird", "thunderbird"]).
score([56,87,63,89,91,62,85]).
Отличительной особенностью описания списка является наличие звездочки (*) после имени домена элементов. Так, запись bird_name * указывает, что это домен списка, элементами которого являются bird_name, т. е. запись bird_ name * следует понимать как список, состоящий из элементов домена bird_name. Примеры внешних целей:
birds(All). birds([_,_,_,B,_]). birds([B1,B2,_,_,_]).
score(All). score([F,S,T,_,_,_,_]).
При задании целей во втором, третьем и пятом примерах требовалось точное знание количества элементов списка, являющегося объектом предиката birds, что не всегда возможно (с точки зрения пользователя). Но вспомним, что Prolog позволяет отделять от списка первый элемент и обрабатывать его отдельно. Данный метод работает вне зависимости от длины списка до тех пор, пока список не будет исчерпан. Этот метод доступа к голове списка называется методом разделения списка на голову и хвост.
Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):
[Head|Tail].
Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка.
Пример. Правило печати элементов списка [4,-9,5,3]:
print_list ([]).
print_list ([Head|Tail]) :write (Head),nl, print_list (Tail).

Когда это правило пытается удовлетворить цель print_ list([4,-9,5,3]), то первый вариант правила — print_ list[] — дает неуспех, так как его объект является пустым списком. Напротив, введенный список соответствует объекту второго варианта предиката — print_list([Head|Tail]).
Переменной Head, следовательно, присваивается значение первого элемента в списке: 4, в то время как переменной Tail cтавится в соответствие оставшаяся часть списка: [-9,5,3]. Теперь, когда выделен первый элемент списка, с ним можно обращаться так же, как и с любым простым объектом: write(Head),nl. Далее, так как хвост списка есть список сам по себе, то значение переменной Tail может быть использовано в качестве объекта рекурсивного вызова print_list: print_list(Tail). Когда испытывается данное подправило, Tail имеет значение [-9,5,3]. Снова первый вариант не проходит и соответствие устанавливается при помощи второго. Переменной Head присваивается значение –9, которое затем печатается на экране, а процесс повторяется со списком [5,3]. В итоге, когда переменная Head принимает значение 3, переменной Tail присваивается пустой список. Теперь при рекурсивном вызове print_list(Tail) значение Tail соответствует объекту правила print_list([]). Поскольку этот вариант не имеет рекурсивных вызовов, цель считается удовлетворенной, и вырабатывается условие окончания рекурсии print_list. Тем самым первый вариант позволяет print_list завершиться успехом, когда рекурсивные вызовы опустошат весь список.
Пример:
/* Демонстрация использования метода деления списка на голову и хвост при выводе списка на экран */ domains animal_list = symbol *
predicates print_list(animal_list)
clauses animal (["тигр","заяц","лев","волк"]). print_list([]).
print_list([Head|Tail]) :write(Head),nl, print_list(Tail).
goal animal (Animals_list), print_list (Animals_list).

Операции над списками
Поиск элемента в списке представляет собой просмотр списка для выявления соответствия между элементом данных и элементом просматриваемого списка. Если такое соответствие найдено, то поиск заканчивается успехом; в противном случае поиск заканчивается неуспехом.
Для сопоставления объекта поиска с элементами просматриваемого списка необходим предикат, объектами которого являются эти объект поиска и список:
find_it(3 ,[1,2,3,4,5]).
Первый из объектов утверждения — 3 — есть объект поиска. Второй
— это список [1,2,3,4,5]. Для выделения элемента из списка и его сравнения с объектом поиска можно применить метод разделения списка на голову и хвост. Стратегия поиска при этом будет состоять в рекурсивном выделении головы списка и ее сравнении с элементом поиска.
Правило поиска может сравнивать объект поиска и голову текущего списка. Саму операцию сравнения можно записать в виде:
find_it(Head,[Head|_]).
Этот вариант правила предполагает наличие соответствия между объектом поиска и головой списка. В данном случае поскольку осуществляется попытка найти соответствие между объектом поиска и головой списка, то нет необходимости заботиться о том, что происходит с хвостом. Если объект поиска и голова списка действительно соответствуют друг другу, то результатом сравнения явится успех; если же нет, то неуспех.
Но если эти два элемента данных различны, то попытка сопоставления считается неуспешной, происходит откат и поиск другого правила или факта, с которыми можно снова попытаться найти соответствие.

Для случая несовпадения объекта поиска и головы списка необходимо предусмотреть правило, которое выделяло бы из списка следующий по порядку элемент и делало бы его доступным для сравнения:
find_it(Head, [Head|_].
find_it(Head, [_,Tail]) :find_it(Head, Tail).
Если правило find_it(Head,[Head|_]) неуспешно, то происходит откат и делается попытка со вторым вариантом. При этом опять-таки присвоенный переменной Tail список разделяется на голову и хвост при помощи утверждения find_it(Head,[Head|_]), и этот процесс повторяется, пока данное утверждение не даст либо успех (в случае установления соответствия на очередной рекурсии), либо неуспех (в случае исчерпания списка).
Деление списков. При работе со списками достаточно часто требуется разделить список на несколько частей. Это бывает необходимо, когда для текущей обработки нужна лишь определенная часть исходного списка.
Рассмотрим предикат split, аргументами которого являются элемент данных и три списка:
split(Middle,L,L1,L2).
Элемент Мiddle здесь является компаратором, L — это исходный список, а L1 и L2 — подсписки, получающиеся в результате деления списка
L. Если элемент исходного списка меньше или равен Middle, то он помещается в список L1, а если больше, — то в список L2.
Пример:
split(40,[30,50,20,25,65,95],L1,L2).
Правило здесь устроено следующим образом: очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом сравнивается с компаратором Middle. Если значение этого элемента меньше или равно значению компаратора, то элемент помещается в список L1, в противном случае — в список L2. В результате применения этого правила к списку [30,50,20,25,65,95] значениями списков L1 и L2

станут соответственно [30,20,25] и [50,65,95]. Само же это правило для разделения списка записывается на языке Prolog следующим образом:
split(Middle,[Head|Tail],[Head|L1],L2)
:Head
<=
Middle, split(Middle,Tail,L1,L2).
split(Middle,[Head|Tail],L1,[Head|L2])
:Head
>
Middle, split(Middle,Tail,L1,L2), split(_,[],[],[]).
Отметим, что метод деления списка на голову и хвост используется в данном правиле как для разделения исходного списка, так и для формирования выходных списков.
Присоединение списка. Слияние двух списков и получение, таким образом, третьего списка принадлежит к числу наиболее полезных при работе со списками операций.
В качестве примера рассмотрим две переменные L1 и L2, представляющие списки и имеющие значения [1,2,3] и [4,5] соответственно.
Тогда весь процесс слияния можно представить в виде такой совокупности действий:
1) список L3 (результирующий) вначале пуст;
2) элементы списка L2 пересылаются в L3; теперь значением L3 будет [4,5];
3) элементы списка L1 пересылаются в L3; в результате он принимает значение [1,2,3,4,5].
Структура правила для выполнения этих действий следующая:
append([],L,L).
append([N|L1],L2,[N|L3]) :append(L1,L2,L3).
Если на его вход подать списки L1=[1,2,3] и L2=[4,5], то сначала Prolog пытается удовлетворить первый вариант правила:
append([],L,L).

Чтобы сделать это, первый объект предиката должен быть пустым списком. Однако это не так. Внутренний процесс унификации Prolog, пытаясь удовлетворить второе правило append, раскручивает цепочку рекурсий до тех пор, пока не обнулит первый список. Элементы списка при этом последовательно пересылаются в стек. Когда первый объект предиката append окажется пустым списком, становится возможным применение первого варианта правила. Третий список при этом инициализируется вторым:
append([],[4,5],_). append([],[4,5],[4,5]).
Теперь Prolog начинает сворачивать рекурсивные вызовы второго правила. Извлекаемые при этом из стека элементы помещаются один за другим в качестве головы к первому и третьему спискам. Следует особо отметить, что элементы извлекаются в обратном порядке (ведь это стек!), и что значение извлеченного из стека элемента присваивается переменной N одновременно в [N|L1] и [N|L3]. Шаги данного процесса можно представить так:
append([],[4,5],[4,5]) append([3],[4,5],[3,4,5]) append([2,3],[4,5],[2,3,4,5]) append([1,2,3],[4,5],[1,2,3,4,5])
Сортировка списков представляет собой переупорядочивание элементов списка определенным образом для упрощения доступа к нужным элементам. Существует много способов сортировки списков, но обычно применяются три из них: метод перестановки, метод вставки и метод выборки (или их комбинации). Первый из этих методов заключается в попарной перестановке элементов списка до тех пор, пока они не выстроятся в нужном порядке. Второй осуществляется при помощи вставки элементов в список на требуемые места до тех пор, пока список не будет упорядочен.
Третий метод включает в себя многократную выборку и перемещение элементов списка. Второй из указанных методов (метод вставки) особенно удобен для реализации на языке Prolog.

Рассмотрим список [4,7,3,9], элементы которого расположены хаотично. Пусть мы хотим получить из него список [3,4,7,9], упорядоченный по возрастанию. Опишем предикат, производящий нужную сортировку списка методом вставки.
Чтобы воспользоваться преимуществами мощного средства языка
Prolog — внутренней унификацией, проведем сортировку хвоста. Правила, реализующие этот способ сортировки, имеют следующую структуру:
insert_sort([],[]).
insert_sort([X|Tail],Sorted_list) :insert_sort(Tail,Sorted_Tail), insert(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]. Вначале
Prolog применяет указанные выше правила к исходному списку; выходной список в этот момент еще не определен: insert_sort([4,7,3,9],_).
Первая попытка удовлетворить правило insert_sort осуществляется с первым вариантом правила insert_sort ([],[]), т. е. для удовлетворения этого правила оба списка должны быть пустыми.
Второй вариант правила insert_sort трактует список как комбинацию головы списка и его хвоста. Внутренние унификационные процедуры языка
Prolog пытаются сделать пустым исходный список. Устранение элементов списка начинается с головы списка и осуществляется рекурсивно. По мере того как Prolog пытается удовлетворить первое из правил, происходят рекурсивные вызовы insert_sort, при этом значениями Х последовательно становятся все элементы исходного списка, которые затем помещаются в стек. В результате применения этой процедуры список становится пустым.
Теперь первый вариант правила insert_sort производит обнуление выходного списка. Далее Prolog пытается удовлетворить второе правило из тела

insert_sort — правило insert. Переменной Х сначала присваивается первое взятое из стека значение 9, а правило insert принимает форму insert(9,[],[9]).
Затем из стека извлекается следующий элемент — 3 — и испытывается первый вариант insert, а значит, и правило упорядочивания asc_order(X,Y)
:X>Y. Переменная Х здесь имеет значение 3, а Y — значение 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 вызывается рекурсивно еще раз, но уже с хвостом списка: 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 уже свернуты.
Компоновка данных в список. Иногда при программировании определенных задач возникает необходимость собрать данные из базы

данных в список для последующей их обработки. Prolog содержит встроенный предикат, позволяющий справиться с этой задачей:
findall(Variable_name, Predicate_expression, List_name).
Variable_name здесь обозначает объект входного предиката
Predicate_expression, а List_name является именем переменной выходного списка. Эта переменная должна относиться к домену списков, объявленному в разделе domains.
Пример. Опишем предикат, содержащий сведения об очках, набранных футбольными командами. Необходимо сложить все очки и усреднить их.
/* Демонстрация предиката компоновки данных в список для вычисления среднего значения*/ domains
list = real * predicates football (symbol,real) sum_list (list, real, integer).
average_score
сlauses
/* факты (футбольная база данных) */ football("Ohio State",116.0). football("Michigan",121.0).
football("Michigan State",114.0). football("Purdue",99.0).
football("UCLA",122.0).
average_score
:findall(Points,football(_,Points),Point_list), sum_list
(Point_list, Sum, Number), Average = Sum / Number, write("Среднее значение=
",Average).
sum_list ([],0,0).
sum_list ([H|T], Sum, Number) :- sum_list(T,Sum1,Number1),
Sum = H + Sum1,
Number = Number1 + 1.
goal average_score.