|
Предикат 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([]). %Пр.1
list([H|T]): ¾list(T). %Пр.2
Рассмотрим пример запроса к процедуре 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]. Þ успех.
Предикат length
Предикат определения длины списка length(L,N) является предопределенным предикатом во многих системах программирования на языке Пролог. Схема отношения этого предиката имеет вид:
length(<список>,<длина списка>).
Декларативное описание предиката length(L,N) формулируется следующим образом:
Предикат length(X, 0) будет истинным, если X ¾пустой список, т.е. длина пустого списка равна нулю. Если список можно разделить на голову и хвост, то длина списка равна длине хвоста списка плюс 1.
Процедура length(L,N) состоит из двух правил:
length([],0). %Пр.1
length([_|T],N):¾length(T,N1),N is N1+1. %Пр.2
Рассмотрим пример запроса к процедуре 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}
| 
