在不多次使用 call_nth/2 或不使用 findall/3 的情况下找到所需的解决方案？

Question

据我了解，call_nth(:Goal, ?Nth) returns Goal的第N个解，但同时它偷偷计算了之前的所有解（从第1到（ N-1)th) 并简单地忽略它们。如果我们希望对 1 和 N-1 之间的每个 X 的第 X 个和第 (X+1) 个解进行比较，call_nth 变得非常昂贵，因为它基本上一直在计算前面步骤中已经计算过的解。我想知道是否有更有效的方法来解决这种形式的问题，当然不用 findall/3。

（一个典型的例子是下面的脚本，如果谓词中不存在 GOAL，它会找到 GOAL 或最接近它的最大值。）

num(10).
num(20).
num(30).
num(40).
num(50).

search_for_goal(GOAL,RESULT):-
    search_for_goal(GOAL,0,1,RESULT).

search_for_goal(GOAL,_,COUNTER,GOAL):-
    call_nth(num(GOAL),COUNTER),!.
search_for_goal(GOAL,CURRENT_MAX,COUNTER,RESULT):-
    call_nth(num(X),COUNTER),
    COUNTER2 is COUNTER+1,
    (  X=<CURRENT_MAX->
       search_for_goal(GOAL,CURRENT_MAX,COUNTER2,RESULT)
    ;  search_for_goal(GOAL,X,COUNTER2,RESULT)
    ).
search_for_goal(_,CURRENT_MAX,COUNTER,CURRENT_MAX):-
    \+call_nth(num(_),COUNTER).

Answer 1

使用 SWI-Prolog，这可以通过 Prolog 引擎实现。为了说明这一点，请考虑我自己的 findall/3 谓词版本，其中 returns 只有 even-numbered 个解决方案。

my_findall(Templ, Goal, List) :-
    setup_call_cleanup(
    engine_create(Templ, Goal, E),
    get_answers(E, List),
    engine_destroy(E)).

get_answers(E, [H|T]) :-
    /* Skip next solution. */
    engine_next(E, _),
    /* Take next solution. */
    engine_next(E, H),
    !,
    get_answers(E, T).

get_answers(_, []).

查询方式：

my_findall(X,member(X,[1,2,3,4]),Y)

Returns只有n为偶数的第n个解。

Y = [2, 4]

在不多次使用 call_nth/2 或不使用 findall/3 的情况下找到所需的解决方案？

Finding a desired solution without using call_nth/2 multiple times or the use of findall/3?

prolog

time-complexity

meta-predicate