15 Лекция №14. Работа со списками

Время: 2 часа (90 мин.)

15.1 Основные вопросы

- обработка списков.

15.2 Текст лекции

Описание предиката списка аналогично описанию обычного предиката. Пусть, например, имеется список марок автомобилей, определяемый предикатом car:

car(["Жигули", "Волга", "BMW", "Ford"]).

Рассмотрим программу, обеспечивающую простейшую обработку данного списка:

/* Программа 10*/

domains

car_list = car_name*

car_name = sybol

predicates

car(car_list)

clauses

car(["Жигули", "волга", "BMW", "Ford"]).

В разделе domains определён домен car_list с указанием того, что это список, состоящий из элементов сar_name. Символ "*", после имени car_name обозначает, что это элементы списка. Тип домена элементов списка (symbol) указан в следующей строке.

В разделе predicates в скобках после имени предиката car указывается имя домена списка. В разделе clauses приводится сам список.

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

domains

car_list = symbol

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

Поскольку в программе 10 нет раздела goal, можно делать внешние запросы, например:

Goal:car(X)

В ответ на такой запрос система выдаст полный список марок автомобилей:

X=["Жигули", "Волга", "BMW", "Ford"]

1 Solution

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

Goal:car([_, A2, _, _])

A2="Волга"

1 Solution

Goal:car([A1, A2, _, _])

A1="Жигули", A2="Волга"

2 Solutions

В подобных запросах важно правильно указать позиции искомых элементов списка и общее количество элементов в нём. Например на вопрос car([A1, A2, A3]) не будет получен ответ из-за несоответствия количества элементов в списке и в целевом утверждении.

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

Для иллюстрации метода рассмотрим, например, программу определения длины списка (т.е. количества его элементов):

/* Программа 11 */

domains

spisok = symbol*

predicates

dlina(spisok, integer)

clauses

dlina([ ], 0).

dlina([_, X ], L) :- dlina(X, Lhvosta), L=Lhvosta + 1.

В программе определён предикат dlina, аргументами которого являются список символических имён и целое число. Аргумент spisok соответствует реальному списку, обрабатываемому программой, а целое число определит его искомую длину.

Первое предложение в clauses утверждает, что длина пустого списка равна нулю. Второе предложение определяет правило вычисления длины списка. В заголовке правила список разделён на голову и хвост ([ _ | X ]). Голова обозначена анонимной переменной, а хвост переменной X. Очевидно, что аргументу [ _ | X ] предиката dlina удовлетворит любой непустой список, связывая переменную X с хвостом этого списка. При этом каков первый элемент списка (т.е. его голова) не является существенным, на что и указывает анонимная переменная.

Первая подцель правила - это рекурсивное повторение самого правила, где в качестве объекта предиката dlina указан хвост списка X. При рекурсивном возврате к заголовку правила хвост списка снова будет делится на голову и новый хвост, т.е. произойдёт отделение следующего элемента от списка. Этот процесс будет продолжаться до полного исчерпания списка, а при каждом рекурсивном возврате к заголовку правила новые копии переменной Lhvosta будут помещаться в стек.

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

Ниже на примере описан процесс определения длины списка. Допустим мы сформулировали внешний запрос:

Goal: dlina([a, b, c, d],LN)

Тогда рекурсивное исчерпание списка будет условно выглядеть следующим образом:

dlina([a | [b, c, d],L1)

dlina([b, [c, d],L2)

dlina([c, [d],L3)

dlina([d, [],L4)

dlina([],0)

Условное же представление вычисления длины списка будет выглядеть так:

L4 = 0 + 1 = 1

L3 = L4 + 1 = 2

L2 = L3 + 1 = 3

L1 = L2 + 1 = 4

в результате на введённый запрос система выдаст ответ:

LN=4

1 Solutions

Рассмотрим теперь программы выполнения операций над списками. Ниже приведена программа, обеспечивающая операцию поиска элемента в списке: