На этом шаге мы рассмотрим списки и рекурсию.
Что такое список?
В Прологе список - это объект, который содержит конечное число других объектов. Списки можно грубо сравнить с массивами в других языках, но, в отличие от массивов, для списков нет необходимости заранее объявлять их размер.
Конечно, есть другие способы объединить несколько объектов в один. Если число объектов заранее известно, то вы можете сделать их аргументами одной составной структуры данных. Если число объектов не определено, то можно использовать рекурсивную составную структуру данных, такую как дерево. Но работать со списками обычно легче, т.к. Пролог обеспечивает для них более четкую запись.
Список, содержащий числа 1, 2 и 3, записывается так:
[1,2,3]
Каждая составляющая списка называется элементом. Чтобы оформить списочную структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные скобки. Вот несколько примеров:
[dog,cat,canary] ["valerie ann","jennifer caitlin","benjamin thomas"]
Объявление списков
Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:
domains
integerlist=integer*
Символ (*) означает "список чего-либо"; таким образом, integer* означает "список целых".
Обратите внимание, что у слова "список" нет специального значения в Прологе. С тем же успехом можно назвать список "занзибаром". Именно обозначение * (а не название), говорит компилятору, что это список.
Элементы списка могут быть любыми, включая другие списки. Однако все его элементы должны принадлежать одному домену. Декларация домена для элементом должна быть следующего вида:
domains
elementlist = elements*
elements = ....
Здесь elements имеют единый тип (например: integer, real или symbol) или являются набором отличных друг от друга элементов, отмеченных разными функторами. В Прологе нельзя смешивать стандартные типы в списке. Например, следующая декларация неправильно определяет список, составленный из элементов, являющихся целыми и действительными числами или идентификаторами:
elementlist=elements*
elements=integer; real; symbol /* Неверно */
Чтобы объявить список, составленный из целых, действительных и идентификаторов, надо определить один тип, включающий все три типа с функторами, которые покажут, к какому типу относится тот или иной элемент. Например:
elementlist=elements*
% функторы здесь i,r и s
elements=i(integer); r(real); s(symbol)
Головы и хвосты
Список является рекурсивным составным объектом. Он состоит из двух частей - головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка - всегда список, голова списка - всегда элемент. Например:
голова [а,b,с] есть а хвост [а,b,с] есть [b,с]
Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:
голова[с] есть с хвост [с] есть [ ]
Если выбирать первый элемент списка достаточное количество раз, вы обязательно дойдете до пустого списка [ ].
Пустой список нельзя разделить на голову и хвост. Это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а,b,с,d] представлена на рис. 1.
Рис.1. Структура дерева
Одноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле - это составная структура данных, как показано на рис. 2.
Рис.2. Составная структура данных
На следующем шаге мы начнем рассматривать работу со списками.
