Prolog #4: Задачи и примеры #1

Пример 5 - Генерация цепочки

Если мы вернемся к примеру 3.3, конечному автомату, то мы можем применить полученные знания (о списках) в этой задаче. Мы хотим определить предикат chain, который получая на вход два узла расположит узлы в путь от первого до второго узла в виде списка. Этот список узлов и называется цепочкой (chain). Для начала, следуя духу Prolog, мы хотим определить предикат с тремя параметрами

chain(X, Y, Z)

где первый параметр – это изначальный узел, второй параметр – конечный узел, а третий – это итоговый список. Мы можем думать о двух первых параметрах, как о входных параметрах, а о третьем – как о выходном (несмотря на то, что он не обязан играть эту роль).

Способ, которым мы можем построить определение chain состоит в размышлении о условиях, при которых цепочка будет существовать (используя преимущества рекурсии, при необходимости). Так как цепочка – это всего лишь список узлов, составляющих путь, нам следует использовать определение пути, беря каждый элемент пути и укладывая его в список. Первая мысль, которая возникает, это то, что ребро из X в Y – это список [X, Y]. Это легко проделать в Prolog:

chain(X, Y, [X, Y]) :- edge(X, Y).

Помните, что мы читаем это определение так: “Если существует ребро из X в Y, то [X, Y] – это цепочка из X в Y”. Разумеется, вполне возможно, что не такого просто пути. Но даже если и так, всегда есть первый шаг, например, из X в некий узел I, а затем можно добраться из I в Y. Попахивает рекурсией и вы совершенно правы. Если существует путь из I в Y, тогда существует цепочка, а значит мы можем и X туда присоединить. Вот трансляция этих размышлений в Prolog:

chain(X, Y, [X,Y]) :- edge(X, Y).

Если не удается обнаружить никакого пути к Y, тогда пустой список – это цепочка. Вот полное определение chain. Почему последняя строка – это факт, а не правило?

chain(X, Y, [X,Y]) :- edge(X, Y).
chain(X, Y, [X|Z]) :- edge(X, I), path(I, Y), chain(I, Y, Z).
chain(X, Y, []).

Есть важный момент в этом примере. Если вы теперь попробуете генерировать цепочки из, скажем, a в d, вы обнаружите, что решение не сгенерировалось – в действительности система впала в бесконечный цикл, пытаясь найти путь к d. Пролог всегда старается унифицировать предикат начиная с его первого определения и до тех пор, пока не найдет унификатор. Это означает, что если вы поместите первое правило edge, в котором определяются циклы в графе в конец определения edge, эти определения (правила) будут использованы позднее. Чтобы удостовериться, что это влияет на некоторые запросы, попробуйте изменить порядок определений и выполнить те же запросы, что делали раньше.

Пример 5 – Переворот списка

Приведем пример программы, которая переворачивает список. Работает она с помощью рекурсии и использования append. Вызов reverse требует двух аргументов, первый – это входной список, второй – выходной (результат).

reverse([], []). %%% Переворот пустого списка – это пустой список.
reverse([H|Tail], Result) :- %%% Чтобы перевернуть не пустой список,
reverse(Tail, Tailreversed), %%% переворачиваем хвост,
append(Tailreversed, [H], Result). %%% присоединяем результат к списку

Продолжение следует