Учебно-методическое пособие для студентов, обучающихся по специальности «Информатика»

Список в ПРОЛОГе заключается в квадратные скобки и элементы списка разделяются запятыми. Список, который не содержит ни одного элемента, называется пустым списком.

Примеры списков:

список, элементами которого являются целые числа: [1, 2, 3]

список, элементами которого являются строки: [“One”, “Two”, “Three”]

пустой список: []

Элементами списка могут быть списки: [[-1,3,5],[6,4,2,8]]

Чтобы использовать в ПРОЛОГ-программе списки, необходимо в разделе DOMAINS описать тип домена в формате.

Например,

DOMAINS

list = *

Список является рекурсивным объектом. Он состоит из головы (первого элемента списка) и хвоста (все последующие элемента). Хвост также является списком.

Например, [A, B, C] - список , у которого А – голова, [B,C] - хвост

В ПРОЛОГе имеется операция “|”, которая позволяет делить список на голову и хвост.

[A, B, C] = [A | [B, C] ] = [A | [B | [C] ] ] = [A | [B | [C | [ ] ] ] ]

Пустой список нельзя разделить на голову и хвост. Такая структура позволяет использовать рекурсию для обработки списка.

Пример программы, осуществляющей вывод элементов списка.

DOMAINS

list = integer *

writelist(list)

CLAUSES

writelist ([]).

GOAL

Результат выполнения программы:

10

20

30

В данной программе A – голова списка, Z – его хвост

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

1) генерирование списка;

2) объединение списков;

3) поиск заданного элемента в списке;

4) удаление указанного элемента из списка;

5) вставка указанного элемента в список.

1. Генерирование списка из (N2-N1) последовательных целых чисел, начиная с N1.

Для формирования списка создадим отношение genlist(N1, N2, L), где

N1 – начальный элемент списка

N2 – его верхняя граница

L – список

Возможны случаи:

1) если N1 = N2, тогда N1 – не добавляется в список и L – пустой список.

genlist (N2, N2, [ ]) – первая часть правила (условие останова).

2) если N1 < N2, то N1 помещаем в голову списка, затем увеличиваем N1 на 1 и для нового значения снова вызывается genlist. Получаем вторую часть правила:

genlist (N1, N2, [N1 | L]): - N1 < N2, N = N1+1, genlist (N, N2, L).

Таким образом, правило формирования списка имеет вид:

genlist (N2, N2, [ ]). % нерекурсивная часть правила

genlist (N1, N2, [N1 | L]): - % рекурсивная часть правила

N1 < N2, N = N1+1, GenList (N, N2, L).

Например, для формирования списка [2, 3, 4, 5] следует указать запрос:

GOAL

Создадим отношение append(L1, L2, L3), где L1, L2 – исходные списки, L3 – список, полученный в результате присоединения L2 к L1.

Возможны случаи:

1) если L1 пустой список, то результирующий список L3 равен списку L2. Получаем первую (нерекурсивную) часть правила:

append ([ ], L, L).

2) если L1 не пустой список, то делим его на голову и хвост ( [X | L1]). Вторая (рекурсивная) часть правила:

append ([X | L1], L2, [X | L3]): - append (L1, L2, L3).

Таким образом, правило объединения списков имеет вид:

append ([ ], L, L).

append ([X | L1], L2, [X | L3]): - append (L1, L2, L3).

Например, для объединения списков [1, 2, 3] и [4, 5] следует написать запрос:

GOAL

Результат:

[1, 2, 3, 4, 5]

При выполнении программы из L1 выделяется и заносится в стек по одному элементу (голова списка) до тех пор, пока L1 не станет пустым. После этого выполняется первая часть правила и L3 получает значение L2, то есть L3 = [4, 5] начинается выгрузка элементов из стека и добавление их в голову L3.

Правило append обладает большое гибкостью и позволяет решать множество задач по обработке списка. Его можно использовать для решения обратной задачи: разбиение исходного списка на две части.

Например, чтобы определить все возможные способы разбиения списка [1,2,3], следует составить запрос:

GOAL

append (L1, L2, [1,2,3]), write (“L1=”, L1, “L2=”, L2), fail, nl.

L1 = [ ] L2 = [1, 2, 3]

L1 = [1] L2 = [2, 3]

L1 = [1, 2] L2 = [3]

