Пролог - возвращает результат вместо печати в алгоритме

Question

Я знаю, что технически нет "возврата" в Прологе, но я не знал, как сформулировать вопрос иначе.

Я нашел пример кода алгоритма для поиска маршрутов между станциями метро. Он работает хорошо, однако предполагается, что он просто распечатывает результат, поэтому его сложно расширить или выполнить. findall/3 например.

% direct routes
findRoute(X,Y,Lines,Output) :- 
    line(Line,Stations),
    \+ member(Line,Lines),
    member(X,Stations),
    member(Y,Stations),
    append(Output,[[X,Line,Y]],NewOutput),
    print(NewOutput).

% needs intermediate stop
findRoute(X,Y,Lines,Output) :- 
    line(Line,Stations),
    \+ member(Line,Lines),
    member(X,Stations),
    member(Intermediate,Stations),
    X\=Intermediate,Intermediate\=Y,
    append(Output,[[X,Line,Intermediate]],NewOutput),
    findRoute(Intermediate,Y,[Line|Lines],NewOutput).

line это предикат с атомом и списком, содержащим станции.
Например: line(s1, [first_stop, second_stop, third_stop])

Так что я пытаюсь избавиться от этого print в строке 11 и добавьте дополнительную переменную в мое правило, чтобы сохранить результат для последующего использования. Однако я с треском провалился, потому что независимо от того, что я пробую, он либо входит в бесконечный цикл, либо возвращает false.

Сейчас:

?- findRoute(first_stop, third_stop, [], []).
% prints [[first_stop,s1,third_stop]]

Хочу:

?- findRoute(first_stop, third_stop, [], R).
% [[first_stop,s1,third_stop]] is stored in R

Answer 1

Как и вы, я также часто вижу эту модель среди начинающих прологов, особенно если они используют плохие книги и другие материалы:

solve :-
     .... some goals ...
     compute(A),
     write(A).

Почти каждая строка в приведенном выше проблематична по следующим причинам:

1. "решить" является обязательным условием. Это не имеет смысла в декларативном языке, таком как Prolog, потому что вы можете использовать предикаты в нескольких направлениях.
2. "вычислить" также является обязательным условием.
3. write/1 является побочным эффектом, и его выход доступен только на системном терминале. Это не дает нам простого способа проверить предикат.

Такие шаблоны всегда должны выглядеть примерно так:

solution(S) :-
     condition1(...),
     condition2(...),
     condition_n(S).

где condition1 и т.д. - это просто чистые цели, которые описывают, что это означает, что S это решение.

При запросе

?- solution(S).

затем привязки для S будет автоматически напечатан на верхнем уровне. Позвольте toplevel сделать печать для вас!

В вашем случае есть прямое решение: просто сделайте NewOutput один из аргументов и уберите последний побочный эффект:

маршрут (X, Y, Lines, Output, NewOutput): - 
    линия (Линия, Станции),
    \+ член (Линия, Линии),
    участник (X, Станции),
    член (Y, Станции),
    append(Output, [[X,Line,Y]], NewOutput).

Обратите внимание, что я изменил название на просто route/5потому что предикат имеет смысл также, если все аргументы уже созданы, что полезно для тестирования и т. д.

Более того, при описании списков вы часто получаете много пользы от использования нотации dcg.

Код будет выглядеть примерно так:

маршрут (S, S, _) -> [].          % case 1: уже есть
маршрут (S0, S, Lines) ->         % case 2: требуется промежуточная остановка
    { line_stations(Line, Stations0),
      maplist(диф (линия), линии),
      выберите (S0, Станции0, Станции),
      участник (S1, Станции)},
    [ссылка (S0, линия, S1)],
    маршрут (S1, S, [Линия | Линии]).

Удобно, вы можете использовать это для описания объединения списков без необходимости append/3 так много. Я также сделал несколько других изменений для улучшения чистоты и читабельности, и я оставляю выяснение точных различий в качестве простого упражнения.

Вы вызываете это с помощью предиката интерфейса DCG phrase/2, с помощью:

?- phrase(route(X,Y,[]), Rs).

где Rs это найденный маршрут. Обратите внимание, что я использую термины формы link/3 обозначить ссылки маршрута. Хорошей практикой является использование специальных терминов, когда арность известна. Списки, например, хороши, если вы заранее не знаете, сколько элементов вам нужно представить.