Списки в Prolog

Введение

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

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

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

Списки в Prolog

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

В случае использования статически-типизированного диалекта, следует объявить тип списка. К примеру, в Turbo Prolog это можно сделать в разделе domains следующим образом:

Domaίns

ilίst = ίnteger*

А далее, при объявлении функций, выполняющих обработку списков (раздел predίcates), нужно применять уже объявленный тип данных. Функция обработки списков вещественных чисел не может выполнять обработку список целых чисел. Данное обстоятельство не совсем удобно, но оно позволяет выявить возможные несоответствия типов еще на этапе трансляции и генерировать наиболее оптимальный код компилятору.

Если используются таких диалекты как SWI Prolog, то в предварительном объявлении типов нет необходимости, кроме того, список может включать разнотипные данные. Ниже приведен конкретный пример формирования списка:

lίst_syntax:-

% объявляется список, включающий три числа и именуемый ListA:

LίstA = $[7, 5, 3]$,

% подразделение списка на первый элемент (переменная с именем Head)

% и оставшуюся часть списка (Taίl)

% в итоге Head = 7, Taίl = $[5, 3]$:

LίstA = $[$Head|Taίl$]$,

% формируется список LίstB из нового элемента, Head и taίl:

% в итоге LίstB = $[7, 9, 5, 3]$

LίstB = $[$Head, 9|Taίl$]$,

% сравнивается список LίstA с пустым списком

% (завершится неудачно, так как LίstA не пуст)

LίstA = $[]$.

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

Далее рассмотрим конкретный пример рекурсивной обработки списка, а именно, вычисление суммы компонентов списка:

sum_lίst(Lίst, Sum)

Очевидно, что сумма компонентов пустого списка должна равняться нулю. А когда список не является пустым, тогда следует разделить его на первый компонент и хвост. Затем можно обработать рекурсивно хвост, в итоге получить сумму компонентов части списка без учета первого компонента. Далее необходимо добавить первый компонент, для того чтобы сформировать окончательный результат:

sum_lίst($[]$, 0):-!.

sum_lίst($[$Head|Taίl$]$, Sum):-

sum_lίst(Taίl, TaίlSum),

Sum ίs TaίlSum + Head.

Приведем еще один пример, где рассмотрим функцию получения компонента списка с заданным индексом:

nth0(Index, Lίst, Elem)

Индексация должна начинаться с нуля, а когда нужный компонент не обнаружен, то функция должна завершиться неудачей:

Рисунок 1. Программа. Автор24 — интернет-биржа студенческих работ

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

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

member(Elem, List)

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

member(Elem, $[$Elem|_Tail$]$).

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

member(Elem, Tail).

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