ОПЕРАЦИИ НАД СПИСКАМИ И АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ

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

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

Турбо-Пролог позволяет выполнять со списком целый ряд операций. Их перечень включает:

- доступ к объектам списка

- проверка на принадлежность к списку

- разделение списка на два

- слияние двух списков

- сортировку элементов списка в порядке возрастания или убывания.

Списки бывают полезны при создании баз знаний (баз данных), экспертных систем, словарей; перечень областей применения можно продолжать еще долго. В настоящей главе рассматриваются структура, организация и представление списков, демонстрируются некоторые из методов, применяемых при программировании на Турбо-Прологе.

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

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

Для удобства обработки списков в Прологе введены два понятия: голова и хвост. Первый элемент списка (или несколько первых элементов) являются головой списка, а оставшиеся - его хвостом

Элементы списка разделяются запятыми и заключаются в квадратные скобки. Любой список представляет собой:

- либо пустой список (атом []);

- либо непустой список - структуру, состоящую из двух частей:

- первый элемент - голова (Head) списка;

- второй элемент - хвост (Tail) списка.

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

Для обозначения списка используются квадратные скобки, а для отделения головы списка от его хвоста - символ "|". Например, для списка [1|2,3] элемент 1 является головой, а список [2,3] хвостом. Пустой список обозначается []. Если список не разделяется на голову и хвост, квадратные скобки можно опустить.

Очевидно, что список является в некотором смысле аналогом массива в алгоритмических языках программирования (Бейсик, Паскаль, Cи). Однако здесь есть существенные отличия. Основным механизмом работы со списками является рекурсия, позволяющая компактно описывать алгоритмы. Для рекурсии не требуется знания точного числа элементов списка, достаточно определения, как правило, головного элемента списка и условия окончания работы рекурсии. Поэтому элементы списков не индексируются, соответственно, количество элементов списка не фиксируется.

Можно также провести аналогию списков Пролога и динамических однонаправленных списковых структур Турбо-Паскаля. От последних их выгодно отличает отсутствие необходимости работать с адресной частью списков.

Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде

[ Элемент1, Элемент2,...]

или

[ Голова | Хвост ]

или

[ Элемент1, Элемент2,... | Остальные].

Здесь знак | используется для отделения начала списка от конца.

Примерами списков могут служить:

[1,2,3,6,9,3,4]

[3.2,4.6,1.1,2.64,100.2]

["YESTERDAY","TODAY","TOMORROW"]

Элементами первого списка являются целые числа. Элементами второго - действительные числа, третьего - символьные строки, т. е. конкретные значения символов. Любой печатный символ кода ASCII пригоден для списков этого типа.

Атрибуты списка.

Объекты списка называются элементами списка. Список может содержать произвольное число элементов, единственным ограничением является лишь объем оперативной памяти.

Турбо-Пролог требует, чтобы все элементы списка принадлежали к одному и тому же типу доменов. Другими словами, либо все элементы списка - целые числа, либо все - действительные, либо все - символы, либо - символьные строки. В Турбо-Прологе список

["JOHN WALKER",3.50,45.50]

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

Количество элементов в списке называется его длиной.

Длина списка ["MADONNA","AND","CHILD"] равна 3.

Длина списка [4.50,3.50,6.25,2.9,100.15] равна 5.

Список может содержать всего один элемент и даже не содержать элементов вовсе:

["summer"]

[]

Список, не содержащий элементов, называется пустым или нулевым списком. Непустой список можно рассматривать как состоящий из двух частей: (1) первый элемент списка - его голова, и (2) остальная часть списка - хвост. Голова является элементом списка, хвост есть список сам по себе. Голова - это отдельное неделимое значение. Наоборот, хвост представляет из себя список, составленный из того, что осталось от исходного списка в результате "усекновения головы". Этот новый список зачастую можно делить и дальше. Если список состоит из одного элемента, то его можно разделить на голову, которой будет этот самый единственный элемент, и хвост, являющийся пустым списком.

В списке

[4.50,3.50,6.25,2.9,100.15]

например, головой является значение 4.50, а хвостом - список

[3.50,6.25,2.9,100.15]

Этот список в свою очередь имеет и голову, и хвост.

Голова - это значение 3.50, хвост - список

[6.25,2.9,100.15]

В таблице. 3.1 показаны головы и хвосты нескольких списков.

Таблица 3.1. Головы и хвосты различных списков

____________________________________________________________