Представление списков

Список — это простая структура данных, широко используемая в нечисловом программировании. Список представляет собой последовательность, состоящую из любого количества элементов, таких как arm, tennis, torn, skiing. Подобный спи­сок может быть записан в языке Prolog следующим образом: [ arm, tennis, torn, skiing]

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

При изучении возможных способов представления списка в виде стандартного

объекта Prolog необходимо учитывать два случая: список может быть либо пустым,

либо непустым. В первом случае список записывается просто в виде атома Prolog,

[ ]. Во втором случае список можно рассматривать как состоящий из следующих

компонентов.

1. Первый компонент, называемый головой списка.

2. Остальная часть списка, называемая хвостом. В приведенном выше примере списка

[ ann, tennis, torn, skiingj

головой является ann, а хвостом — следующий список:


[ tennis, torn, skiing]

Как правило, в качестве головы может быть выбран любой объект Prolog (например, дерево или переменная), а хвост должен представлять собой список. За­тем голова и хвост объединяются в некоторую структуру с помощью специального функтора списка: . ( Head, Tall)

Поскольку Tail, в свою очередь, является списком, он может либо быть пустым, либо иметь собственную голову и хвост. Поэтому для представления списков любой длины в программе Prolog не требуются какие-либо дополнительные понятия, кроме понятий функтора, атома и терма. В таком случае приведенный выше пример списка представляется в виде следующего терма:

. { arm, , ( tennis, . ( torn, . ( skiing, [])!!>

Соответствующая древовидная структура показана на рис. 3.1. Следует отметить, что в приведенном выше терме присутствует пустой список. Это связано с тем, что предпоследний хвост представляет собой одноэлементный список: I skiing]

/ \

Щи

/\

>>■............... ■■

Torn

/\

skiing [ ]

Рис. 3.1. Древовидное представление спи­ска [ ann, tennis, torn, skiinq)

Этот список в качестве хвоста имеет пустой список:

[skiing] = .(skiing, [])

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

?- Listl = [a, b,c] ,

ListZ = . | a, . ( b, . ( c, []))).

Listl = [a,b,c)

List2 = [a,b,c]

?- Hobbiesl = .(tennisr .( music, [])),


Глава З. Списки, операции, арифметические выражения



L = [ann, [hbiengl, torn, Hobbies2].

Hobbiesl= Гtennis, music]

Hobbies2 - skiing food]

L [ ann, [ tennis, music], torn, [ skiing, food] j

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

На практике часто возникает необходимость рассматривать весь хвост списка как единый объект. Например, предположим, что определен такой список: L - [а, Ь,с]

Поэтому можно записать следующее: Tail • [b,c] и L - .{ a, Tail)

Чтобы можно было представить это выражение на основе системы обозначений для списков с применением квадратных скобок, в языке Prolog предусмотрено еще одно дополнение к списковой записи: вертикальная черта, которая разделяет голову и хвост, как показано в следующем примере: Ь = [a I Tail]

Обозначение с помощью вертикальной черты фактически является более общим, поскольку в список можно ввести любое количество элементов, за ними указать символ " |" и после этого привести список оставшихся элементов. Поэтому все следующие аль­тернативные способы записи приведенного выше списка являются допустимыми: [а,Ь,с]- [а I lb,с]] - ia,bI [с] ]- [а,Ь,с! []]

Ив этого следуют приведенные ниже выводы.

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

• Списки обрабатываются в языке Prolog как частный случай бинарных деревь­ев. Для повышения удобства чтения в языке Prolog для списков предусмотре­на специальная система обозначений, поэтому являются допустимыми списки, оформленные следующим образом:

[ Iteml, ItemS, ...]

или

[ Head ] Tail] ИЛИ

; Iteml, Item2, ... Others]