<<
>>

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

На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять.
Для решения таких задач в языке Пролог предусмотрены списки. Список можно задать перечислением элементов. Например, имена учеников класса: [саша,петя,дима,ксюша,лена]. Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться. Альтернативный способ задания списка использует понятия головы и хвоста списка. Например, в списке [X | Y] Х - это голова списка. Y - его хвост. Хвост списка по определению также является списком. Теперь список может быть определен рекурсивно: 1) пустой список [] - список: 2) [X | Y] - список, если Y - список. Определение списка через его голову и хвост в сочетании с рекурсией лежит в основе большого числа программ, оперирующих списками. Эти программы состоят 1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка; 2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста ( в голове правила), через операцию над хвостом (в подцели).
Пример I: определение числа элементов в списке. Программа 122 сколько ([], 0). сколько ([А|В], N) :- сколько (В, М), N is M+1. ?- сколько ([саша, игорь, лена]), X). Ответ: Х=3. Пример 2: принадлежность элемента списку. Программа 123 принадлежит (X, [X | Y]). принадлежит (X, [A |Y ]) : - принадлежит (X,Y). ?-принадлежит (4,(1,3,4,9]). Ответ:да. Данная программа имеет очень простой декларативный смысл: элемент принадлежит списку, если он является его головой или принадлежит хвосту списка. Пример 3: соединение двух списков. Эту задачу можно описать с помощью следующих предикатов: а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р; б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове Х (при этом получается список [Х|Т]).
Программа 124 присоединить([ ], Р, Р). присоединить([XIY], Р, [X | Т]):-присоединить(Y, Р, Т). ? присоединить(L,[джим.R],(джек,бил,джим,тим,джим,боб]). Ответ: L=[джек,бил]. К=[тим джим,боб]. L=[джек,бил,джим,тим]. R=[бoб]. Существует традиция использовать для обозначения предиката слияния двух списков предикативный символ append (по-английски -добавить). В некоторых случаях постановки вопросов к такого рода программам приходится использовать отсечение (!). Программа 125 append([ ], L, L). append([A I B] , C, [A | D]):- append(B, C, D). ?-append(X,Y,[1,2]). Ответ: X=[] Y=[l,2] X=[l] Y=[2] X=[l,2] Y=[]. Если же заменить первое предложение на append([ ], 1,1):- !. и задать тот же вопрос, то получится правильный ответ: Х=[] Y=[l,2]. Пример 4. удаление элементов из списка. Программа 126 аналогична проверке принадлежности элемента списку, но требует уже трехарного предиката, один аргумент которого указывает удаляемый элемент, второй аргумент-исходный список и третий - список-результат. Программа 126 удал (X. [X I Y], Y) : - !. удал (X. [Z I Y], [Z I W]) : - удал (X, Y, W) . Декларативный смысл: если удаляемый элемент совпадает с головой списка, то результатом программы является хвост списка, иначе удаления производятся из хвоста списка. Данная программа удаляет первое вхождение в список элемента, связанного с переменной X. Знак отсечения "!"в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта. Для удаления всех вхождений элемента Х программу надо дополнить: удал (Х,[ ],[]). удал (X, [X | Y], W) :- удал (X, Y, W). удал (X, [Z I Y], W):- удал (X, Y, W). Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, значит, отбросить голову списка, а затем удалять его из оставшегося хвоста, иначе надо сразу удалять элемент из хвоста. Пример 5: индексация элементов списка. Смысл программы 127 состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.
Программа 127 получить ([X | Y], 1, X). получить ([W | Y], N, X) :- N is M+l, получить (Y, M, X). Пример 6: поиск максимального элемента. Программа 128 max ([X], X). max ([X | Y], X) :- шах (Y, W), X>W, !. max ([X | Y], W) :-max (Y, W). Декларативный смысл программы: если в списке один элемент - он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста. Пример 7: обращение списка. Данная задача - самая сложная из рассмотренных. Для ее решения важно сообразить, что обратить список из одного элемента - означает оставить список без изменения. Обратить более длинный список - обратить его хвост, а потом сзади приставить к нему голову исходного списка. Программа 129 обр ([X], [X]) . обр ([X I Y], Z) :- обр (Y, W), присоединить (W, [X], Z). В этой программе используется процедура слияния списков, описанная выше. Arity-Prolog располагает значительным числом встроенных предикатов для обработки списков, так что приведенные программы имеют, в основном, учебный характер.
<< | >>
Источник: А.В. Могилев Н.И. Пак Е.К. Хеннер. Информатика. 2003

Еще по теме 7.5. ОБРАБОТКА СПИСКОВ:

  1. Номер один в списке неправильных действий
  2. ИНФОРМАЦИЯ: ОБРАБОТКА ПОСЛЕДОВАТЕЛЬНАЯ (
  3. ИНФОРМАЦИЯ: ОБРАБОТКА ПАРАЛЛЕЛЬНАЯ
  4. Статистическая обработка.
  5. ТЕОРИЯ УРОВНЕЙ ОБРАБОТКИ
  6. Обработка материалов
  7. Обработка результатов
  8. ГЛАВА ДЕВЯТАЯ ОБРАБОТКА ИНФОРМАЦИИ В УМЕ
  9. Алгоритм обработки результатов.
  10. ДАННОЕ: ОБРАБОТКА СТАТИСТИЧЕСКАЯ
  11. Обработка материала