Traverse(tree(X,Y,Z):- do something with X, traverse(Y),

Traverse(Z).

Для практичної реалізації розглянемо програму, яка обходить дерево й виводить на екран значення, що містяться у вузлах дерева:

Domains

treetype = tree(string, treetype, treetype);

Empty()

Predicates

print_all_elements(treetype)

Clauses

print_all_elements(empty).

print_all_elements(tree(X,Y,Z)):- write(X), nl,

print_all_elements(Y),

print_all_elements(Z).

goal: print_all_elements(tree("Перро", tree("Грімм",

tree("Гауф", empty, empty),

tree("Лондон", empty, empty)),

tree("Кіплінг", tree("Уайльд", empty,

empty), tree("Лагерлеф", empty,

Empty)))).

 

Для значної кількості задач інколи потрібно створити структуру даних типу дерево в пам'яті комп'ютера з подальшою її обробкою.

Один вузол дерева можна створити так:

create_tree(N, tree(N,empty,empty)).

Цей предикат можна інтерпретувати так: „Якщо N є елемент даних, то tree(N,empty,empty) – це вузл дерева, який містить цей елемент”.

Процес побудови дерева трохи складніший. Розглянемо фразу, яка містить предикат із трьома аргументами типу дерево. Він вставляє перше дерево як ліве піддерево другого дерева, використовуючи третє дерево як результуюче:

insert_left(X, tree(A, _, B), tree(A,X,B)).

Припустимо, наприклад, що ми хотіли б вставити

Tree('Грімм ', empty, empty)

як ліве піддерево:

Tree('Перро', empty, empty).

Це можна зробити, сформувавши запит

goal: insert_left(tree(' Грімм ',empty,empty),

Tree('Перро ',empty,empty),T)

де T зразу ж набуде значення tree('Перро', tree(Грімм ',empty,empty), empty).

Отже, ми поетапно можемо побудувати дерево. Наведена нижче програма демонструє застосування запропонованого підходу для побудови дерева. На практиці елементи, розміщені у вузлах дерева, майже завжди беруть із зовнішнього файлу. Для виконання цієї програми необхідно у Visual Prolog вибрати в меню Project пункт New project, ввести ім’я проекту й ім’я файлу проекту, перейти на вкладку target, у списку UI Strategy вибрати Easywin, створити проект і скопіювати текст програми у файл із розширенням .pro, згенерований Visual Prolog ' ом. Для запуску програми слід застосувати команду R із панелі інструментів.

 

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* Прості процедури побудови дерева. *

* create_tree(A, B) вставляє A в поле даних дерева B *

* insert_left(A, B, C) вставляє A як ліве піддерево B, *

* отримуючи дерево C *

* insert_right(A, B, C) вставляє A як праве піддерево B, *

* отримуючи дерево С *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

Domains

treetype = tree(string, treetype, treetype);

Empty()

Predicates

create_tree(string, treetype)

insert_left(treetype, treetype, treetype)

insert_right(treetype, treetype, treetype)

Clauses

create_tree(A, tree(A, empty, empty)).

insert_left(X, tree(A, _, B), tree(A, X, B)).

insert_right(X, tree(A, B,_), tree(A, B, X)).

Goal

/* Спочатку створимо вузли (однорівневі дерева)... */

create_tree("Гауф", Ch), create_tree("Лондон", H),

create_tree("Грімм", Mi), create_tree("Уайльд", J),

create_tree("Лагерлеф", E), create_tree("Кіплінг", Me),

create_tree("Перро", Ca),

/*... потім установимо зв'язки */

insert_left(Ch, Mi, Mi2), insert_right(H, Mi2, Mi3),

insert_left(J, Me, Me2), insert_right(E, Me2, Me3),

insert_left(Mi3,Ca, Ca2), insert_right(Me3, Ca2, Ca3),

/*... і роздрукуємо результат. */

Write(Ca3), nl.

Оскільки в мові Пролог ми не можемо змінити значення змінної, а можемо лише пов'язати змінну з якимсь значенням, ця програма містить так багато змінних.

 

Бінарний пошук на дереві

 

Ми описали використання дерева для задання відношень між його елементами. Це не найкращий спосіб використання дерева в мові Пролог, оскільки будь-яка фраза Прологу може виконати таку роботу. Але використання дерева має інші переваги. Розглянемо спеціальний тип бінарного дерева, яке називають бінарним деревом пошуку. Його будують у такий спосіб:

1) якщо поточний вузол – порожнє дерево, то вставляють елемент у нього;

2) у противному разі порівнюють вставлюваний елемент з елементом, який зберігається в поточному вузлі. Якщо значення нового елемента менше, то вставляють новий елемент у ліве піддерево поточного вузла, а якщо більше – у праве піддерево поточного вузла.

Для того щоб побудувати бінарне дерево пошуку в мові Пролог, потрібна наявність трьох фраз. Перша з них

insert(NewItem,empty, tree(NewItem,empty,empty):-!.

означає, що результатом вставки елемента NewItem у порожнє дерево буде дерево tree(NewItem, empty,empty).

Друга й третя фрази реалізують відповідно лівосторонню або правосторонню вставку в непорожнє дерево:

Insert(NewItem,

Tree(Element,Left,Right),

tree(Element,NewLeft,Right)):- NewItem < Element,!,

Insert (NewItem, Left, NewLeft).

Insert(NewItem,

Tree(Element,Left,Right),

Tree(Element, Left, NewRight)):-

Insert(NewItem, Right, NewRight).

Сортування за деревом

 

Якщо бінарне дерево пошуку вже побудовано, дуже просто розмістити всі його елементи в лексикографічному порядку. Рекурсивний алгоритм буде включати зворотний обхід дерева:

1) якщо дерево порожнє, то нічого не треба робити;

2) у противному разі слід переглянути всі елементи лівого піддерева, потім – поточний елемент, потім – усі елементи правого піддерева.

