Язык Prolog. Представление списков.

Список – это последовательность, составленная из произвольного числа элементов, например, энн, теннис, том, лыжи. На Прологе это записывается так

[энн, теннис, том, лыжи ]

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

Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом []. Во втором случае список следует рассматривать как структуру, состоящую из двух частей:

1)                первый элемент, называемый головой списка;

2)                остальная часть списка, называемая хвостом.

Например, для списка

[энн, теннис, том, лыжи ]

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

[теннис, том, лыжи ]

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

.( Голова, Хвост)

Поскольку Хвост – это список, он либо пуст, либо имеет свои собственные голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:

.( энн, .( теннис, .(том, .( лыжи, [] ) ) ) )

На следующем рисунке изображена соответствующая древовидная структура.

Заметим, что показанный пример содержит пустой список []. Дело в том, что самый последний хвост является одноэлементным списком:

[ лыжи ]

Хвост этого списка пуст

[ лыжи ] = .( лыжи, [] )

Рассмотренный пример показывает. Как общий принцип структуризации объектов данных можно применить к спискам любой длины. Из нашего примера также видно, что такой примитивный способ представления в случае большой глубины вложенности подэлементов в хвостовой части списка может привести к довольно запутанным выражениям. Вот почему в Прологе предусматривается более лаконичный способ изображения списков, при котором они записываются как последовательности элементов, заключенные в квадратные скобки. Программист может использовать оба способа, но представление с квадратными скобками, конечно в большинстве случаев пользуется предпочтением. Мы, однако, всегда будем помнить, что это всего лишь косметическое улучшение и что во внутреннем представлении наши списки выглядят как деревья. При выводе же они автоматически преобразуются в более лаконичную форму представления. Так, например, возможен следующий диалог:

?- Список1 = [a, b, c],

Список2 = (а, .(b, .( c, []) ) )

Список1 = [a, b, c],

Список2 = [a, b, c]

?- Увлечения1 = .( теннис, .(музыка, [] ) ),

Увлечения2 =[ лыжи, еда ]

L = [энн, Увлечения2, том, Увлечения2].

Увлечения1 =[теннис, музыка]

Увлечения2 = [лыжи, еда]

L =[энн, [теннис, музыка], том, [лыжи, еда]]

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

На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть

L = [a, b, c]

Тогда можно написать:

Хвост =[ b, c] и L= .(a, Хвост)

Для того, чтобы выразить это при помощи квадратных скобок, в Прологе предусмотрено еще одно расширение нотации для представления СПиска, а именно вертикальная черта, отделяющая голову от хвоста.

L = [a | Хвост]

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

[a, b, c] = [a, | [b, c]] = [a, b, | [ c]] = [a, b, c | [ ]]

Подытожим:

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

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

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

или

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

или

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

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.