Представление списков
Список — это простая структура данных, широко используемая в нечисловом программировании. Список представляет собой последовательность, состоящую из любого количества элементов, таких как 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]