4

我正在使用缺少findall.

在这里实现我们自己的还有另一个问题findall：在 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, []).

有效率的

需要一个“解决方案”的高阶谓词：

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

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

4

2 回答 2

3

如果你的 Prolog 有某种不可回溯的赋值，比如 SWI-Prolog 'global' variables，你可以用这种方式实现（当心，简单的代码）：

:- 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 动态数据库（断言/撤回），并且（在 SWI-prolog 中）甚至可以在多线程应用程序中使用。

编辑

感谢@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]].

编辑

这是solutions/3 的变体，按顺序构建结果列表，以避免最终的reverse/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).
于 2017-11-12T09:47:04.847 回答
3

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

例如，对于父母的具体用例：

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

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

示例查询：

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

您可以将其与sort/2渐近优化性能结合起来，避免“幼稚”解决方案的二次开销以删除重复项。

但请注意：首先，这不是线程安全的。为了使其线程安全，您需要添加与当前线程有关的更多信息。

其次，如果您以这种方式实现成熟findall/3，则必须注意嵌套 findall/3调用。

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

  • solution(S)，例如solution(parent(pam))，表示通过最近一次findall/3调用在回溯中找到的具体解决方案
  • mark，表示新的findall/3开始在这里

收集解决方案时，您只进行到最近的mark.

请参阅 Richard O'Keefe 的书以获得对这些问题的良好介绍。

于 2017-11-11T09:28:33.607 回答