Cодержание

4.1 Списки

4.1.1 Представление списка диаграммой

4.1.2 Выделение головы и хвоста списка

4.1.3 Шаблоны списков

4.1.4 Определения отношений через cons форму списка

4.2 Процедуры обработки списков

4.2.1 member

4.2.2 append

4.2.3 Применение append

4.2.4 reverse

4.2.5 Длина списка

4.3 Встроенные предикаты

4.3.1 Простые встроенные предикаты ввода-вывода.

4.3.2 Процедурный смысл встроенных предикатов ввода-вывода.

4.4 Ввод-вывод списков.

4.4.1 Ввод-вывод списка как терма.

4.4.2 Поэлементный ввод-вывод списка.

4.1 Списки

Списки - такая же важная структура данных в Прологе, как и в Лиспе.

Список в Лиспе (a b c d) (1 2 (3))
записывается на Прологе [a,b,c,d] [1,2,[3]]

т.е. элементы записываются в квадратных скобках через запятую.

Элементами списка могут быть любые термы.

Пустой список - не nil , а [ ].

4.1.1 Представление списка диаграммой.

Список в лиспе можно представить через функцию cons

В Прологе функции cons соответствует функтор "." (точка).

.(a,[]) соответствует [a] , это другая форма записи
или

Ответственно список [a,b,c] представляется как структура .(а ,.(b,.(c,[])
или в виде дерева, или диаграммой "виноградная лоза"

Для вложенных списков [a,b,[c,d]]

4.1.2 Выделение головы и хвоста списка

В Лиспе для этого используются функции car и cdr.

В Прологе имеется специальная форма представления списка, называемая cons-формой записи:

[Head|Tail] или [H|T] [a|[]] = [а]

При конкретизации формы списком H сопоставляется с головой списка, а Т - с хвостом.

Например

Таким образом выделяются одновременно голова списка и хвост.

Рассмотрим сопоставление двух списков :

4.1.3 Шаблоны списков.

Шаблон (образец) списка -это форма описания множества (семейства)списков, обладающих определенными свойствами.

Например:

Шаблон списка [X|Y] описывает любой список,состоящий не менее чем из одного элемента.

Шаблон [X,Y|Z] - список, состоящий не менее чем из двух элементов.

Шаблон [b|Z] - список, первым элементом которого является b.

Шаблон [Y,X,Z] - список из трех элементов.

Шаблоны списка используются при описании процедур работы со списками.

4.1.4 Определения отношений через cons форму списка

Задача 1: Определить отношение replace_first, которое заменяет первый элемент списка новым

Например

Это отношение:

Что будет ответом для следующего вопроса ?

4.2 Процедуры обработки списков

Процедура в прологе - это совокупность предложений с головами, представленными одинаковыми термами.

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

4.2.1 member

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

Если X принадлежит L, то истина и ложь в противном случае.

С точки зрения декларативного смысла:

1. X принадлежит списку, если X совпадает с головой списка.
2. X принадлежит списку, если X принадлежит хвосту списка.

Можно записать:

С точки зрения процедурного смысла - это рекурсивная процедура.

Первое предложение терминальное условие.
Когда хвост будет равен [] проверка остановиться.

Второе предложение рекурсивное.
Сокращение списка происходит за счет взятия хвоста (cdr-рекурсия).

Примеры применения

Ответьте на вопрос:

4.2.2 append

Используется для соединения двух списков. т.е

L1 и L2 - списки, а L3 - их соединение.

Для определения процедуры append используем два предложения:

1. Если присоединить пустой список [] к списку L, то получим список L.

2. Если присоединить не пустой список [X|L1] к списку L2, то результатом будет список [X|L3], где L3 получаeтся соединением L1 к L2 :

     |X|      L1       |      L2       |    

  

  

           ----------------------------------------  

  

  

     |X|              L3                |     

С точки зрения процедурной семантики
первое предложение - терминальное условие,
второе - рекурсивное с хвостовой рекурсией.

Рассмотрим примеры применения

Можно использовать для разбиения

4.2.3 Применение append

Процедуру арреnd можно использовать для поиска комбинаций элементов.
Например можно выделить списки слева и справа от элемента

Можно удалить все, что следует за данным элементом и этот элемент тоже:

Можно определить процедуру ,выделяющую последний элемент в списке:

4.2.4 reverse

Процедура reverse обращает список.

1. Пустой список после обращения - пустой.

2. Обратить список [X|L1] и получить список L2 можно, если обратить список L1 в L3 и в хвост ему добавить X

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

4.2.5 Длина списка

Можно, используя рекурсивный вызов, легко посчитать длину списка:

4.3 Встроенные предикаты

До сих пор мы получали ответы в форме предлагаемой прологом:

1. печатались значения переменных присутствующих в вопросе;
2. вопросы полностью записывались после запроса "?-".

Однако можно задавать вопросы и получать ответы в произвольной форме.

Для этого достаточно использовать т.н. встроенные предикаты.

Встроенные предикаты - предикаты исходно определенные в прологе, для которых не существует процедур в базе данных.

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

Встроенные предикаты обычно выполняют функции не связанные с логическим выводом.

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

4.3.1 Простые встроенные предикаты ввода-вывода.

Встроенные предикаты обеспечивают возможности ввода-вывода информации:

1. write/1 - этот предикат всегда успешен. Когда вызывается, то побочным эффектом будет вывод значения аргумента на экран. При бэктрекинге предикат дает неудачу. Бэктрекинг не сбрасывает побочный эффект.
2. nl/0 - этот предикат всегда успешен. Когда вызывается, то побочным эффектом будет перевод на следующую строку. При бэктрекинге предикат дает неудачу. Бэктрекинг не сбрасывает побочный эффект.
3. tab/1 - этот предикат всегда успешен. Когда вызывается, то побочным эффектом будет печать коли- чество пробелов заданное аргументом. Аргумент должен быть целым. При бэктрекинге предикат дает неудачу. Бэктрекинг не сбрасывает побочный эффект.
4. read/1 - этот предикат читает терм , который вводится с клавиатуры и заканчивается точкой. Этот терм сопоста- вляется с аргументом. При бэктрекинге предикат дает неудачу. Бэктрекинг не сбрасывает побочный эффект.

Например,

При вызове

последовательность термов читает значение X,переводит строку,печатает 'X=',пропускает два пробела и печатает значение X.

4.3.2 Процедурный смысл встроенных предикатов ввода-вывода.

Определяя встроенные предикаты мы писали: "этот предикат всегда успешен. Когда вызывается, то побочным эффектом будет... При бэктрекинге предикат дает неудачу. Бэктрекинг не сбрасывает побочный эффект."

Обычно в прологе вход в цель возможен через "call" при вызове и через "redo" при бэктрекинге.

Цель имеет внутреннею структуру:

Для встроенных предикатов нет внутренних точек решения внутри цели.
Она представляется в виде:

4.4 Ввод-вывод списков.

Для ввода-вывода списков возможны следующие два способа.

4.4.1 Ввод-вывод списка как терма.

При этом способе список рассматривается как один терм.

Например, процедура:

При вызове цели

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

Введите список L:
[a,b,c,d].
Список L= [a,b,c,d]

4.4.2 Поэлементный ввод-вывод списка.

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

end - терм , означающий конец списка.

Тогда после вызова цели:

Возникает следующий диалог:

Введите элемент: a.
Введите элемент: b.
Введите элемент: c.
Введите элемент: d.
Введите элемент: end.

Список= a b c d

(c) M.N.Morozov, 1999.