1.4.5.2 Предикат может иметь несколько вариантов использования

Состояние аргументов при вызове предиката называется потоком параметров. Аргу­мент, который присваивается или назначается в момент вызова, называется входным аргументом и обозначается буквой i; а свободный аргумент — это выходной аргу­мент, обозначается буквой o.

У предиката append есть возможность работать с разными потоками параметров, в зависимости от того, какие исходные данные вы ему дадите. Однако не для всех предикатов имеется возможность быть вызванными с различными потоками пара­метров. Если предложение Пролога может быть использовано с различными пото­ками параметров, оно называется обратимым предложением. Когда вы записываете собственные предложения в Прологе, помните, что обратимые предложения имеют дополнительные преимущества, и их создание добавляет "мощности" преди­катам.

Работа с деревьями в языке Пролог.

Структурой вводимого нами типа данных является дерево (рисунок 1). Каждая ветвь дерева сама является деревом, поэтому структура рекурсивна.

Обход дерева

Одной из наиболее часто осуществляемых операций с деревом является исследование всех узлов и обработка их некоторым образом, либо поиск некоторого значения, либо сбор всех значений. Эти процедуры известны как обход дерева. Основной алгоритм для этого следующий:

1. Если дерево пусто, то ничего не делать.

2. Иначе, обработать текущее значение, затем перейти на левое поддерево, затем перейти на правое поддерево.

Как и само дерево, алгоритм является рекурсивным: он обрабатывает левое и правое поддеревья так же, как и исходное дерево. В Прологе он выражается двумя предложениями: одно для пустого, а другое для непустого дерева.

traverse (empty). % ничего не делать

traverse (tree (X, Y, Z)) :-

do_something_with_X,

traverse(Y),

traverse(Z).

Этот алгоритм известен как поиск "сначала – вглубь", т.к. он спускается по каждой ветви вниз, насколько возможно, прежде чем вернуться вверх для обхода другой ветви (рисунок 2). Он организует предложения в дерево и проходит каждое поддерево, пока предложения не закончатся. Вы могли бы описать дерево посредством набора правил Пролога, таких как:

father_of("Cathy", "Michael").

mother_of("Cathy", "Melody").

…

Это было бы предпочтительнее, если бы дерево предназначалось только для выражения родственных связей между людьми. Но такой вид описания делает невозможным обработку всего дерева как единой, сложной структуры данных. Как вы увидите, сложные структуры данных бывают весьма полезными, т. к. они упрощают сложные вычислительные задачи.

1.3 Создание дерева

Один из способов создания дерева – это вложенная структура из функторов и аргументов, как в предыдущем примере. Однако в общем случае Пролог создает дерево путем вычисления. На каждом шаге пустое поддерево заменяется непустым в процессе унификации (сопоставления по аргументам).

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

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

Здесь говорится: "Если N – данное, то tree(N, empty, empty) – это дерево из одного узла, содержащее его".

Построение структуры дерева так же просто. Следующей процедуре нужны три дерева в качестве аргументов. Она вставляет первое дерево в качестве левого поддерева во второе дерево, и результат этого присваивает третьему дереву:

insert_left(X, tree(А, _, В), tree(А, X, В)).

Заметьте, что в этом предложении нет тела, т. е. нет четких шагов при его выполнении. Все, что должен сделать компьютер, – это соединить аргументы друг с другом в правильном порядке, – и работа закончена.

Предположим, что вы хотите вставить tree("Michael", empty, empty) в качестве левого поддерева для tree("Cathy", empty, empty). Чтобы это сделать, надо выполнить целевое утверждение:

insert_left(tree("Michael", empty, empty),

tree("Cathy", empty, empty),

T)

Тогда Т примет значение:

tree("Cathy", tree("Michael", empty, empty), empty).

Это дает способ построения дерева шаг за шагом.

Сортировка на основе дерева

После того, как дерево построено, можно легко переставить все его элементы в алфавитном порядке. Алгоритм для этого – вновь вариант поиска "сначала – вглубь":

1. Если дерево пустое, то ничего не делать.

2. Иначе, переставить все элементы левого поддерева, потом текущий элемент, затем все элементы правого поддерева.

Или на Прологе:

retrieve_all(empty). % Ничего не делать

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

retrieve_all(Left),

do_something_to (Item),

retrieve_all(Right).

Сортировку следующих друг за другом значений можно выполнить, вставляя их в дерево, и затем переставляя их по порядку.