Применение ссылочных типов при реализации бинарных деревьев

В главах 15 и 8 было показано, как бинарные деревья могут применять-

ся для реализации быстрой и эффективной сортировки. Однако, сортировка

может быть реализована более элегантно с помощью ссылочных типов. Пос-

кольку невозможно изменить листья дерева, когда им уже присвоены значе-

ния, поэтому возникает необходимость копирования узлов при создании дере-

ва. Когда вам необходимо отсортировать большой объем данных, это копиро-

вание может часто приводить к ошибке переполнения памяти. Ссылочный тип

позволяет избегнуть этого за счет того, что листья деревьев остаются сво-

бодными переменными (куда впоследствии будут внесены поддеревья). С по-

мощью ссылочного типа вам нет нужды копировать дерево в том месте, где

будет вводиться новый узел.

Рассмотрим как работает предикат insert в программе CH19EX05.PRO при

оценке следующего целевого утверждения:

goal

insert("tom",Tree),

insert("dick",Tree),

insert("harry",Tree).

В этой программе с помощью предиката insert формируется бинарное де-

рево на основе ссылочного типа tree.

/* Program CH19EX05.PRO */

domains

tree = reference t(val, tree, tree)

val = string

predicates

insert(val, tree)

clauses

insert(ID, t(ID,_,_)) :- !.

insert(ID, t(ID1,Tree,_)) :- ID<ID1, !, insert(Val, Tree).

insert(ID, t(_,_,Tree)) :- insert(Val, Tree).

Первая подцель, insert("tom",tree), соответствует первому правилу и

сложный объект принимает вид

t("to",_,_)

Хотя последние два аргумента в t являются свободными, объект t пере-

дается дальше в следующую подцель

insert("dick",Tree)

При этом Tree получает следующее значение

t("tom",t("dick",_,_),_)

Наконец, с помощью подцели

insert("harry",Tree)

Tree получает значение

t("tom",t("dick",_,t("harry",_,_)),_)

что и является результатом выполнения всего целевого утверждения.

Сортировка с помощью ссылочных типов

В этом разделе мы расширим предыдущий пример с бинарным деревом

(CH19EX05.PRO), чтобы показать как вы можете использовать ссылочные типы

и преобразовывать переменные из ссылочного в обычный тип.

/* Program CH19EX05.PRO */

domains

tree = reference t(val, tree, tree)

val = integer

list = integer*

predicates

insert(integer, tree)

instree(list, tree)

treemembers(integer, tree)

sort(list, list)

clauses

insert(Val, t(Val,_,_)) :- !.

insert(Val, t(Val1,Tree,_)) :- Val<Val1, !, insert(Val, Tree).

insert(Val, t(_,_,Tree)) :- insert(Val, Tree).

instree([],_).

instree([H|T], Tree) :-

insert(H, Tree),

instree(T, Tree).

treemembers(_, T) :- free(T), !, fail.

treemembers(X, T(Refstr,_,_)) :- X = Refstr.

treemembers(X, t(_, _, R)) :- treemembers(X, R).

treemembers(X, t(_, L,_)) :- treemembers(X, L).

sort(L, L1) :-

instree(L, Tree),

findall(X, treemembers(X, Tree), L1).

goal

sort([3, 6, 4, 5], L).

В этом примере обратите внимание на то, что ссылочный тип использу-

ется только для получения дерева. Все остальные аргументы относятся к

обычному типу.

Для более глубокого изучения ссылочных типов обратитесь к разделу

"Метапрограммирование".