Мовою Пролог вищевказані операції можна записати так:

 

retrieve_all(empty).

retrieve_all(tree(Item,Left,Right)):- retrieve_all(Left),

do_something_to(Item),

retrieve_all(Right).

Таким чином, застосовуючи сортування за деревом, можна швидко впорядковувати елементи. Таке впорядкування одне з найефективніших. Так, для N елементів часова оцінка роботи алгоритму буде О (N log N).

 

Лексикографічне впорядкування

 

У розглядуваній програмі ми будемо використовувати вмонтовані предикати мови Пролог для реалізації введення з клавіатури. Так, предикат READINT вводить цілі, а предикат READCHAR – символи. Стандартний предикат EXIT зупиняє процес виконання.

Domains

chartree = tree(char, chartree, chartree);

End

Predicates

Nondeterm do(chartree)

Action(integer, chartree, chartree)

create_tree(chartree, chartree)

Insert(char, chartree, chartree)

write_tree(chartree)

Nondeterm repeat

goal do(end).

Clauses

Do(Tree):-

Repeat,

write("Enter 1 to create a tree\n"),

write("Enter 2 to show tree\n"),

write("Enter 7 to exit\n"),

Readint(X),

Action(X, Tree, NewTree),

Do(NewTree).

Action(1, Tree, NewTree):-

write("Enter characters or. to end: "),

create_Tree(Tree, NewTree).

Action(2, Tree, Tree):-

write_Tree(Tree),

write("\nPress a key to continue\n"),

readchar(_).

action(7, _, end):- exit.

create_Tree(Tree, NewTree):-

Readchar(C),

C <> '.',!,

write(C, " "),

Insert(C, Tree, TempTree),

create_Tree(TempTree, NewTree).

create_Tree(Tree, Tree).

insert(New, end, tree(New, end, end)):-!.

Insert(New,

Tree(Element, Left, Right),

Tree(Element, NewLeft, Right)):-

New < Element,!,

Insert(New, Left, NewLeft).

Insert(New, tree(Element, Left, Right),

Tree(Element, Left, NewRight)):-

Insert(New, Right, NewRight).

write_Tree(end).

write_Tree(tree(Item, Left, Right)):-

write_Tree(Left),

write(Item, " "),

write_Tree(Right).

Repeat.

Repeat:-repeat.

Списки

 

