Тема 22 Списки и структуры в Прологе.

Операции над списками. Использование структур.

Списки в Прологе

В императивных языках, как правило, основной структурой данных являются массивы. В Прологе так же, как и в Лиспе, основным составным типом данных является список.

Дадим сначала неформальное определение списка. Будем называть списком упорядоченную последовательность элементов произвольной длины.

Список задается перечислением элементов списка через запятую в квадратных скобках, так, как показано в приведенных ниже примерах. Список в Лиспе (a b c d) (1 2 (3)) записывается на Прологе [a,b,c,d] [1,2,[3]]

Элементами списка могут быть любые термы. Пустой список - обозначается не nil , а «пустыми» квадратными скобками -[].

Примеры.

[1, 2, 3, 4, 5, 6, 7] — список, элементами которого являются номера дней недели;

['п', 'в', 'с', 'ч', 'п', 'с', 'в'] — список, элементами которого являются первые символы русских названий дней недели;

Дадим рекурсивное определение списка.

Список — это структура данных, определяемая следующим образом:

1. пустой список ([ ]) является списком;

2. структура вида [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 | [ ]]]].

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

В качестве резюме к нашим рассуждениям запишем еще раз определение списка в нотации Бэкуса-Науэра:

Список ::= [ ]|[Элемент <,Элемент>*]|[Голова|Хвост]

Голова ::= Элемент <,Элемент>*

Хвост ::= Список

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