2. Унификация списков.

Списки представляют собой частный случай составных термов, и их унификация выполняется по общим правилам унификации составных термов. Списки успешно унифицируются, если они имеют одинаковую длину и соответствующие элементы этих списков попарно успешно сопоставимы.

Примеры унификации списков. 1) ?  [a]=[]. No Списки имеют разную длину, унификация невозможна, так как [a] является списком из одного элемента, а []  пустой список.

2. ?  [L]=[a]. L=a yes

Списки имеют одинаковую длину, переменная L и терм а успешно унифицируются, и переменная L конкретизируется значением а.

2. ?  [L]=[a, b, с]. No

Списки имеют разную длину, переменная L обозначает один элемент списка, а другой операнд операции сопоставления является списком из трех элементов.

2. ?  [a|L]=[a, b, с]. L=[b,c]

Yes

Унификация успешна, списки имеют одинаковые первые элементы, переменная L, обозначающая хвост первого списка, успешно сопоставляется и конкретизируется значением [b,c], списком, который является хвостом второго списка.

3. Предикат list.

Предикат list(X) во многих версиях языка Пролог является предопределенным предикатом и предназначен для распознавания, является ли терм X списком или нет.

Декларативное описание этого отношения имеет следующий вид: Для любого X предикат list(X) будет истинен, если X пустой список или выделенный из Х хвост является списком.

Для того, чтобы проверить, является ли X списком, нужно разделить Х на голову и хвост и убедится, что хвост является списком. Процедура list(X)  рекурсивна. При каждом рекурсивном обращении к процедуре list длина списка уменьшается, успешное завершение рекурсии наступит тогда, когда хвост очередного списка станет пустым. Правило для пустого списка является условием завершения рекурсии, так как пустой список есть список.

Процедура list имеет вид:

list(L):[]. list(L):L=[H|T],list(T). Переменная H во втором правиле может быть заменена анонимной переменной, так как ее значение не используется. Более компактная запись процедуры list имеет вид:

list([]). list([H|T]):  list(T).

Рассмотрим пример запроса к процедуре list.

?  list([1,2,3]).

ТР: list([1,2,3]).

Шаг 1: ТЦ: list([1,2,3]).

Пр1: []=[1,2,3].  неуспех

Пр2: [1|[2,3]]=[_|T1] T1=[2,3]

ТР: list([2,3]).

Шаг 2: ТЦ: list([2,3]).

Пр1: []=[2,3].  неуспех

Пр2: [2|[3]]=[_|T1] T1=[3]

ТР: list([3]).

Шаг 3: ТЦ: list([3]).

Пр1: []=[3].  неуспех

Пр2: [3|[]]=[_|T1] T1=[]

ТР: list([]).

Шаг 4: ТЦ: list([]).

Пр1: []=[].  успех

Переход на шаг 3. Истинность ТЦ на шаге 4 влечет истинность цели на шаге 3 list([3]).

Переход на шаг 2. Истинность ТЦ на шаге 3 влечет истинность цели на шаге 2 list([2,3]).

Переход на шаг 1. Истинность ТЦ на шаге 2 влечет истинность цели на шаге 1 list([1,2,3]).

ТР:  успех.

Результат вычисления запроса list([1,2,3].  успех.

4. Типовые процедуры обработки списков на языке Пролог.

   1. Предикат length.

Предикат определения длины списка length(L,N) является предопределенным предикатом во многих системах программирования на языке Пролог. Схема отношения этого предиката имеет вид:

length(<список>,<длина списка>).

Декларативное описание предиката length(L,N) формулируется следующим образом:

Предикат length(X, 0) будет истинным, если X пустой список, т.е. длина пустого списка равна нулю. Если список можно разделить на голову и хвост, то длина списка равна длине хвоста списка плюс 1.

Процедура length(L,N) состоит из двух правил:

length([],0).

length([_|T],N):length(T,N1),N is N1+1.

Рассмотрим пример запроса к процедуре length.

?  length([1,2,3], N).

ТР: length([1,2,3], N).

Шаг 1: ТЦ: length([1,2,3], N).

Пр1: []=[1,2,3].  неуспех

Пр2: [1|[2,3]]=[_|T11] T11=[2,3]

ТР: length([2, 3], N11),N is N11+1.

Шаг 2: ТЦ: length([2, 3], N11).

Пр1: []=[2,3].  неуспех

Пр2: [2|[3]]=[_|T12] T12=[3]

ТР: length([3], N12),N11 is N12+1,N is N11+1.

Шаг 3: ТЦ: length([3]).

Пр1: []=[3].  неуспех

Пр2: [3|[]]=[_|T13] T13=[]

ТР: length([], N13),N12 is N13+ 1,N11 is N12+1,N is N11+1.

Шаг 3: ТЦ: length([], N13).

Пр1: []=[].  успех

{N13=0}

ТР: N12 is N13+ 1,N11 is N12+1,N is N11+1.

Шаг 4: ТЦ: N12 is 0+ 1.

{N12=1}

ТР: N11 is N12+1,N is N11+1.

Шаг 4: ТЦ: N11 is 1+ 1.

{N11=2}

ТР: N is N11+1.

Шаг 4: ТЦ: N is 2+ 1.

{N=2}

ТР: .

Успех.

Ответ: {N=2}