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", "bald eagle"]).
score([56,87,63,89,91,62,85]).
/***** конец программы *****/
____________________________________________________________
Эта программа создавалась в расчете на следующие внешние запросы: birds(All).
birds([_,_,_,B,_]). birds([B1,B2,_,_,_]). score(All). score([F,S,T,_,_,_,_]).
Поясним теперь работу программы при задании каждой из этих целей, это прояснит способ работы со списками в программах на ТурбоПрологе. Заметим, что свободная переменная All представляет весь список в целом. Он рассматривается при этом как некое целое, элементы играют роль частей этого целого.
Что касается второй цели, birds([_,_,_,B,_]), то процесс сопоставления начинается с первого элемента. Первые три переменные в целевом утверждении являются анонимными, при сопоставлении это обстоятельство, однако, роли не играет. Переменной B присваивается значение thunderbird. В этом процессе используется внутренняя связь элементов. В результате удовлетворения цели появляется строка B=thunderbird.
Третья цель, birds([B1,B2,_,_,_]), запрашивает первые два элемента списка. На выходе можно будет увидеть B1=sparrow,
B2=robin, т. е. значения первого и второго элементов списка.
Обратимся теперь ко второй части программы, имеющей дело со списком целых чисел. В случае со score(All) переменной All присваивается весь список из 7 элементов, а выдача будет выглядеть так:
All=[56,87,63,89,91,62,85].
101
Пятая цель - это score([S1,_,_,S4,_,S6,_]). На выходе будем иметь S1=56, S4=89, S6=62. Также как и в случае с третьей целью, внутренне связанные элементы будут выбираться селективно в соответствии с порядком в списке.
*Упражнения
5.7.Нарисуйте линейный граф для списка birds(bird_list).
5.8.Нарисуйте дерево для списка score(number_list).
5.9.Запустите программу "Списки" и введите такое целевое утвержде-
ние:
birds([S,R,M,T,B]).
Какова будет выдача программы, и в чем она будет отличаться от выдачи при целевом утверждении birds(All)?
5.4 Использование метода с разделением списка на голову и хвост
В программе "Списки" для получения доступа к элементам списков были использованы внешние целевые утверждения. Задание цели в виде birds(All) обеспечивало присваивание переменной All всего списка в целом. Напротив, цель birds([_,_,_,B,_]) позволила извлечь из списка лишь один элемент. В этом случае, однако, требовалось точное знание числа элементов списка, являющегося объектом предиката birds. Если зададать цель в виде birds([B1,B2,B3]), то цель не будет удовлетворена ввиду несоответствия между количеством элементов в списке и количеством элементов в целевом утверждении.
Турбо-Пролог, однако, позволяет отделять от списка первый элемент и обрабатывать его отдельно. Данный метод работает вне зависимости от длины списка, до тех пор, пока список не будет исчерпан. Этот метод доступа к голове списка называется методом разделения списка на голову и хвост.
Рассмотрим список [4, 9, 5, 3]. В этом исходном списке головой является элемент 4, а хвостом - список [9,5,3]. Головой нового списка будет уже число 9, хвостом - список [5,3]. Этот список также имеет голову 5 и хвост [3]. Наконец, список [3] состоит из головы - числа 3 и хвоста, являющегося пустым списком. Как Вы скоро увидите, неоднократное разделение списка на голову и хвост играет важную роль в программировании на Турбо-Прологе.
Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):
[Head|Tail].
Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка. (Для имен головы и хвоста списка пригодны любые допустимые Турбо-Прологом имена.)
102
Программа "Голова-хвост" (листинг 5.2) демонстрирует использования метода разделения списка. Два списка описаны в ней: список целых чисел (имя домена - number_list) и список символических имен (домен animal_list). Правило print_list применяется для доступа к элементам обоих списков.
_____________________________________________________________
Листинг 5.2
/* Программа: Голова-хвост Файл: PROG0502.PRO */
/* Назначение: Работа со списками путем |
*/ |
||
/* |
деления на голову и хвост. |
*/ |
|
domains
number_list = integer * animal_list = symbol *
predicates
print_list(number_list) print_list(animal_list)
clauses
print_list([]). print_list([Head|Tail]) :-
write(Head),nl, print_list(Tail).
/***** конец программы *****/
_____________________________________________________________
Программа "Голова-хвост" использует правило print_list([]). print_list([Head|Tail]) :-
write(Head),nl, print_list(Tail).
для доступа к элементам списков. Так как предикат print_list определен для объектов обоих доменов, то это правило используется для работы как со списком number_list, так и списком animal_list.
Когда правило пытается удовлетворить цель print_list([4,9,5,3])
то первый вариант правила, print_list[], дает неуспех, так как его объект является пустым списком. Напротив, введенный список соответствует объекту второго варианта предиката, print_list([Head|Tail]). Переменной Head, следовательно, присваивается значение первого элемента в списке, 4, в то время как переменной Tail cтавится в соответствие оставшаяся часть списка, [9,5,3].
Теперь, когда выделен первый элемент списка, с ним можно обращаться так же, как и с любым простым объектом:
write(Head),nl,
103
Так как хвост списка есть список сам по себе, значение переменной 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 завершиться успехом, когда рекурсивные вызовы опустошат весь список.
Похожий процесс имеет место и при задании цели print_list(["cat","dog","horse","cow"]).
Сначала переменной Head присваивается значение cat, cat печатается на экране, а Tail принимает значение ["dog","horse","cow"]. В дальнейшем при последовательном выполнении рекурсий все эти значения также отображаются на экран. Наконец, когда Head приняло значение последнего элемента исходного списка, cow, значением Tail становится пустой список. Вариант
print_list[]
дает успех, тем самым завершая рекурсию.
Рекурсивные правила для работы со списками просты, но вместе с тем и очень важны, ввиду их применимости в большинстве программ.
*Упражнение
5.10.Для списка ["Boston","Philadelphia","Seattle","Chicago"]
а) нарисуйте диаграмму работы со списком при помощи метода деления списка на голову и хвост; б) запишите значения голов списков в процессе работы метода. в. Напишите
рекурсивное правило, которое печатает все элементы списка через два пробела.
5.5. Различные операции над списками
Различные операции, которые можно проделать над списками, включают в себя поиск элемента в списке, деление списка на два, присоединение одного списка к другому, сортировку списка и создание списка из содержимого базы данных. Настоящий раздел посвящен технике программирования этих операций.
104
5.5.1 Поиск элемента в списке
Поиск элемента в списке является очень распространенной операцией. Поиск представляет собой просмотр списка на предмет выявления соответствия между элементом данных (объектом поиска) и элементом просматриваемого списка. Если такое соответствие найдено, то поиск заканчивается успехом. В противном случае поиск заканчивается неуспехом. Результат поиска, так же как и результат любой другой операции Турбо-Пролога, базирующейся на унификации термов, всегда бывает либо успехом, либо неуспехом. Для сопоставления объекта поиска с элементами просматриваемого списка необходим предикат, объектами которого и являются эти объект поиска и список:
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).
105