Глава 8. Списки и рекурсия

Обработка списков, т.е. объектов, которые содержат конечное число

элементов - мощное средство в Прологе. В этой главе объясняется, что та-

кое списки и как их объявлять. Затем приводится несколько примеров, в ко-

торых показано, как можно использовать обработку списков в задачах. Также

определяются два известных предиката Пролога - member (член) и append

(объединение), при рассмотрении процедурных и рекурсивных аспектов обра-

ботки списков. После этого определяется стандартный предикaт Турбо Проло-

га - findal, который дает возможность находить и собирать все решения для

одного внутреннего целевого утверждения. Завершается эта глава рассмотре-

нием составных списков, т.е. комбинаций элементов различных типов, и при-

мером грамматического разбора списков.

Что такое списки?

В Прологе список - это объект, который содержит конечное число дру-

гих объектов. Список можно грубо сравнивать с массивами в других языках,

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

их размер. Конечно, есть другие способы объединить несколько объектов в

один. Если число объектов заранее известно, то вы можете сделать их аргу-

ментами одной составной структуры данных. И даже если число объектов не

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

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

печивает для них более четкую запись.

Список содержащий числа 1, 2 и 3 записывается так:

[1,2,3]

Каждая составляющая списка называется элементом. Чтобы оформить спи-

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

чить их в квадратные скобки. Вот несколько примеров:

[dog, cat, canary]

["valerie ann", "jennifer caitlin", "benjamin thomas"]

Объявление списков

Чтобы объявить тип для списка целых надо использовать domains - дек-

ларацию, такую как:

domains

integerlist = integer*

Обозначение "*" означает "список чего-либо"; таким образом, integer*

означает "список целых". ВАЖНОЕ ЗАМЕЧАНИЕ: у слова "список" нет специаль-

ного значения в Турбо Прологе. Вы могли бы с тем же успехом назвать спи-

сок ЗАНЗИБАРОМ. Именно обозначение "*", а не название, говорит компилято-

ру, что вы имеете ввиду список.

Элементы списка могут быть любыми, включая другие списки. Однако все

элементы списка должны принадлежать одному типу. И domains - декларация

для элементов должна быть следующего вида:

domains

elementlist = elements*

elements = ....

где elements имеют единый тип (например: integer, real или symbol)

или является набором отличных друг от друга элементов, отмеченных разными

функторами. В Турбо Прологе нельзя смешивать стандартные типы в списке.

Например: следующая декларация неправильно определяет список, составлен-

ный из целых, действительных и символьных элементов:

elementslist = elements*

elements = integer; real; symbol

/*неверная запись в Прологе*/

Чтобы объявить список, составленный из целых, действительных и сим-

вольных элементов, надо определить один тип, включающий все три типа с

функторами, которые покажут, к какому типу относится тот или иной эле-

мент. Например:

elementslist = elements*

elements = i(integer); r(real); s(symbol)

/*функторы здесь i,r и s*/

(Более подробно об этом смотрите ниже, в этой главе, в разделе

"Составные списки")