МЕТОД РАЗДЕЛЕНИЯ СПИСКА НА ГОЛОВУ И ХВОСТ

В программе 6.1 «Списки» для получения доступа к элементам списков были использованы внешние целевые утверждения. Задание цели в виде animals(All) обеспечивало присваивание переменной All всего списка в целом. Напротив, цель animals([_,_,B,_]) позволила извлечь из списка лишь один элемент. В этом случае, однако, требовалось точное знание числа элементов списка.

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

МЕТОДОМ РАЗДЕЛЕНИЯ СПИСКА НА ГОЛОВУ И ХВОСТ.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

[Head|Tail]

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка. (Для имен головы и хвоста списка пригодны любые допустимые Турбо-Прологом имена.)

Программа 6.2 демонстрирует использования метода разделения списка. Два списка описаны в ней: список целых чисел (имя домена — integer*) и список символических имен (домен animals_list). Правило print_list применяется для доступа к элементам обоих списков.

/* Программа 6.2 «Голова-хвост». Назначение: */

/* разделение списка на голову и хвост */

domains

animals_list = symbol *

predicates

print_list(integer *)

print_list(animal_list)

clauses

print_list([]).

print_list([Head|Tail]) :-

write(Head),nl,

print_list(Tail).

/* Конец программы */

Программа 6.2 использует правило print_list для доступа к элементам списков. Так как предикат print_list определен для объектов обоих доменов, то это правило используется для работы как со списком number_list, так и списком animal_list.

Когда правило пытается удовлетворить внешнюю цель

print_list([4,-9,5,3])

то первый вариант правила, print_list[], дает неуспех, так как его объект является пустым списком. Напротив, введенный список соответствует объекту второго варианта предиката print_list([Head|Tail]). Переменной Head, следовательно, присваивается значение первого элемента в списке, 4, в то время как переменной Tail ставится в соответствие оставшаяся часть списка,
[-9,5,3].

Теперь, когда выделен первый элемент списка, с ним можно обращаться так же, как и с любым простым объектом:

write(Head),nl

Так как хвост списка есть список сам по себе, значение переменной Tail может быть использовано в качестве объекта рекурсивного вызова:

print_list(Tail)

Процесс повторяется до тех пор, пока переменная Head не примет значение 3, а переменная Tail присвоится пустой список. Теперь при рекурсивном вызове print_list(Tail) значение Tail соответствует объекту правила

print_list([])

Этот вариант является граничным условием рекурсии, и цель считается удовлетворенной.

Рекурсивные правила для работы со списками просты, но вместе с тем и очень важны, ввиду их применимости в большинстве программ.