Simultaneously visit solutions to two or more backtrackable predicates

user_14411997 0
Viewed 83

If I had two predicates that generate values in a sequence, for example:

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

How can I iterate through them so that I get the solutions:

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

Trying the normal way of course doesn't work:

?- 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 ;

Of course I can collect the two in lists separately:

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

but this is what I want to avoid. I don't want to make the full list, maybe it is too big. Or maybe I want to use something like between(1, inf, X) as one of the generators.

There seems to be a solution for something similar called merge and outlined here: https://www.swi-prolog.org/pldoc/man?section=engine-examples but it does something different.

prolog
2 Answers

I think that it is possible to simultaneously visit solutions to two backtrackable predicates using engines.

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).

Here are some examples:

?- 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.

TIME COMPLEXITY

To see that the time complexity is O(n), consider the following predicate:

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)))).

Empirical results (SWI-Prolog, version 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.

As we can observe, when the number of answers doubles, time doubles as well.

user_115359400

The answer by @slago is the solution for SWI-Prolog. I have now defined the following predicate (which also is SWI-Prolog specific):

:- 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
        ).

It works as the other answer:

?- 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.
user_144119970
Related