Списки в Prolog. Теория. Примеры

Заказать решение задачи на Prolog или попросить помощь

В функциональных и логических языках списки используются чрезвычайно часто, они позволяют сохранить набор данных произвольной длины. В статье на множестве примеров показана обработка списков в языке Prolog. Основная часть примеров написана на диалектах с динамической типизацией (SWI/GNU/Arity Prolog), но с небольшими изменениями будет отлично работать на строго-типизированных реализациях (Turbo/Visual Prolog).

Списки. Теория

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

Связный список — структура данных, состоящая из узлов. Узел содержит данные и ссылку (указатель, связку) на один или два соседних узла. Списки языка Prolog являются односвязными, т.е. каждый узел содержит лишь одну ссылку.

В языке Prolog программист не сталкивается с явной работой с указателями в узлах, однако ему нужно иметь общее представление о списках, т.к. являясь основной структурой данных в функциональных и логических языках, они обладают рядом существенных отличий от массивов, используемых в императивных языках (таких как С++, Java, Pascal). В частности, элемент данных может быть очень быстро добавлен или удален из начала односвязного списка. Однако операция произвольного доступа (обращения к n-ному элементу) в списках выполняется гораздо дольше чем в массивах, т.к. требует n операций перехода по ссылкам.

При работе с односвязными списками необходимо выделять первый узел (называемый головой списка), остальные узлы (составляющие хвост списка) можно получить передвигаясь по указателям вплоть до последнего узла. Хвост списка является таким же списком, как и исходный, поэтому обрабатывается аналогичным образом (рекурсивно).

prolog-list-processing

Процесс обработки списка в Prolog

Списки в Prolog. Синтаксис

При использовании статически-типизированного диалекта необходимо объявить тип списка (например в Turbo Prolog это делается в разделе domains):

domains
  ilist = integer*

В дальнейшем, при объявлении функций обработки списков (раздел predicates) необходимо использовать объявленный тип данных. Функция обработки списков вещественных чисел не будет обрабатывать список целых — это не очень удобно, однако позволяет выявлять несоответствие типов на этапе трансляции и генерировать более оптимальный код компилятору.

При использовании таких диалектов как SWI Prolog, предварительное объявление типов не требуется, кроме того, список может содержать данные разных типов.

list_syntax:-
% объявление списка из трех чисел с именем ListA:
   ListA = [7, 5, 3],
% разделение списка на первый элемент (переменная с именем Head)
% и остальную часть списка (Tail)
% в результате Head = 7, Tail = [5, 3]:
   ListA = [Head|Tail],
% формирование списка ListB из нового элемента, Head и tail:
% в результате ListB = [7, 9, 5, 3]
   ListB = [Head, 9|Tail],
% сравнение списка ListA с пустым списком
% (завершится неудачей, т.к. ListA не пуст)
   ListA = [].

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

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

sum_list(List, Sum) — вычисление суммы элементов списка

Сумма элементов пустого списка равна нулю. Если список не пуст — разделим его на первый элемент и хвост. Обработаем рекурсивно хвост, в результате получим сумму элементов части списка без учета первого элемента. Добавим первый элемент чтобы получить окончательный результат.

sum_list([], 0):-!.
sum_list([Head|Tail], Sum):-
   sum_list(Tail, TailSum),
   Sum is TailSum + Head.

nth0(Index, List, Elem) — функция получения элемента списка с заданным индексом. Индексация начинается с нуля. Если нужного элемента нет — функция завершается неудачей.

nth0(0, [Elem|_Tail], Elem):-!.
nth0(Index, _List, _Elem):-
   Index < 0, !, fail.
nth0(Index, [_Head|Tail], Elem):-
   NextIndex is Index - 1,
   nth0(NextIndex, Tail, Elem).

Функция завершает свою и успешно возвращает первый элемент списка если Index равен нулю и от списка удалось отделить первый элемент. Функция завершается неудачей если Idex оказался меньше нуля или остался больше нуля при пустом списке. Если же список не пуст (от него успешно отделяется первый элемент) и индекс больше ноля — рекурсивно обрабатывается хвост списка и уменьшенный на единицу Index (ведь список уменьшился на один элемент).

member(Elem, List) — выполняет поиск значения в списке. Завершается удачей если элемент найден.

Если значение первого элемента списка совпадает со значением искомого элемента — правило сразу завершается удачей. В противном случае первый элемент отбрасывается и поиск продолжается в хвосте. Как только разделение списка на голову и хвост станет невозможно — правило завершится неудачей.

member(Elem, [Elem|_Tail]).
member(Elem, [_Head|Tail]):-
   member(Elem, Tail).

Важно то, что предикат может вернуть несколько решений (предикат является недетерминированным — nondeterm), поэтому первое правило не содержит отсечения. Такое поведение особенно важно если функция member используется для перебора всех элементов списка (достаточно передать вместо Elem анонимную переменную).

min_list(List,MinElem) — вычисление наименьшего элемента списка

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

min_list([MinElem], MinElem):-!.
min_list([Head|Tail], MinElem):-
   min_list(Tail, TailMinElem),
   TailMinElem < Head, !, MinElem = TailMinElem;
   MinElem = Head.

Если на вход будет подан пустой список, то разделение на голову и хвост провалится и правило завершится неудачей.

reverse(List, ReverseList) — функция переворота списка

Чтобы перевернуть список используется метод накапливающего параметра, при этом создается вспомогательная функция, которая помимо двух списков принимает буфер. Изначально буфер пуст, но по мере обработки, в его начало добавляются элементы из исходного списка — поэтому первый добавленный элемент окажется последним, а последний — первым. Как только все элементы окажутся обработаны — накопленные в буфере значения будут переписаны в список-результат.

