Списки и их представление на Прологе
5.3.1. Основные определения.
В языках, предназначенных для программирования задач искусственного интеллекта, важную роль играют динамические структуры данных, называемые списками. Главное достоинство списков состоит в том, что при их обработке операции вставки, замены и удаления элементов выполняются весьма просто. Списки ¾ структуры данных с последовательным доступом, и поэтому основным средством их обработки является рекурсия.
Список в языке Пролог представляет собой заключенную в квадратные скобки [] последовательность термов, разделенных запятыми:
[<терм1>,<терм2>,…<термn>]. Список¾ это составной терм или структура, главный функтор которой обозначается символом «.» (точка).
Структура Список может быть представлена в виде так называемой точечной пары ·(H,T), где Н ¾ первый элемент списка, называемый головой списка, а Т ¾ все остальные элементы списка, называемые хвостом списка. Голова списка является термом, а хвост ¾списком.
В языке Пролог список, разделенный на головы и хвост, обозначается следующим образом: [H|T], например [a|[d,b,k,l]]. Возможность разделения списка на голову и хвост играет важную роль в программировании рекурсивных процедур обработки списков.
Число элементов в списке называется длиной списка. Длина списка может динамически изменяться в процессе выполнения запроса. Список, не имеющий ни одного элемента, обозначается [] и называется пустым списком. Длина пустого списка равно нулю. Пустой список нельзя разделить на голову и хвост.
|
|
|
Голова и хвост списка могут быть заполнены константами, числами или символьными термами, например [1|[6,8,12,9]] или [a|[r,t,y,u]].
Голова и хвост списка могут быть переменными, например,
[H|LT], здесь Н¾терм, а LT¾переменная, имеющая значение списка.
Переменные в Прологе не типизированы, и поэтому в процессе доказательства вопроса они могут конкретизироваться значениями любого типа. Естественно, что интерпретатор не контролирует соблюдение типов аргументов предикатов, это должен делать программист.
5.3.2. Унификация списков.
Списки представляют собой частный случай составных термов, и их унификация выполняется по общим правилам унификации составных термов. Списки успешно унифицируются, если они имеют одинаковую длину и соответствующие элементы этих списков попарно успешно сопоставимы.
Примеры унификации списков.
1) ? ¾[a]=[].
No
Списки имеют разную длину, унификация невозможна, так как [a] является списком из одного элемента, а [] ¾ пустой список.
2) ? ¾[L]=[a].
L=a
yes
Списки имеют одинаковую длину, переменная L и терм а успешно унифицируются, и переменная L конкретизируется значением а.
|
|
|
3) ? ¾[L]=[a, b, с].
No
Списки имеют разную длину, переменная L обозначает один элемент списка, а другой операнд операции сопоставления является списком из трех элементов.
4) ? ¾[a|L]=[a, b, с].
L=[b,c]
Yes
Унификация успешна, списки имеют одинаковые первые элементы, переменная L, обозначающая хвост первого списка, успешно сопоставляется и конкретизируется значением [b,c], списком, который является хвостом второго списка.
5.3.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]. Þ успех.
Дата добавления: 2018-04-04; просмотров: 494; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!