L1 = [1, 2, 3] L2 = [ ]

3. Поиск заданного элемента

Чтобы определить содержится ли элемент X в списке L создадим отношение member(X, L).

Возможны случаи:

1) если X совпадает с головой списка L, то элемент найден и поиск прекращается. Первая часть правила (нерекурсивная):

member (X, [X | L]).

2) если X не принадлежит голове, то он может принадлежать хвосту. Отбрасываем голову списка и вызываем правило для оставшегося списка. Вторая часть правила (рекурсивная):

member (X, [_ | L]: - member (X, L).

Таким образом, правило поиска элемента имеет вид:

member (X, [X | L]).

member (X, [_ | L]: - member (X, L).

Например, для ответа на вопрос «Содержится ли число 4 в списке [2, 3, 4, 5]?», можно составить запрос:

GOAL

При выполнении поиска X сравнивается с головой L. Если элементы не совпадают, то первый элемент отбрасывается и X сравнивается с головой полученного списка и так далее, пока L не станет пустым списком. Если элемент X найден, то цель достигнута, выводится сообщение “yes”, иначе выводится “no”.

Определим отношение del(X, L, L1), где

X – удаляемый элемент;

L – исходный список;

L1 – список, полученный в результате удаления X из L.

Возможны два случая:

1) если X – голова списка, то результирующий список равен хвосту списка L. Первая часть правила (нерекурсивная):

del(X, [X|L], L).

2) если X принадлежит хвосту, то список L делим на голову и хвост. Для хвоста снова вызывается правило del. Вторая часть правила (рекурсивная):

del(X, [Y|L], [Y|L1]):- del(X,L,L1).

Полная запись правила удаления элемента из списка:

del(X, [X|L], L).

del(X, [Y|L], [Y|L1]):- del (X,L,L1).

Например, для удаления из списка [1, 2, 3, 4] элемента 3, следует составить запрос:

GOAL

del(3, [1, 2, 3, 4], L),Write (L), nl.

П
нет

X

X

X = 3 [3 | 4] первая часть правила выполняется, результирующий список принимает значение хвоста L = [4]. Элементы извлекаются из стека по одному и становятся в голову списка L.

L = [1, 2, 4]

5. Вставка символа X в список

Определим отношение ins(X, L, L1), где

X – добавляемый элемент в список

L – исходный список

L1 – список, полученный в результате вставки элемента Х в список L

Отношение ins(X, L, L1) можно определить через del(X, L1, L). Если для отношения del(X, L1, L) список L1 – исходный список, содержащий элемент Х, то для ins(X, L, L1) список L1 является результирующим. Список L, не содержащий Х, для del(X, L1, L) – результирующий, а для ins(X, L, L1) – исходный.

ins(X, L, L1): - del(X, L1, L).

Например, для вставки элемента 5 в список [1, 2, 3] необходимо составить запрос:

GOAL

ins(5, [1, 2, 3], L),Write (L), nl, fail.

[5, 1, 2, 3]

[1, 5, 2, 3]

[1, 2, 5, 3]

[1, 2, 3, 5]

Примечание: так как отношение ins(X, L, L1) определено через del (X, L1, L), то в разделе CLAUSES должно быть описано также правило del(X, L1, L).

Литература

1. 
   Адаменко А., Кучуров А. Логическое программирование и Visual Prolog.-CПб., 2003.
   
2. 
   Братко И. Программирование на языке ПРОЛОГ для искуственного интеллекта.- М., 1990.
   
3. 
   Ин Ц., Соломон Д. Использование Турбо-Пролога. -М., 1993.
   
4. 
   Клоксин У., Меллиш К. Программирование на языке ПРОЛОГ. -М., 1991.
   
5. 
   Макаллистер Дж. Искусственный интеллект и Пролог на микроЭВМ.- М., 1990.
   
6. 
   Нильсон Н. Искусственный интеллект. М., 1973.
   
7. 
   Попов Э.В. Экспертные системы. М., 1987.
   
8. 
   Симонс Дж. ЭВМ пятого поколения: компьютеры 90-х годов.- М.,1985 г.
   
9. 
   Тимофеев А.В. Информатика и искусственный интеллект.- М.,1992.
   
10. 
    Янсон А. Турбо-Пролог в сжатом изложении. -М.,1990.