reverse(List, ReverseList):-
   reverse(List, [], ReverseList). % вызов вспомогательной функции с пустым буфером

reverse([], Buffer, Buffer):-!.
reverse([Head|Tail], Buffer, ReverseList):-
   reverse(Tail, [Head|Buffer], ReverseList).

Метод накапливающего параметра используется достаточно часто, т.к. при его использовании рекурсивный вызов оказывается последней операцией, выполняемой функцией. Компиляторы заменяют такой вызов циклом, что позволяет обрабатывать огромные списки и не бояться переполнения стека.

sublist(Sub, List) — завершается удачей если все элементы списка Sub встречаются в списке List в точно таком же порядке.

Напишем вспомогательную функцию sub_start для проверки случая, когда список List начинается со списка Sub. Очевидно, проверка вспомогательного правила даст условие выхода из рекурсии в случае успешного завершения работы. Если же проверка не увенчалась успехом — отделим от List первый элемент, а остальные попробуем обработать рекурсивно.

sub_start([], _List):-!.
sub_start([Head|TailSub], [Head|TailList]):-
   sub_start(TailSub, TailList).

sublist(Sub, List):-
   sub_start(Sub, List), !.
sublist(Sub, [_Head|Tail]):-
   sublist(Sub, Tail).

Функция sub_start завершается успехом если список Sub оказался пуст, т.к. пустой список по определению является часть любого списка.

delete(InputList, Elem, ResultList) — функция удаления всех элементов с заданным значением из списка

Если на вход подан пустой список, то результатом должен также являться пустой список. Если первый элемент списка совпал с удаляемым значением — функция должна вернуть результат рекурсивной обработки хвоста, а в противном случае — добавить к полученному результату первый элемент.

delete([], _Elem, []):-!.
delete([Elem|Tail], Elem, ResultTail):-
   delete(Tail, Elem, ResultTail), !.
delete([Head|Tail], Elem, [Head|ResultTail]):-
   delete(Tail, Elem, ResultTail).

append(List1, List2, List1AndList2)— функция объединения двух списков

Постепенно выбирая элементы первого списка сводим ситуацию к тому, что список станет пуст — в этом случае результатом работы функции должен являться второй список. На рекурсивном подъеме добавим к полученному результату элементы первого списка.

append([], List2, List2).
append([Head|Tail], List2, [Head|TailResult]):-
   append(Tail, List2, TailResult).

Функция может выполнять как объединение списков, так и их вычитание. Если задан третий аргумент, но не задан второй или первый — то она попробует подобрать недостающие значения так, чтобы получился требуемый результат. Кроме того, если не заданы оба первых аргумента — функция будете перебирать все варианты генерации третьего списка из двух.

append_examples_prolog

Примеры использования функции append

unique(List) — проверка того, что ни один элемент списка не повторяется дважды

В списке нет повторяющихся элементов, если первый элемент списка не встречается в хвосте, а также, в хвосте нет повторяющихся элементов. Условием выхода из рекурсии может быть пустота исходного списка — в нем гарантированно нет повторяющихся элементов.

unique([]):-!.
unique([Head|Tail]):-
   member(Head, Tail), !, fail;
   unique(Tail).

rangConcat(List1, List2, List1AndList2) — объединение двух отсортированных списков так, чтобы в результате получился отсортированный список.

Очевидно, что если один из списков пуст — результатом является другой список. На каждом шаге алгоритма оба входных списка разделяются на голову и хвост. Головы сравниваются и рекурсивно обрабатываются списки без наименьшей головы, на рекурсивном подъеме она добавляется к результату.

rangConcat([], List2, List2):-!.
rangConcat(List1, [], List1):-!.
rangConcat([Head1|Tail1], [Head2|Tail2], [Head1|TailResult]):-
   Head1 < Head2, !, rangConcat(Tail1, [Head2|Tail2], TailResult).
  
rangConcat(List1, [Head2|Tail2], [Head2|TailResult]):-
   rangConcat(List1, Tail2, TailResult).

length(List, Length) — вычисляет длину списка

Используем метод накапливающего параметра чтобы рекурсия функции была хвостовой, т.к. длина списков на языке Prolog вычисляется очень часто поэтому эффективность функции является критичной.

Функция length вызывает вспомогательную, при этом задает начальное значение длины равным нулю.

length(List, Length):-
   length(List, 0, Length).

length([], Length, Length):-!.
length([_Head|Tail], Buffer, Length):-
   NewBuffer is Buffer + 1,
   length(Tail, NewBuffer, Length).

Вспомогательная функция возвращает накопленное в буфере значение в качестве длины если на вход подан пустой список. В противном случае от исходного списка отделяется один элемент, вычисляется новое значение буфера. Хвост списка и буфер передаются для рекурсивной обработки.

Литература:

  1. Документация SWI-Prolog [Электронный ресурс] – режим доступа: http://www.swi-prolog.org/. Дата обращения: 06.01.2014.
  2. Visual Prolog официальный сайт [Электронный ресурс] – режим доступа: http://www.visual-prolog.com/. Дата обращения: 06.01.2014.
  3. А.отт, Обзор литературы о функциональном программировании [Электронный ресурс] – режим доступа: http://fprog.ru/2009/issue1/alex-ott-literature-overview/. Дата обращения: 06.01.2014.
  4. Сергиевский Г. М. Функциональное и логическое программирование : [учеб. пособие] / Г. М. Сергиевский, Н. Г. Волченков. – М. : Академия, 2010. – 317с

One thought on “Списки в Prolog. Теория. Примеры

Добавить комментарий