8.8.2. Рекурсивная обработка списков

Основной принцип работы со списками можно сформулировать так: "если не можешь решить задачу для всего списка, попробуй решить ее для хвоста". Процедурно это означает, что на каждом шаге задача будет решаться для списка, длина которого на 1 меньше, чем у предыдущего. Естественно, для завершения прямого хода рекурсии нужно задать граничное условие. Поэтому рекурсивная программа обработки списка обязательно содержит следующие два раздела:

1. факт, являющийся граничным условием, завершающим прямой ход;

2. рекурсивное правило, которое сводит операцию над списком к операциям над хвостом.

Приведем несколько операций со списками.

Примеры

8.13. Определить число элементов в списке.

сколько ([ ], 0).

сколько ([A | B], N) if сколько (B,M), N,M+1.

? – сколько ([саша, игорь, лена], Х).

Ответ: Х=3.

8.14. Определение принадлежности элементов списку

принадлежит (X,[X ¦ _]).

принадлежит (X, [A¦Y]) if принадлежит (X,Y).

? – принадлежит (4, [1,3,4,9]).

Ответ: да.

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

8.15. Соединение двух списков.

Эту задачу можно описать с помощью следующих предикатов:

1. ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список P, то в результате получиться P;

2. рекурсия состоит в том, что можно список P добавить к концу списка [X¦Y], если P будет добавлен к хвосту Y и затем присоединен к голове X (при этом получается список [X¦T]).

присоединить ([ ], P, P).

присоединить ([X¦Y], P, [X¦T] ) if присоединить (Y, P, T).

Например, если задан вопрос к этой базе знаний:

? – присоединить (L, [джим ¦ R], [джек, бил, джим, тим, джим, боб]).

То будут получены ответы:

L = [джек, бил].

R = [тим, джим, боб].

L = [джек, бил, джим, тим].

R = [боб].

Существует также традиция использовать для обозначения предиката слияния двух списков предикативный символ "append" (англ. "добавить").

В некоторых случаях постановки вопросов к такого рода программам приходиться использовать отсечение (!), например, ответ к программе:

Append ([ ], L, L).

Append ([A¦B], C, [A¦D])if append (B, C, D).

? – append (X, Y, [1, 2]).

Получается таким:

X = [ ]

Y = [1,2]

X = [1]

Y = [2]

X = [1, 2]

Y = [ ].

Если же заменить первое предложение на append ([ ], l, l) if !. и задать тот же вопрос, то получиться правильный ответ:

X = [ ]

Y = [1, 2].

8.16. Удаление элемента списка.

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

удал (X, [X¦Y], Y) : – !.

удал (X, [Z¦Y], [Z│W]) : – удал (X, Y, W).

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

Программа удаляет первое вхождение в список элемента, связанного с переменной X. Знак отсечения "!" в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.

Для удаления всех вхождений элемента X программу надо дополнить:

удал (X, [ ], [ ]) if !.

удал (X, [X¦Y], W) : – удал (X, Y, W).

удал (X, [Z¦Y], [Z¦W]) : – удал (X, Y, W).

Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, а затем удалить его из оставшегося хвоста, иначе надо сразу удалить элемент из хвоста.

8.17. Индексация элементов списка.

Смысл программы состоит в том, чтобы получить элемент под номером N или узнать номер элемента X:

получить ([X¦_], 1, X).

получить ([W¦Y], N, X)if N is M+1, получить (Y, M, X).

По смыслу программа аналогична подсчету элементов списка.

8.18. Поиск максимального элемента.

max ([X], X).

max ([X¦Y], X) : – max (Y, W), X >W, !.

max ([X¦Y], W) : – max (Y, W).

Декларативный смысл программы: если в списке один элемент, он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста.

8.19. Обращение списка.

Эта задача самая сложная из рассмотренных. Для ее решения важно сообразить, что обратить список из одного элемента – значит оставить список без изменения. Обратить более длинный список значит обратить его хвост, а потом в конец добавить к нему голову исходного списка:

