Головы и хвосты

Список является рекурсивным составным объектом. Он состоит из двух частей — головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка — всегда список, голова списка — всегда элемент. Например:

голова [а, b, с] есть а

хвост [а, b, с] есть [b, с]

Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:

Голова[с] есть с

хвост [с] есть []

Если выбирать первый элемент списка достаточное количество раз, вы обязательно дойдете до пустого списка [ ]. Пустой список нельзя разделить на голову и хвост.

В концептуальном плане это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 14.1.

Рис. 14.1. Структура дерева

Одноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле — это составная структура данных, как показано на рис. 14.2.

Рис. 14.2. Составная структура данных

Работа со списками

В Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например:

[а, b, с] эквивалентно [а | [ b, с]] и, продолжая процесс,

[а | [b, с]] эквивалентно [а | [b | [с]]], что эквивалентно [а | [b | [с | []]]]

Можно использовать оба вида разделителей в одном и том же списке при условии, что вертикальная черта есть последний разделитель. При желании можно набрать [а, Ь, с, d] как [а, b | [с, d] ]. В табл. 14.1 вы найдете другие примеры.

Таблица 14.1. Головы и хвосты списков

Список	Голова	Хвост
['а', 'b', 'с']	'а'	['b', 'с']
[ 'а' ]	'а'	[] % пустой список
[ ]	Не определена	Не определен
[[1, 2, 3], [2, 3, 4], []]	[1, 2, 3]	[[2, 3, 4], []]

В табл. 14.2 приведены несколько примеров на присвоение в списках.

Список	Голова	Хвост
[X, Y, Z]	[эгберт, ест, мороженое]	Х= эгберт, Y=ест, Z=мороженое
[7]	[X | Y]	X=7, Y=[ ]
[1, 2, 3, 4]	[X, Y | Z]	X=l, Y=2, Z=[3,4]
[1, 2]	[3 1 X]	fail % неудача

Таблица 14.2. Присвоение в списках

Использование списков

Список является рекурсивной составной структурой данных, поэтому нужны алго­ритмы для его обработки. Главный способ обработки списка – это просмотр и об­работка каждого его элемента, пока не будет достигнут конец.

Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе – что делать с пустым списком.

Печать списков

Если нужно напечатать элементы списка, это делается так, как показано в листин­ге 14.1.

Листинг 14.1. Программа ch07e01.pro

domains

list = integer* % Или любой тип, какой вы хотите

predicates

write_a_list(list)

clauses

write_a_list([]). % Если список пустой - ничего не делать

write_a_list([Н|Т]):- % Присвоить Н-голова,Т-хвост, затем...

write(H),nl, write_a_list(Т).

goal

write_a_list([1, 2, 3]).

Вот два целевых утверждения write_a_list, описанные на обычном языке:

Печатать пустой список — значит, ничего не делать.

Иначе, печатать список — означает печатать его голову (которая является одним элементом), затем печатать его хвост (список).

При первом просмотре целевое утверждение таково:

write_a_list([l, 2, 3]) .

Оно удовлетворяет второму предложению при Н = 1 и Т = [2, 3]. Компьютер напе­чатает 1 и вызовет рекурсивно write_a_list:

write_a_list([2, 3]). % Это write_a_list(T)

Этот рекурсивный вызов удовлетворяет второму предложению. На этот раз Н = 2 и Т = [3], так что компьютер печатает 2 и снова рекурсивно вызывает write_a_list с целевым утверждением

write_a_list([3]).

Итак, какому предложению подходит это целевое утверждение? Вспомним, что, хотя список [3] имеет всего один элемент, у него есть голова 3 и хвост []. Следователь­но, целевое утверждение снова подходит под второе предложение с Н=3 и Т= [ ]. Про­грамма печатает 3 и делает рекурсивный вызов:

write_a_list([]) .

Теперь видно, что этому целевому утверждению подходит первое предложение. Вто­рое предложение не подходит, т. к. [] нельзя разделить на голову и хвост. Так что, если бы не было первого предложения, целевое утверждение было бы невыполни­мым. Но первое предложение подходит, и целевое утверждение выполняется без дальнейших действий.