Информатика -продвинутый курс
ОБРАБОТКА СПИСКОВ
На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять. Для решения таких задач в языке Пролог предусмотрены списки.
Список можно задать перечислением элементов. Например, имена учеников класса:
[саша,петя,дима,ксюша,лена].
Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться.
Альтернативный способ задания списка использует понятия головы и хвоста списка.
Например, в списке [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:
соединение двух списков.
Эту задачу можно описать с помощью следующих предикатов:
а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р;
