Упражнение

1. Попробуйте обе версии length_of для очень больших списков (напри-

мер 200 или 500 элементов). Что произойдет? Как соотносятся по ско-

рости обе версии на длинных списках?

2. Что произойдет при использовании новой версии length_of, если вы-

полнить следующее целевое утвердение?

length_of(MyList, 5, 0).

Подсказка: Здесь вы найдете очень важное свойство Пролога, названное

взаимозаменяемостью неизвестных. Но, не все предикаты Пролога обла-

дают этим свойством.

3. Перепишите sum_of также, как новая версия length_of.

Другой пример - изменения в списках

Иногда необходимо из одного списка выработать другой. Вы делаете

это, работая со списком, заменяя элемент за элементом вычисленным значе-

нием. Вот, например, программа, которая каждому числу списка добавит 1:

/* Программа CH08EX04.PRO - изменения списков */

trace

domains

list = integer*

predicates

add1(list, list)

clauses

add1([], []). /* граничное условие*/

add1([Head|Tail], [Head1|Tail1]):- /*отделить голову*/

/*от остального списка*/

Head1= Head+1, /*добавить к 1-му элементу*/

add1(Tail, Tail1)./*вызвать элемент из остатка списка*/

Переведя это на естественный язык получим:

Добавить 1 ко всем элементам пустого списка, создать другой пус-

той список.

Добавить 1 ко всем элементам любого другого списка, добавить 1 к

голове и сделать это головой результирующего списка, затем доба-

вить 1 к каждому элементу хвоста списка и сделать это хвостом ре-

зультата.

Введите программу (отметьте опцию trace компилятора). Затем введите

целевое утверждение add1([1, 2, 3, 4], NewList)., а затем выполните прог-

рамму, используя клавишу F10. Турбо Пролог выдаст результат:

NewList= [2, 3, 4, 5]

1 Solution

Снова о хвостовой рекурсии

Является ли add1 (добавление 1) хвостовой рекурсией? Если вы знакомы

с Лиспом или Паскалем, то можете подумать, что нет, т.к. считаете, что

предикат выполняет следующие операции:

1. Разделяет список на Head и Tail.

2. Добавляет 1 к Head и результат присваивает Head1.

3. Рекурсивно добавляет 1 ко всем элементам Tail, присваивает ре-

зультат Tail1.

4. Объединяет Head1 и Tail1 и присваивает результат новому списку.

Эта процедура не является хвостовой рекурсией, потому, что рекурсив-

ный вызов - это не последний шаг.

Но, и это важно - Пролог делает это не так. В Турбо Прологе, add1

является хвостовой рекурсией, потому, что шаги на самом деле следующие:

1. Присвоить голову и хвост списка к Head и Tail.

2. Присвоить голову и хвост результата к Head1 и Tail1. (Head1 и

Tail1 пока не определены).

3. Добавить 1 к Head и присвоить результат Head1.

4. Рекурсивно добавить 1 ко всем элементам Tail, присваивая резуль-

тат Tail1.

Когда все будет завершено, Head1 и Tail1 уже являются головой и

хвостом результата, и нет отдельной операции для их объединения. Таким

образом рекурсивный вызов является последним шагом.