обр ([X], [X]).

обр ([X¦Y], Z) : – обр (Y, W), присоединить (W, [X], Z).

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

8.20. Задать два списка слов, соединить их и удалить все вхождения головы второго списка.

Domains

X, Y, Z = symbol*.

A,B=symbol.

Predicates

Dan1 (X).

Dan2 (X).

Soed (X,X,X).

Udal (A,X,X).

Clauses

Dan1 ([1,2,3,4]).

Dan2 ([4,3,4,2]).

Soed ( [ ], X, X ) if !.

Soed ( [X¦Y] ,Z, [ X¦T ] ) if soed ( Y, Z, T).

Udal (A, [ ], [ ] ) if ! .

Udal ( A, [A¦Y], Z) if udal ( A, Y, Z)

Udal (A, [ B¦Y], [B¦Z] ) if udal (A, Y, Z) .

Rezult (X, Y, Z) if dan1 (X), dan2 ( [A¦Y]), soed (X, [A¦Y], T), udal ( A, T, Z).

Процедура доказательства предиката Rezult содержит следующие действия:

1. Унификация предикатов dan1 и dan2 с фактами базы данных, при этом переменная X конкретизируется значением [1, 2, 3, 4], переменная А – значением 4, переменная Y – значением [3, 4, 2].

1. Выполняется соединение списков [1,2,3,4] и [4,3,4,2], при этом переменная T получает значение [1, 2, 3, 4, 4, 3, 4, 2].

2. Удаляется число 4, которое является головой второго списка, из списка T. При этом получается список Z=[1,2,3,3,2].

Упражнения

111. Объединить два списка, найти max и удалить его.

112. Обратить список, удалить последний элемент.

113. Удалить из списка заданный элемент, найти длину оставшегося списка.

114. Два списка обратить, объединить, найти min.

115. Добавить к списку заданный элемент, найти длину хвоста списка.

116. Один из двух списков обратить, объединить со вторым, найти max.

117. Обратить список, найти последний и предпоследний элементы результата.

118. Объединить два списка. В хвосте найти min, max.

119. Исключить из списка число 5, найти длину оставшегося списка.

120. Объединить два списка, вставить перед первым элементом число 6, найти min.

121. Определить, принадлежат ли числа 2, 3 списку. Если принадлежат, то совпадают ли с max?

122. Из первого списка исключить первый, из второго – последний элементы. Списки объединить, найти длину результата.

123. Входит ли в список товаров «стол»? Если да, то исключить его.

124. Добавить к списку товаров «обувь». Объединить список товаров со списком цен. Выяснить, есть ли товар «шляпы».

125. Найти последний элемент списка, удалить его и найти длину результата.

126. Объединить два списка, найти последний элемент, проверить, является ли он минимальным в списке.

127. Обратить список, найти max и удалить его.

128. К первому списку добавить элемент в начало, ко второму – в конец и объединить списки.

129. Объединить два списка, найти min и удалить его.

130. Найти max хвоста, длину хвоста и обратить хвост. Присоединить его к голове исходного списка.

131. К первому списку добавить инвертированный второй список. Найти длину результата

132. Найти max и min элементы. Min исключить, а max заменить нулем.

133. Обратить список, добавить один элемент в начало, другой – в конец списка.

134. Найти max результата.

135. Объединить два списка, найти последний и предпоследний элементы. Удалить все вхождения последнего. Найти длину результата.

136. Даны два списка. Из второго удалить все вхождения головы первого списка.

137. В списке товаров найти номер «дивана». Если он первый, то удалить, иначе заменить на «кресло».

138. Даны два списка. Обратить их хвосты, и объединить их.

139. В списке слов определить слово, следующее за «прием» и удалить все вхождения этого слова.

140. Инвертировать первый список. Во втором удалить последний элемент. Результаты соединить.

141. В списке найти min. Если это голова, то удалить все вхождения. Если нет, то заменить min на 999.