Лабораторная работа № 2

ОБРАБОТКА СПИСКОВ

2.1. Что такое список ?

Существуют различные способы объединения нескольких объектов в один. Если число объединяемых объектов известно за-

ранее, их можно сделать аргументами одной составной структуры

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

Каждый входящий в список обьект именуется элементом списка. Для формирования списочной структуры элементы нужно разделить запятыми и заключить в квадратные скобки. Так, например, список, содержащий элементы 1, 2 и 3, записывается как

[ 1, 2, 3 ]

Чтобы объявить домен, например, для списка целых значений, используется объявление domains, подобное следующему:

domains

список_целых = integer*

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

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

domains

список_элементов = элементы*

элементы = ...

где "элементы" приравниваются к одному типу данных (напри­мер, integer, real или symbol) или набору альтернативных типов, помеченных различными функторами. Visual-Пролог не допускает смешивания в списке стандартных типов. Например, следующие объ­явления не будут правильно отражать список, составленный из элементов типа integer, real, symbol:

список_элементов = элементы*

элементы = integer;real;symbol /* неверно ! */

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

список_элементов=элементы*

элементы=ц(integer);в(real);с(symbol)

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

голова[a,b,c] - это a

хвост[a,b,c] - это [b,c]

В случае одноэлементного списка:

голова[а] - это а

хвост[а] - это []

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

Пустой список на голову и хвост разбить невозможно. Это означает, что концептуально списки имеют древовидную струк-

туру, как и другие составные объекты.

Древовидная структура - список [а,в,с] - может быть пред­ставлена так:

список

/ \

a список

/ \

в список

/ \

с список

\

[]

Более того, одноэлементный список [a] - это не то же са­мое, что содержащийся в нем элемент, поскольку в действитель­ности он соответствует структуре:

список

/ \

a []

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

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

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

Можно даже в одном списке использовать оба вида разделите­лей, но при этом вертикальная черта должна быть последним раз­делителем в списке. Например, можно записать [a,b,c,d,e] как

[a,b,c|[d,e]]. В таблице 4.1 приведены еще примеры.

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

список	голова	хвост
[a,b,c] [a] [] [[1,2,3],[2,3,4],[]]	a a не определена [1,2,3]	[b,c] [] не определен [[2,3,4],[]]

А в таблице 2.2 приводятся несколько примеров установле­ния соответствия между списками.

Таблица 2.2

	Список1	Список2	Связывание переменных
	[X,Y,Z] [7] [1,2,3,4] [1,2]	[анна,ест,торт] [X|Y] [X,Y|Z] [3|X]	X=анна Y=ест Z=торт X=7 Y=[] X=1 Y=2 Z=[3,4] неудачный исход

Ввиду того, что списки являются рекурсивными составными структурами данных, для их обработки нужны рекурсивные алгорит­мы. Наиболее общим способом обработки списка является похожде­ние по списку до конца с выполнением над каждым элементом ка­ких-либо действий.

Для такого алгоритма необходимы два выражения. Одно, гово­рящее о том, что делать с обычным списком (тем, который может быть разбит на голову и хвост), и второе, указывающее действие для пустого списка.

Например, если нам нужно вывести элементы списка, то вы­полняется следующее:

/* Вывод элементов списка */

domains

список = integer* /* или любой нужный тип */

predicates

вывести_список(список)

clauses

вывести_список([]). /* Если список пуст, не делать ничего*/

вывести_список([Г|Х]) :- /* Привести в соответствие голову

с Г и хвост с Х , затем ... */

write(Г), nl,

вывести_список(Х).

goal

вывести_список([1, 2, 3]).

Здесь два выражения "вывести_список", говоря естественным языком, означают :

Для вывода пустого списка не делать ничего.

Иначе, для вывода списка вывести его голову, а затем вывести хвост.

При первом прохождении цель - вывести_список([1,2,3]).

Она приводится в соответствие со вторым выражением с Г=1 и Х=[2,3]. Компьютер выводит 1, а затем вызывает рекурсивно "вы­вести_список":

вывести_список([2,3]).

И так далее. Когда список становится пустым, рекурсивно вызыва­ется вывести_список([]).

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