В императивных языках, как правило, основной структурой данных являются массивы. В Прологе так же, как и в Лиспе, основным составным типом данных является список. В этой лекции мы займемся изучением именно списков.
Дадим сначала неформальное определение списка.
Будем называть списком упорядоченную последовательность элементов произвольной длины.
Список задается перечислением элементов списка через запятую в квадратных скобках, так, как показано в приведенных ниже примерах.
[monday, tuesday, wednesday, thursday, friday, saturday, sunday] — список, элементами которого являются английские названия дней недели;
["понедельник", "вторник", "среда", "четверг", "пятница", "суббота", "воскресенье"] — список, элементами которого являются русские названия дней недели;
[1, 2, 3, 4, 5, 6, 7] — список, элементами которого являются номера дней недели;
['п', 'в', 'с', 'ч', 'п', 'с', 'в'] — список, элементами которого являются первые символы русских названий дней недели;
[] — пустой список, т.е. список, не содержащий элементов (в языке функционального программирования Лисп он обозначается nil).
Элементы списка могут быть любыми, в том числе и составными объектами. В частности, элементы списка сами могут быть списками.
В разделе описания доменов списки описываются следующим образом:
DOMAINS
<имя спискового домена>=<имя домена элементов списка>*
Звездочка после имени домена указывает на то, что мы описываем список, состоящий из объектов соответствующего типа.
Например:
listI = integer* /* список, элементы которого —
целые числа */
listR = real* /* список, состоящий из вещественных
чисел */
listC = char* /* список символов */
lists = string* /* список, состоящий из строк */
listL = listI* /* список, элементами которого являются
списки целых чисел */
Последнему примеру будут соответствовать списки вида:
[[1,3,7],[],[5,2,94],[–5,13]]
В классическом Прологе элементы списка могут принадлежать разным доменам, например: [monday, 1, "понедельник"]
В Турбо Прологе, в связи со строгой типизацией, все элементы списка должны принадлежать одному домену. Однако можно разместить в одном списке объекты разной природы, используя домен с соответствующими альтернативами.
Например, следующее описание:
DOMAINS
element = i(integer); c(char); s(string)
listE = element*
позволит иметь дело со списками вида
[i(–15), s("Мама"),c('A'),s("мыла"),c('+'),s("раму"),
i(48),c('!')]
Дадим рекурсивное определение списка.
список — это структура данных, определяемая следующим образом:
- пустой список ([ ]) является списком;
- структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.
Принято называть H головой списка, а T — хвостом списка. Заметим, что выбор переменных для обозначения головы и хвоста не случаен. По-английски голова — Head, а хвост — Tail.
Фактически операция "|" позволяет разделить список на хвост и голову (в Лиспе есть подобные операции car и cdr) или, наоборот, приписать объект (объекты) к началу списка (cons в Лиспе).
Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост. Хвост, в свою очередь, также является списком, содержащим меньшее количество элементов, чем исходный список. Если хвост не пуст, его также можно разбить на голову и хвост. И так до тех пор, пока мы не доберемся до пустого списка, у которого нет головы.
Например, в списке [1, 2, 3] элемент 1 является головой, а список [2, 3] — хвостом, т.е. [1, 2, 3] = [1|[2, 3]].
Заметим, что хвост этого списка [2, 3], в свою очередь, может быть представлен в виде головы 2 и хвоста [3], а список [3] можно рассматривать в виде головы 3 и хвоста []. Пустой список далее не разделяется.
В итоге получаем, что список [1, 2, 3] эквивалентен списку [1|[2, 3]], который, в свою очередь, эквивалентен списку [1|[2|[3]]]. Последний сопоставим со списком [1|[2|[3|[ ]]]].
В этом же списке можно выделить два первых элемента и хвост из третьего элемента [1,2|[3]]. И, наконец, возможен вариант разбиения на голову из трех первых элементов и пустой хвост: [1, 2, 3|[]].
Чтобы организовать обработку списка, в соответствии с приведенным выше рекурсивным определением, нам достаточно задать предложение (правило или факт, определяющее, что нужно делать с пустым списком), которое будет базисом рекурсии, а также рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста. Иногда базис рекурсии записывается не для пустого, а для одно- или двухэлементного списка.
В качестве резюме к нашим рассуждениям запишем еще раз определение списка в нотации Бэкуса–Науэра:
Список ::= [ ]|[Элемент <,Элемент>*]|[Голова|Хвост]
Голова ::= Элемент <,Элемент>*
Хвост ::= Список
Словесно это можно записать так: список или пустой, или представим в виде перечисления элементов, записанных через запятую, или состоит из головы и хвоста, который, в свою очередь, также является списком.
