Prolog Language
Рассуждение о данных
Поиск…
замечания
Был создан новый раздел « Структуры данных», в котором даны объяснения некоторых структур + некоторый простой пример (ы) создания. Чтобы содержимое было сжатым и незагроможденным, оно не должно содержать никакой документации по манипулированию данными.
Поэтому этот раздел был переименован в «Рассуждение о данных» с целью обобщения рассуждений о данных в Prolog. Сюда могут входить темы, начиная от «сверху вниз» и заканчивая «обходом списков», а также многих других. Из-за его широкого обобщения следует сделать четкие подразделы!
Рекурсия
Пролог не имеет итерации, но вся итерация может быть переписана с помощью рекурсии. Рекурсия появляется, когда предикат содержит цель, которая ссылается на себя. При написании таких предикатов в Prolog стандартный рекурсивный шаблон всегда имеет как минимум две части:
Базовое (нерекурсивное) предложение : Обычно правило (и) базового блока будет представлять собой наименьший возможный пример (ы) проблемы, которую вы пытаетесь решить, - список без членов или только один член, или если вы «Работая с древовидной структурой, он может иметь дело с пустым деревом или деревом с одним узлом в нем и т. д. Он не рекурсивно описывает базу рекурсивного процесса.
Рекурсивное (продолжение) предложение : содержит любую требуемую логику, включая вызов самому себе, продолжающуюся рекурсию.
В качестве примера мы определим известный предикат append/3 . При просмотре декларативно append(L1,L2,L3) выполняется, когда список L3 является результатом добавления списков L1 и L2 . Когда мы пытаемся выяснить декларативный смысл предиката, мы пытаемся описать решения, для которых выполняется предикат. Трудность здесь заключается в том, чтобы избежать каких-либо пошаговых повторяющихся подробностей, сохраняя при этом в виду процедурное поведение, которое должен проявлять предикат.
% Base case
append([],L,L).
% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
В базовом случае декларативно указывается, что «любой L, приложенный к пустым спискам, равен L», обратите внимание, что это ничего не говорит о том, что L пуст или даже является списком (помните, что в Prolog все сводится к условиям):
?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).
Для описания рекурсивного правила, хотя Prolog выполняет правила слева направо, мы опускаем голову на секунду и сначала смотрим на тело - читаем правило справа налево:
append([X|L1],L2,[X|L3]):- append(L1,L2,L3).
Теперь мы говорим, что если тело имеет место: «если предположить, что append(L1,L2,L3) имеет место"
append([X|L1],L2,[X|L3]) :-append(L1,L2,L3).
Тогда и голова: «тогда также append([X|L1],L2,[X|L3]) »
На простом английском языке это просто означает:
Предполагая, что L3 является конкатенацией L1 и L2, тогда [X, за которым следует L3] также является конкатенацией [X, за которой следуют L1] и L2.
В практическом примере:
«Предполагая, что [1,2,3] является конкатенацией [1] и [2,3], тогда [a, 1,2,3] также является конкатенацией [a, 1] и [2,3]. »
Теперь давайте посмотрим на некоторые запросы:
Всегда полезно сначала проверить ваш предикат с помощью наиболее общего запроса, а не предоставить ему конкретный сценарий. Подумайте об этом: из-за объединения Prolog мы не обязаны предоставлять тестовые данные, мы просто передаем бесплатные переменные!
?- append(L1,L2,L3).
L1 = [],
L2 = L3 ; % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ; % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ; % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ; % Answer #4
...
Давайте заменим свободную переменную _G1162 нотации на алфавитные буквы, чтобы получить лучший обзор:
?- append(L1,L2,L3).
L1 = [],
L2 = L3 ; % Answer #1
L1 = [_A],
L3 = [_A|L2] ; % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ; % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ; % Answer #4
...
В первом ответе базовый случай был сопоставлен с образцом, а Prolog создавал экземпляр L1 в пустой список и унифицировал L2 и L3 доказывая, что L3 является конкатенацией пустого списка и L2.
В ответе №2, с помощью хронологического возврата, рекурсивное предложение вступает в игру, и Prolog пытается доказать, что какой-то элемент в голове L1 объединенный с L2 является L3 с тем же элементом в его списке. Для этого новая свободная переменная _A унифицирована с головкой L1 и L3, как доказано, теперь [_A|L2] .
Выполняется новый рекурсивный вызов, теперь с L1 = [_A] . Еще раз Prolog пытается доказать, что какой-то элемент, помещенный в головку L1 , объединенный с L2 является L3 с тем же самым элементом в голове. Обратите внимание, что _A уже является главой L1 , которая идеально соответствует правилу, поэтому теперь, через рекурсию, Prolog ставит _A перед новой свободной переменной, и мы получаем L1 = [_A,_B] и L3 = [_A,_B|L2]
Мы отчетливо видим, что рекурсивный шаблон повторяется и может легко увидеть, что, например, результат 100-го шага в рекурсии будет выглядеть так:
L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]
Примечание: как это типично для хорошего кода Prolog, рекурсивное определение append/3 дает нам возможность не только проверять , является ли список конкатенацией двух других списков, но также генерирует все возможные ответы, удовлетворяющие логическим отношениям, либо полностью или частично инстанцированные списки.
Доступ к спискам
член
member/2 имеет member(?Elem, ?List) подписи member(?Elem, ?List) и обозначает true если Elem является членом List . Этот предикат можно использовать для доступа к переменным в списке, где различные решения извлекаются с помощью обратного отслеживания.
Примеры запросов:
?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.
?- member(X,[Y]).
X = Y.
?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...
Согласование образцов
Когда индексы, которые вам нужны для доступа, малы, сопоставление образцов может быть хорошим решением, например:
third([_,_,X|_], X).
fourth([_,_,_,X|_], X).