Список – це структура даних, яка може зберігати довільну кількість однотипних елементів, наприклад:

[ ]

[1, 2, 3, 4, 5]

[tom, ann, john, bob]

Першим наведено порожній список. Непорожній список складається з двох елементів – голови і хвоста. Голова – перший елемент списку, інша частина списку – хвіст. Наприклад, в останньому списку tom – це голова, [ann, john, bob] – це хвіст списку. Список можна явно поділити на голову і хвіст за допомогою вертикальної риски:

[tom | [ann, john, bob]]

Насправді вертикальна риска має більш загальний зміст, нею можна виділити довільну кількість елементів: [tom, ann | [john, bob]], [tom, ann, john, bob] | [ ]].

Списки, як і всі структурні об’єкти в мові Пролог, – це дерева. Зокрема, третій список можна зобразити у вигляді дерева, показаного на рис. 9. Списки зручно використовувати, коли кількість компонентів у структурі змінна. Наприклад, якщо ми хочемо створити БД, у якій зберігаються прізвища викладачів і назви дисциплін, які вони викладають, її можна реалізувати таким чином:

 

Domains

teacher = string

courses_list = string*

Predicates

info(teacher, courses_list)

Clauses

info("Шевченко О.В.", ["Інформатика", "Чисельні методи"]).

info("Нікольський А.С.", ["Комп’ютерна графіка"]).

info("Рябчук М.В.", ["Фізика", "Хімія", "Астрономія"]).

Goal

info("Рябчук М.В.", X), write (X), nl.

 

 

Рис. 9. Зображення списку у вигляді дерева

 

Як видно, кількість дисциплін може варіюватися від нуля до довільної кількості. Списки описують за допомогою знака „*” (зірочка).

Основні операції зі списками такі:

- перевірка об’єкта на належність до списку;

- конкатенація (зчеплення) двох списків;

- додавання або вилучення об’єкта зі списку.

Операції зі списками програмують із застосуванням рекурсії. У процесі обробки списку його розбивають на голову і хвіст. Процедура зазвичай складається з двох правил: у першому описують окремий випадок, у другому – більш загальний випадок.

Приклади

Перевірку об’єкта на належність до списку реалізують на основі таких міркувань:

1) об’єкт є головою списку;

2) об’єкт належить списку, якщо об’єкт належить хвосту списку.

Ці речення мовою Пролог записують так:

 

member(X, [X | Tail]).

member(X, [Head | Tail]):-

Member(X, Tail).

 

Конкатенацію (зчеплення) двох списків реалізують у вигляді предиката з трьома аргументами: перший і другий аргументи – два вхідні списки, третій аргумент – вихідний список. Нижчеподані фрази показують, як зчепити два списки:

1) якщо перший аргумент порожній, то другий і третій аргументи являють собою один і той же список;

2) якщо перший аргумент непорожній, то він має голову й хвіст, а результатом зчеплення буде список, який складається з голови першого списку та зі списку, який становить конкатенацію хвоста першого списку і всього другого списку.

Мовою Пролог ці фрази записують таким чином:

 

append([], List, List).

append([X|L1], List2, [X|L3]):-

Append(L1, List2, L3).

 

Додати об’єкт до списку можна без будь-якої процедури, просто записуючи його у вигляді голови списку: [X | List]. Якщо ж треба явно описати процедуру додавання об’єкта до списку, її можна записати у вигляді факту:

 

add(X, List, [X | List]).

 

Вилучення об’єкта зі списку можна описати як предикат, що має три аргументи: 1) сам об’єкт; 2) початковий список; 3) результуючий список. Відношення вилучення записують двома реченнями:

1) якщо Х – голова списку, то результатом вилучення буде хвіст цього списку;

2) якщо Х знаходиться у хвості списку, то його треба вилучити звідти.

Мовою Пролог зазначене вище можна переписати так:

 

remove(X, [X | Tail], Tail).

remove(X, [Y | Tail], [Y | Tail1]):-

Remove(X, Tail, Tail1).

 

Пролог має і вбудований предикат для роботи зі списками – findall. За допомогою нього можна зібрати всі розв’язки цілі в один список. Загальна форма така: