同时访问两个或多个可回溯谓词的解决方案

Question

如果我有两个谓词按顺序生成值，例如：

between(1, 3, X), sub_atom(abc, _, 1, _, Y)

如何遍历它们以获得解决方案：

X = 1, Y = a ;
X = 2, Y = b ;
X = 3, Y = c.

尝试正常的方法当然不行：

?- between(1, 3, X), sub_atom(abc, _, 1, _, Y).
X = 1, Y = a ;
X = 1, Y = b ;
X = 1, Y = c ;
X = 2, Y = a ;

当然我可以把这两个分别收集在列表中：

?- findall(X, between(1, 3, X), Xs), findall(Y, sub_atom(abc, _, 1, _, Y), Ys).
Xs = [1, 2, 3],
Ys = [a, b, c].

但这是我想避免的。我不想列出完整的清单，也许它太大了。或者，也许我想使用 between(1, inf, X) 之类的东西作为生成器之一。

似乎有一个类似的解决方案，称为 merge 并在此处概述：https://www.swi-prolog.org/pldoc/man?section=engine-examples 但它做了一些不同的事情。

Answer 1

我认为可以使用引擎.

同时访问两个可回溯谓词的解决方案

simultaneously_visit_generators(G1, G2, X-Y) :-
   engine_create(X, G1, E1),
   engine_create(Y, G2, E2),
   simultaneously_visit_engines(E1, E2, X-Y).

simultaneously_visit_engines(E1, E2, X-Y) :-
   (   engine_next(E1, X),
       engine_next(E2, Y)
   ->  true
   ;   !,
       fail ).

simultaneously_visit_engines(E1, E2, X-Y) :-
   simultaneously_visit_engines(E1, E2, X-Y).

这里有一些例子：

?- simultaneously_visit_generators(between(1,3,X), sub_atom(abc,_,1,_,Y), X-Y).
X = 1,
Y = a ;
X = 2,
Y = b ;
X = 3,
Y = c ;
false.

?- simultaneously_visit_generators(between(1,inf,X), member(Y,[a,b,c]), X-Y).
X = 1,
Y = a ;
X = 2,
Y = b ;
X = 3,
Y = c ;
false.

?- simultaneously_visit_generators(between(1,2,X), between(1,inf,Y), X-Y).
X = Y, Y = 1 ;
X = Y, Y = 2 ;
false.

时间复杂度

要看到时间复杂度是O(n)，考虑下面的谓词：

running_time :-
   forall( between(16, 20, Exponent),
           ( N is 2**Exponent,
             time(findall(X-Y,
                          simultaneously_visit_generators(between(1, inf, X),
                                                          between(1, N, Y), X-Y), _L)))).

实证结果（SWI-Prolog，版本 8.2.4）：

?- running_time.
% 262,162 inferences, 0.063 CPU in 0.078 seconds (80% CPU, 4194592 Lips)
% 524,306 inferences, 0.125 CPU in 0.125 seconds (100% CPU, 4194448 Lips)
% 1,048,594 inferences, 0.297 CPU in 0.297 seconds (100% CPU, 3532106 Lips)
% 2,097,170 inferences, 0.531 CPU in 0.547 seconds (97% CPU, 3947614 Lips)
% 4,194,322 inferences, 1.094 CPU in 1.109 seconds (99% CPU, 3834809 Lips)
true.

我们可以观察到，当答案数量翻倍时，时间也会翻倍。

Answer 2

@slago 的回答是SWI-Prolog 的解决方案。我现在定义了以下谓词（也是 SWI-Prolog 特定的）：

:- meta_predicate zip(?,0, ?,0, -, -).

zip(T1, G1, T2, G2, A1, A2) :-
    engine_create(T1, G1, E1),
    engine_create(T2, G2, E2),
    repeat,
        (   engine_next(E1, A1),
            engine_next(E2, A2)
        ->  true
        ;   !, fail
        ).

它作为另一个答案：

?- zip(X, between(1, inf, X), Y, sub_atom(abc, _, 1, _, Y), A, B).
A = 1,
B = a ;
A = 2,
B = b ;
A = 3,
B = c ;
false.

同时访问两个或多个可回溯谓词的解决方案

Simultaneously visit solutions to two or more backtrackable predicates

prolog