prolog - 高阶 "solutions"谓词

Question

我正在使用缺少 findall 的高阶 Prolog 变体.

还有一个关于实现我们自己的问题 findall这里:Getting list of solutions in Prolog .

低效的实现是:

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, []).

有效率的

need a "solutions" higher-order predicate:

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

什么是 solutions ?我可以实现我自己的 solutions高阶 lambda Prolog 中的谓词？

Answer 1

是 , 如果 findall/3不可用，您可以例如通过 实现它动态数据库 .

例如，对于 parent 的具体用例:

list_parents(_) :-
parent (P，_)，
断言(父(P))，
错误的。
list_parents(Ps) :-
短语(retract_parents，Ps)。

缩回 parent -->
( { 收回(父(P)) } ->
[P],
缩回 parent
; []
)。

示例查询:

?- list_parents(Ps)。
Ps = [pam，乔治]。

您可以将此与 sort/2 结合使用为了渐近优化性能，避免“朴素”解决方案的二次开销以删除重复项。

当心 不过:首先，这不是线程安全的。为了使其线程安全，您需要添加更多与当前线程相关的信息。

其次，如果你实现了成熟的findall/3这样，你必须照顾嵌套findall/3调用。

一种方法是断言两种术语:

solution(S) ，例如 solution(parent(pam)) ，表明通过最近的 findall/3 在回溯中找到的具体解决方案调用

mark , 表示新的 findall/3从这里开始

收集解决方案时，您只能继续到最近的 mark .

有关这些问题的详细介绍，请参阅 Richard O'Keefe 的书。