Использование списков

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

Совокупность элементов списка заключается в квадратные скобки ([]), элементы друг от друга отделяются запятыми. Список может содержать произвольное число элементов, единственным ограничением является объем оперативной памяти. Количество элементов в списке называется его длиной. Список может содержать один элемент и даже не содержать ни одного элемента. Список, не содержащий элементов, называется пустым или нулевым списком.

Непустой список можно рассматривать как список, состоящий из двух частей: головы – первого элемента списка; и хвоста – остальной части списка. Голова является элементом списка, хвост является списком. Голова списка – это неделимое значение, хвост представляет собой список, составленный из того, что осталось от исходного списка в результате «отделения головы». Этот новый список обычно можно делить и дальше. Если список состоит из одного элемента, то его можно разделить на голову, которой будет этот самый элемент, и хвост, являющийся пустым списком.

Пустой список нельзя разделить на голову и хвост!

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

[Head | Tail].

Голова списка всегда имеет тип элемента списка, хвост списка – тип списка!

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка (для имен головы и хвоста списка пригодны любые допустимые Прологом имена).

Данная операция также присоединяет элемент в начало списка, например, для того, чтобы присоединить X к списку S следует написать [X|S].

В концептуальном плане, список имеет структуру дерева, как и другие составные термы. Так, например, список [a,b,c] можно представить в виде структуры:

Отличительной особенностью описания списков является наличие звездочки (*) после имени домена элементов.

Пример 34: объявление списков, состоящих из элементов стандартных типов доменов или типа структуры.

domains

list1=integer*

list2=char*

list3=string*

list4=real*

list5=symbol*

personal_library = book (title, author, publisher, year)

list6= personal_library*

list7=list1*

list8=list5*

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

Пример 35: демонстрация разделения списков на голову и хвост.

Visual Prolog допускает объявление и использвание составных списков. Составной список – это список, в котром используется более чем один тип элемента. Для создания такого списка, необходимо использовать структуры, так как домен может содержать более одного типа данных только для структуры.

Пример 36: объявление списка, который может содержать символы, целые числа или строки:

domains

llist=i(integer);c(char);s(string)

list=llistl*

Для применения списков в программах на Прологе необходимо описать домен списка в разделе domains, предикаты, работающие со списками необходимо описать в разделе predicates, задать сам список можно либо в разделе clauses либо в разделе goal.

Над списками можно реализовать различные операции: поиск элемента в списке, разделение списка на два списка, присоединение одного списка к другому, удаление элементов из списка, сортировку списка, создание списка из содержимого БД и так далее.