С П И С К И И Р Е К У Р С И Я

 

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

Определение

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

Эта структура либо пуста, либо состоит из двух частей – головы и хвоста.

Хвост в свою очередь является списком.

Голова – обычная переменная. Выделив из списка голову, можно ее обрабатывать как и любую другую переменную. Все элементы списка обладают общим свойством: в Прологе это свойство трактуется как отношение, определяющее связь между элементами списка или между списком в целом и элементом, внешним по отношению к списку. Все элементы списка заключаются в [] и отделяются друг от друга запятыми:

[ann, peter, jim, tom] , [2,5.7.8]

В Прологе список – это последовательность, состоящая из любого количества элементов. Известно, что все структурированные объекты Пролога – это деревья. Списки не являются исключением из этого правила:

[3,7,10]

/ \

3 [7,10]

/ \

7 [10]

/ \

10 []

Рис.6.1.Двоичное дерево списка

Замечание

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

 

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

Список помогает сделать программу компактной, эффектив-

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

Это базовые структуры функциональных языков. С помощью списков можно представить практически любые сложные структуры.

Порядок расположения элементов является отличительной чертой списка: те же элементы, упорядоченные иным способом, представляют собой уже совсем другой список. Порядок важен в процессе сопоставления. Объекты cписка называются элементами списка. Единственное ограничение на их число – объем оперативной памяти.

Все элементы списка принадлежат одному и тому же типу доменов. (Исключением являются списки структур. Структура может принадлежать альтернативному домену, и тогда элементы списка могут иметь разный тип).

Как представить список в виде стандартного объекта Пролога?