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

Главной операцией при работе со списками является расщепление списка на голову и хвост.

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

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

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

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

Например

р([a,b,c]).

		?-p([X|Y]). yes X=a Y=[b,c]

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

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

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

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

Например:

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

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

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

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

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

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

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

Например

		?-replace_first([a,b,с],w,X). X=[w,b,c]

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

replace_first([H|T],A,[A|T]). или replace_first([_|T],A,[A|T]).

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

?-replace_first([_|T],A,[a,b,c]).

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

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

Например

		?-replace_first([a,b,с],w,X). X=[w,b,c]

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

replace_first([H|T],A,[A|T]). или replace_first([_|T],A,[A|T]).

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

?-replace_first([_|T],A,[a,b,c]).

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

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

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

• member - проверяет принадлежность элемента списку

• append - используется для соединения двух списков

• reverse - обращает список

• length - вычисляет длину списка

• remove - удаляет элемент из списка

4.2.1 member

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

member(X, L)

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

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

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

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

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

member(X, [X|T]). member(X, [H|T]) :-member(X, T).

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

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

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

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

		?-member(a, [a, b, с]). Yes ?-member(X, [a, b, с]). Yes X = a X = b X = c

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

		?-member(a, X).

4.2.2 append

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

append (L1, L2, L3)

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

		?-append ([a, b], [c], [a,b,c]). Yes

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

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

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

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

|X| L1 | L2 | ---------------------------------------- |X| L3 |

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

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

		?-append([a], [b, c], L). L=[a, b, c] ?-append([a], L, [a, b, c]). L=[b, c] ?-append(L, [b, c], [a, b, c]). L=[a]

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

?-append(L1, L2, [a, b, c]). L1=[] L2=[a, b, c]; L1=[a] L2=[b, c]; L1=[a, b] L2=[c]; L1=[a, b, c] L2=[]