Составные объекты
Составные объекты данных позволяют рассматривать информацию, состоящую из нескольких частей, как единое целое, в то же время предоставляя возможность получать доступ к отдельным частям этой информации.
Например, дата рождения человека может быть представлена как единый объект, и в то же время, дата состоит из трех частей, числа, месяца и года. Такую составную структуру можно представить как единое целое, использовав функтор, например, birthday. Имя функтора выбирается произвольно. Тогда структура будет выглядеть следующим образом:
birthday (25, “мая”, 1980)
Секция описания доменов будет выглядеть следующим образом:
DOMAINS
day=birthday (integer, symbol, integer)
Такое описание домена позволит определить предикат, в котором в качестве аргумента можно использовать данные, принадлежащие домену day. Далее следует пример программы с использованием данного домена.
DOMAINS
day=birthday (integer, string, integer)
name=string
PREDICATES
congratulation (name, day)
print
print2
CLAUSES
congratulation (“Анна”, birthday (25, “мая”, 1980)).
congratulation (“Иван”, birthday (17, “декабря”, 1957)).
congratulation (“Петр”, birthday (30, “июля”, 2001)).
print:- congratulation (Name, birthday (Day, Month, Year)), write (“С днем рождения ”, Day, Month, Year, ”, ”, Name,”!”), nl, fail.
print.
print2:- congratulation (Name, Birthday), write (“С днем рождения ”, Birthday, ”, ”, Name,”!”), nl, fail.
print2.
GOAL
print, print2.
Как видно из вышеприведенного примера, к составному объекту можно обратиться как единому целому, так и получить доступ к его составным элементам.
Списки
Список – это объект, который содержит конечное число других объектов. Список в Prolog’е можно приблизительно сравнить с массивами в других языках, но для списков нет необходимости заранее объявлять размерность.
Список в Prolog’е заключается в квадратные скобки, и элементы списка разделяются запятыми. Список, который не содержит ни одного элемента, называется пустым списком.
Примеры списков:
список, элементами которого являются целые числа
[1, 2, 3]
список, элементами которого являются символы
[one, two, three]
список, элементами которого являются строки
[“One”, “Two”, “Three”]
пустой список
[ ]
Для работы со списками с Prolog’е не существует отдельного домена, для того, чтобы работать со списком, необходимо объявить списочный домен следующим образом:
DOMAINS
listdomain=elementdomain*
elementdomain=…
listdomain – это произвольно выбранное имя нестандартного списочного домена, elementdomain – имя домена, которому принадлежит элемент списка, звездочка * как раз и обозначает, что выполнено объявление списка, состоящего из элементов домена element. При работе со списками нельзя включать в список элементы, принадлежащие разным доменам. В таком случае нужно воспользоваться составным доменом.
Примеры объявления списочных доменов:
DOMAINS
%элементы списка – целые числа
intlist=integer*
%элементы списка – символы
symlist=symbol*
%элементы списка – строки
strlist=string*
%элементы списка – или целые числа, или символы, или строки
mixlist=mixdomain*
mixdomain=int(integer); sym(symbol); str(string)
Обратите внимание, что при объявлении составного домена были использованы функторы, так как объявление вида mixdomain=integer; symbol; string привело бы к ошибке.
Список является рекурсивным составным объектом, состоящим из двух частей. Составные части списка:
Голова списка – первый элемент списка;
Хвост списка – все последующие элементы, являющиеся, в свою очередь списком.
Примеры голов и хвостов списков:
[1, 2, 3] голова списка – 1, хвост списка – [2, 3]
[1] голова списка – 1, хвост списка – [ ]
[ ] пустой список нельзя разделить на голову и хвост
В Prolog’е используется специальный символ для разделения списка на голову и хвост – вертикальная черта |.
Например:
[1, 2, 3] или [1 | [2, 3]] или [1 | [2| [3]]] или [1 | [2 | [3 | [ ]]]]
[1] или [1 | [ ]]
Вертикальную черту можно использовать не только для отделения головы списка, но и для отделения произвольного числа начальных элементов списка:
[1, 2, 3] или [1, 2 | [3]] или [1, 2, 3 | [ ]]
Примеры сопоставления и унификации в списках:
[1, 2, 3]=[Elem1, Elem2, Elem3] Elem1=1, Elem2=2, Elem3=3
[1, 2, 3]=[Elem1, Elem2, Elem3 | T] Elem1=1, Elem2=2, Elem3=3, T=[ ]
[1, 2, 3]=[Head | Tail] Head=1, Tail=[2, 3]
[1, 2, 3]=[Elem1, Elem2 | T] Elem1=1, Elem2=2, T=[3]
[1, 2, 3]=[4 | T] ошибка
[ ]=[H | T] ошибка
Так как список является рекурсивной структурой данных, то для работы со списками используется рекурсия. Основной метод обработки списков заключается в следующем: отделить от списка голову, выполнить с ней какие-либо действия и перейти к работе с хвостом списка, являющимся в свою очередь списком. Далее у хвоста списка отделить голову и так далее до тех пор, пока список не останется пустым. В этом случае обработку списка необходимо прекратить. Следовательно, предикаты для работы со списками должны иметь, по крайней мере, два предложения: для пустого списка и для непустого списка.
Пример: поэлементный вывод списка, элементами которого являются целые числа, на экран (нужно отметить, что этот пример приводится в учебных целях, список вполне может быть выведен на экран как единая структура, например, GOAL List=[1, 2, 3], write(List)).
DOMAINS
intlist=integer*
PREDICATES
printlist (intlist)
CLAUSES
%если список пустой, то выводить не экран нечего
printlist ([ ]):- !.
%если список непустой, то отделить от списка голову, напечатать ее и
%использовать тот же самый предикат для печати хвоста списка, то есть
%выполнить рекурсивный вызов предиката printlist, передав в качестве
%аргумента хвост
printlist ([H | T]):- write (H), nl, printlist (T).
GOAL
printlist ([1, 2, 3]).
Результат работы программы:
1
2
3
Еще один пример работы со списком – подсчет числа элементов списка или, другими словами, определение длины списка. Для того чтобы определить длину списка, вновь нужно рассмотреть два случая: для пустого и непустого списков. Если список пуст, то его длина равна 0, если же список не пуст, то определить его длину можно следующим образом: разделить список на голову и хвост, подсчитать длину хвоста списка и увеличить длину хвоста на единицу (то есть учесть отделенную предварительно голову списка.)
DOMAINS
intlist=integer*
PREDICATES
list_length (intlist, integer)
CLAUSES
%если список пустой, то его длина равна 0
list_length ([ ], 0):- !.
%если список непустой, то его длина равна длине хвоста, увеличенной на 1
list_length (List, Length):- List=[H | T], list_length (T, Length_T), Length=Length_T+1.
%более кратко второе правило вывода можно записать, перенеся разделение
%списка на голову и хвост в заголовок предложения и избавиться от лишней
%переменной List
%list_length ([H | T], Length):- list_length (T, Length_T), Length=Length_T+1.
GOAL
listlength ([1, 2], Length), write(“Length=”, Length).
Результат работы программы:
Length=2
Для того чтобы лучше понять, каким образом работает приведенный пример, удобно воспользоваться деревом целей. В данном примере следует обратить внимание на то, каким образом формируется выходное значение – длина списка. Счетчик для подсчета числа элементов в списке обнуляется в момент, когда рекурсия останавливается, то есть список разбирается до пустого списка-хвоста и результат насчитывается при выходе из рекурсии.
Достаточно часто необходимо обработать список поэлементно, выполняя некоторые действия с элементами списка, в зависимости от соблюдения некоторых условий. Предположим, необходимо преобразовать список, элементами которого являются целые числа, инвертируя знак элементов списка, то есть положительные числа преобразовать в отрицательные, отрицательные в положительные, для нулевых значений никаких действий не предпринимать. Вновь придется рассмотреть два случая – для непустого и пустого списков. Преобразование пустого списка дает в результате такой же пустой список. Если же список не пуст, то следует рекурсивно выполнять отделение головы списка, ее обработку и рассматривать полученный результат как голову списка-результата.
DOMAINS
intlist=integer*
PREDICATES
inverting (intlist, intlist)
processing (integer, integer)
CLAUSES
%обработка пустого списка дает, в результате, тоже пустой список
inverting ([ ], [ ]):- !.
%если список непустой, отделить голову, обработать ее,
%и добавить в качестве головы списка-результата
inverting ([H | T], [Inv_H | Inv_T]):- processing (H, Inv_H), inverting (T, Inv_T).
%предикат processing выполняет действия по обработке элемента списка в
%зависимости от его знака, предикат имеет два предложения, так как нужно
%рассмотреть два варианта: ненулевое и нулевое значения
processing (0, 0):- !.
processing (H, Inv_H):- Inv_H=-H.
GOAL
inverting ([-2, -1, 0, 1, 2], Inv_List), write(“Inv_List=”, Inv_List).
Результат работы программы:
Inv_List=[2, 1, 0, -1, -2]
Следующий пример рассматривает достаточно часто встречающуюся задачу – определение принадлежности элемента списку. Проверка принадлежности элемента списку выполняется достаточно просто – отделением головы списка и сравнением ее с искомым элементом. Если сравнение завершилось неудачей, продолжается поиск элемента в хвосте списка. Признаком наличия искомого элемента в списке будет успешное доказательство цели, если же цель не была доказана, значит, такого элемента в списке нет.
DOMAINS
strlist=string*
PREDICATES
member (string, strlist)
search (string, strlist)
CLAUSES
%искомый элемент найден, его значение совпало со значением головы списка,
%хвост списка обозначен анонимной переменной, так как теперь хвост списка
%не важен
member (Elem, [Elem | _]):- !.
%если элемент пока не обнаружен, попробовать найти его в хвосте списка,
%теперь для головы списка использована анонимная переменная, поскольку ее
%значение не важно, так как оно точно не равно искомому значению
member (Elem, [_ | T]):- member (Elem, T).
%предикат search служит для двух целей: во-первых, чтобы сообщить о
%результатах поиска, и, во-вторых, чтобы при любом исходе поиска программа
%всегда заканчивала свое выполнение с успехом
search (Elem, List):- member (Elem, List), !, write (“Элемент найден! :-) ”).
search (_, _):- write (“Элемент не найден! :-( ”).
GOAL
Cityes=[“Москва”, “Санкт-Петербург”, “Омск”, “Новосибирск”, “Томск”], City=“Новосибирск”, search (City, Cityes).
Результат работы программы:
Элемент найден! :-)
Последний пример, который будет рассмотрен, это решение задачи соединения двух списков. Итак, каким образом можно объединить два списка? Предположим, имеется два двухэлементных списка: [1, 2] и [3, 4]. Объединение нужно начать с последовательного отделения голов первого списка до тех пор, пока первый список не станет пустым. Как только первый список станет пустым, его легко можно будет объединить со вторым, непустым, никоим образом к этому моменту не изменившимся списком. В результате, естественно, будет получен список, полностью совпадающий со вторым. Все, что осталось сделать, это добавить головы, отделенные от первого списка, ко второму списку. Вот как это выглядит в пошаговом описании:
отделяется голова от первого списка – [1, 2] –> [1 | [2]] (голова – 1, хвост – [2])
продолжается выполнение отделение головы, только теперь от полученного хвоста – [ 2] –> [2 | [ ]] (голова – 2, хвост – [ ])
когда первый список разобран до пустого, можно приступить к его объединению со вторым, непустым списком, объединяются пустой хвост [ ] и непустой второй список [3, 4] – получается тоже непустой список – [3, 4], теперь можно приступать к формированию объединенного списка, так как основа для списка-результата заложена, это его будущий хвост – [3, 4]
к хвосту списка-результата [3, 4] добавляется последняя отделенная от первого списка голова 2, что дает следующий список – [2, 3, 4]
все, что осталось сделать, это добавить к списку [2, 3, 4], который получился на предыдущем шаге, голову 1, которая была отделена самой первой и получается объединенный список [1, 2, 3, 4]
Теперь, собственно, текст программы:
DOMAINS
intlist=integer*
PREDICATES
append (intlist, intlist, intlist)
CLAUSES
%объединение пустого и непустого списков
append ([ ], List, List):- !.
%объединение двух непустых списков
append ([H | T], List, [H | App_T]):- append (T, List, App_T).
GOAL
append ([1, 2], [3, 4], App_List), write(“App_List=”, App_List).
Результат работы программы:
App_List=[1, 2, 3, 4]
Деревья
Дерево, как и список, также является рекурсивным составным объектом, но, в отличие от списка, в дереве можно выделить три составные части (сразу же следует оговорить, что далее речь пойдет только о двоичных, или бинарных деревьях). Составные части двоичного (бинарного) дерева:
Левое поддерево, являющееся, в свою очередь деревом;
Корень дерева;
Правое поддерево, также являющееся деревом.
В графическом виде дерево может быть представлено, например, так:
На следующем рисунке обозначены три составные части дерева.
Каждый узел дерева, приведенного в качестве примера, содержит целое число. Если для всего дерева соблюдается определенное правило расположения значений в узлах дерева, то такое дерево называют упорядоченным. Правило формулируется следующим образом: дерево можно назвать упорядоченным, если все значения, находящиеся в узлах левого поддерева, меньше значения в корне дерева, а все значения, находящиеся в узлах правого поддерева, больше значения в корне дерева.
Это правило должно соблюдаться как для левого, так и для правого поддеревьев, и для их левых и правых поддеревьев (ведь дерево – это рекурсивная структура, и как левое, так и правое поддеревья также являются полноценными деревьями).
Для дерева, приведенного выше в качестве примера, это правило соблюдается, следовательно, это дерево упорядочено.
5 больше –1, 2 и 4, и 5 меньше 7 и 9 (для дерева в целом)
2 больше –1, и 2 меньше 4 (для левого поддерева)
9 больше чем 7 (для правого поддерева)
Узлы дерева, у которых нет левого и правого поддерева, называется листьевыми узлами или вершинами. В рассматриваемом дереве это узлы, которые содержат значения –1, 4 и 7. Отсутствующие у этих узлов левое и правое поддеревья можно назвать пустыми деревьями.
Пустое дерево – это дерево, в котором нет ни одного узла.
Если обозначить на рисунке пустые поддеревья, то это может выглядеть, например, так:
Заштрихованные кружочки как раз и обозначают пустые деревья, или, другими словами, отсутствующие левое и/или правое поддеревья у какого либо узла.
В Prolog’е для представления деревьев не существует отдельного домена, для того, чтобы работать с деревом, необходимо объявить новый нестандартный домен. При этом следует учитывать, что, во-первых, дерево – структура рекурсивная, во-вторых, дерево – структура, состоящая их трех частей, и, в-третьих, дерево может быть пустым или непустым. Все эти особенности учитываются в следующем объявлении домена:
DOMAINS
%домен_для_дерева=функтор_непустого_дерева(корень, левое_поддерево, правое_поддерево) ;
% функтор_пустого_дерева()
treetype=tree (integer, treetype, treetype) ; empty ()
Treetype – это имя нестандартного домена для представления дерева, рекурсивность структуры дерева обеспечивается использованием рекурсивного описания домена, treetype дважды используется справа от знака равенства и описывает, соответственно, домен левого и правого поддеревьев.
Integer – описание домена для значения, находящегося в корневом узле дерева. Объединить в единое дерево три его составные части позволяет использование функтора tree с тремя аргументами. Для описания двух возможных состояний, в которых может находиться дерево, пустого и непустого, используются, соответственно, два функтора – tree и empty. Так как у пустого дерева нет ни корня, ни левого и правого поддеревьев, то и функтор empty не имеет аргументов (используются пустые скобки после empty). В этом случае пустые скобки можно и не использовать.
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
При объявлении домена было использовано только одно зарезервированное слово – integer, все остальные имена выбраны произвольно. В следующем примере также описан домен для представления дерева, только использованы другие имена.
DOMAINS
a=b (integer, a, a) ; c
Такое определение позволяет записать следующую структуру данных (для дерева, приведенного на рисунке):
tree (5,
tree (2,
tree (-1, empty, empty),
tree (4, empty, empty)),
tree (9,
tree (7, empty, empty),
empty))
Вот пример программы, выводящей на экран дерево, как единый объект:
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
GOAL
OrderTree=tree (5, tree (2, tree (-1, empty, empty), tree (4, empty, empty)), tree (9, tree(7, empty, empty), empty)), write (“Tree=”, OrderTree).
Результат работы программы:
Tree=tree(5,tree(2,tree(-1,empty,empty),tree(4,empty,empty)),
tree(9,tree(7,empty,empty),empty))
Одной из наиболее частых операций, выполняемых с деревом, является исследование всех узлов дерева и обработка их некоторым образом. Последовательная обработка всех узлов дерева называется обходом дерева. В зависимости от того, в какой очередности обрабатываются корень дерева и его поддеревья, различают несколько направлений обхода дерева:
Корень, левое поддерево, правое поддерево обход «сверху вниз»;
Левое поддерево, правое поддерево, корень обход «снизу вверх»;
Левое поддерево, корень, правое поддерево обход «слева направо»;
Правое поддерево, корень, левое поддерево обход «справа налево»;
Так как дерево является рекурсивной структурой данных, то для работы с деревьями используется рекурсия. Основной метод обработки дерева заключается в следующем: разделить дерево на корень, левое поддерево и правое поддерево, выполнить какие-либо действия с корнем дерева, и перейти к обработке левого поддерева, а затем правого поддерева, являющимися, в свою очередь, деревьями. Обработка каждого из поддеревьев заключается в разделении их на три части и последовательной обработке каждой из частей.
Деление деревьев продолжается до тех пор, пока очередное поддерево не станет пустым. В этом случае обработку дерева необходимо прекратить. Следовательно, предикаты для работы с деревьями должны иметь, по крайней мере, два предложения: для пустого дерева и для непустого дерева.
Пример: поэлементный вывод дерева, в узлах которого хранятся целые числа, на экран (нужно отметить, что этот пример приводится в учебных целях, дерево вполне может быть выведено на экран как единая структура (см. предыдущий пример)).
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
PREDICATES
printtree (treetype)
CLAUSES
%если дерево пустое, то выводить не экран нечего
printtree (empty):- !.
%если дерево непусто, то разделить дерево на корень, левое и правое поддеревья,
%напечатать корень и использовать тот же самый предикат для печати левого,
%а затем правого поддеревьев, то есть выполнить рекурсивные вызовы
%предиката printtree, передав в качестве аргумента сначала левое, а затем правое
%поддеревья
printtree (tree (Root, Left, Right)):- write (Root), write (“ ”), printtree (Left),
printtree (Right).
GOAL
printtree (tree (5, tree (2, tree (–1, empty, empty), tree (4, empty, empty)), tree (9, tree(7, empty, empty), empty))).
Результат работы программы обхода дерева «сверху вниз»:
5
2
–1
4
9
7
Если же второе предложение для предиката printlist переписать для выполнения обхода «слева направо»
printtree (tree (Root, Left, Right)):- printtree (Left), write (Root), write (“ – ”),
printtree (Right).
то результат работы будет следующим, так как дерево упорядочено:
–1
2
4
5
7
9
Еще один пример работы с деревом – подсчет числа узлов дерева. Для того чтобы определить количество узлов дерева, вновь нужно рассмотреть два случая: для пустого и непустого деревьев. Если дерево пусто, то количество узлов в таком дереве равно 0. Если дерево не пусто, то определить количество узлов в дереве в целом можно следующим образом: разделить дерево на корень, левое и правое поддеревья, подсчитать число узлов в, левом поддереве, затем в правом поддереве. Зная количество узлов в каждом поддереве достаточно сложить эти значения и прибавить к получившей сумме единицу (учесть, таким образом, корень). Результат и будет общим числом узлов в дереве.
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
PREDICATES
counter (treetype, integer)
CLAUSES
%число узлов в пустом дереве равно 0
counter (empty, 0):- !.
%если дерево непусто, общее количество узлов дерева равно сумме узлов
%левого и правого поддеревьев, увеличенной на 1
counter (tree (Root, Left, Right), Count):- counter (Left, CountLeft), counter (Right, CountRight), Count=CountLeft+CountRight+1.
GOAL
counter (tree (5, tree (2, tree (–1, empty, empty), tree (4, empty, empty)), tree (9, tree(7, empty, empty), empty)), N), write(“N=”, N).
Результат работы программы:
N=6
Для того чтобы лучше понять, каким образом работает приведенный пример, рекомендуется самостоятельно построить дерево целей, в качестве основы можно взять деревья целей для примеров работы со списками.
И еще один пример по работе с деревьями – создание упорядоченного дерева. Пусть в узлах дерева содержатся символы, символы, добавляемые к дереву, не должны повторяться (программа не выполняет проверки на существование вводимых символов в дереве). Символы вводятся с клавиатуры, символ ‘#’ – признак конца ввода символов.
DOMAINS
treetype=tree (char, treetype, treetype) ; end
PREDICATES
insert (char, treetype, treetype)
create_tree (treetype, treetype)
CLAUSES
%предикат insert обеспечивает вставку введенного с клавиатуры символа в дерево,
%для предиката insert записывается три правила вывода, в которых рассматривается
%три случая: первый случай – вставка нового символа в пустое дерево,
%второй и третий случаи – вставка нового символа в непустое дерево,
%если новый символ меньше, чем символ в корне дерева, то новый символ добавляется
%в левое поддерево, если больше – в правое
%(для сравнения символов используются их ASCII-коды)
%вставка нового символа в пустое дерево, получается дерево с корнем и пустыми
%левым и правым поддеревьями
insert (New, end, tree (New, end, end)):- !.
%вставка нового символа по результатам проверки в левое поддерево,
%левое поддерево изменяется, а правое остается без изменений
insert (New, tree (Root, Left, Right), tree (Root, NewLeft, Right)):- Newinsert (New, Left, NewLeft).
%вставка нового символа в правое поддерево, без проверки,
%правое поддерево изменяется, а левое остается без изменений
insert (New, tree (Root, Left, Right), tree (Root, Left, NewRight)):-
insert (New, Right, NewRight).
%предикат create_tree обеспечивает ввод символа с клавиатуры, и вызов предиката insert
create_tree (Tree, NewTree):- readchar(Ch), Ch<>’#’, !,
insert (Ch, Tree, TmpTree), create_tree (TmpTree, NewTree).
create_tree (Tree, Tree).
GOAL
create_tree (end, Tree), write(“Tree=”, Tree).
Результат работы программы:
Tree=tree('d',tree('a',end,tree('b',end,tree('c',end,end))),tree('f',tree('e',end,end),tree('g',end,end)))
С клавиатуры была введена последовательность:
‘d’ ‘a’ ‘f’ ‘b’ ‘e’ ‘g’ ‘c’ ‘#’
|
Скачать 410 Kb.