Предикат "решений" высшего порядка

Question

Я использую вариант Пролога высшего порядка, в котором отсутствует findall,

Есть еще один вопрос по реализации нашего собственного findall здесь: Получение списка решений в Прологе.

Неэффективная реализация:

parent(pam, bob). %pam is a parent of bob
parent(george, bob). %george is a parent of bob

list_parents(A, Es, [X|Xs]) :-
   parent(X, A),
   \+ member(X, Es),
   list_parents(A, [X|Es], Xs).
list_parents(A, Es, []).

Эффективный

нужен предикат "решения" высшего порядка:

list_parents(X, Ys) :- solutions(parent, [X, W], 1, Ys)

Что такое solutions? Могу ли я реализовать свой собственный solutions предикат в лямбда-прологе высшего порядка?

Answer 1

Да, если findall/3 были недоступны, вы могли бы реализовать это, например, через динамическую базу данных.

Например, для конкретного случая использования родителей:

list_parents (_): -
        родитель (P, _),
        assertz (родитель (P)),
        ложный.
list_parents(Ps):-
        фраза (retract_parents, Ps).

retract_parents ->
        ({ retract (parent (P))} ->
            [П],
            retract_parents;   []).

Пример запроса:

? - list_parents (Ps).
Ps = [pam, george].

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

Будьте осторожны: во-первых, это не потокобезопасно. Чтобы сделать его потокобезопасным, вам нужно добавить больше информации, относящейся к текущему потоку.

Во-вторых, если вы реализуете полноценный findall/3 таким образом, вы должны заботиться о вложенных findall/3 звонки.

Одним из способов сделать это является утверждение двух видов терминов:

• solution(S), такие как solution(parent(pam)) с указанием конкретного решения, которое было найдено при возврате через самый последний findall/3 вызов
• mark, указывая, что новый findall/3 начинается здесь

При сборе решений вы переходите только к самым последним mark,

См. Книгу Ричарда О'Киф для хорошего знакомства с этими вопросами.

Answer 2

Если ваш Prolog имеет какое-то не подлежащее возврату назначение, например, "глобальные" переменные SWI-Prolog, вы можете реализовать (остерегайтесь, простой код) следующим образом:

:- meta_predicate solutions(0, ?).
:- meta_predicate solutions(+, 0, ?).

solutions(G, L) :-
    solutions(G, G, L).

solutions(P, G, L) :-
    ( nb_current(solutions_depth, C) -> true ; C=1 ),
    D is C+1,
    nb_setval(solutions_depth, D),
    atom_concat(solutions_depth_, D, Store),
    nb_setval(Store, []),
    (   G,
        nb_getval(Store, T),
        nb_setval(Store, [P|T]),
        fail
    ;   nb_getval(Store, R)
    ),
    nb_delete(Store),
    nb_setval(solutions_depth, C),
    reverse(R, L).

Использование "глобальных" переменных приводит к более эффективному выполнению. WRT динамическая база данных (assert/retract) и (в SWI-прологе) могут использоваться даже в многопоточных приложениях.

редактировать

Благодаря комментарию @false переместил вырез (ы) перед reverse/2 и ввел стек для реентерабельных вызовов: например

?- solutions(X-Ys,(between(1,3,X),solutions(Y,between(1,5,Y),Ys)),S).
S = [1-[1, 2, 3, 4, 5], 2-[1, 2, 3, 4, 5], 3-[1, 2, 3, 4, 5]].

редактировать

Вот вариант решения /3, строящий список результатов по порядку, чтобы избежать финального обратного вызова / 2. Добавление результатов в хвост списка немного сложно...

solutions(P, G, L) :-
    ( nb_current(solutions_depth, C) -> true ; C=1 ),
    D is C+1,
    nb_setval(solutions_depth, D),
    atom_concat(solutions_depth_, D, Store),
    (   G,
        ( nb_current(Store, U/B) -> B = [P|R], Q = U/R ; Q = [P|T]/T ),
        nb_setval(Store, Q),
        fail
    ;   ( nb_current(Store, L/[]) -> true ; L = [] )
    ),
    nb_delete(Store),
    nb_setval(solutions_depth, C).