Alternative to findall

3
votes

I'm trying to create an alternative to findall in Prolog.

What I have is:

solutions(A,T,S) :- 
   T,
   assert(temp(A)),
   fail.
solutions(A,T,S) :-
   obtain([],S).

obtain(X,S) :-
   retract(temp(A)),
   obtain([A|X],S).
obtain(S,S).

This is however giving me inconsistent results. What is wrong? Thank you in advance.

2
prologprolog-findall
Can you describe what is inconsistent in your results? - lurker
Perhaps using assertz instead of assert will solve this mysterious inconsistency. - Eugene Sh.
@EugeneSh. I believe assert and assertz do the same thing. :) - lurker
@lurker Will assert guarantee appending to the end? I can't find anything mentioning it.. - Eugene Sh.
@EugeneSh. If it's SWI Prolog, then I believe it does since assert/1 is deprecated in favor of assertz/1. I don't know why it would not be consistent. I'm still waiting for the OP to explain what is inconsistent. :) - lurker

2 Answers

3
votes

There are several problems with your implementation.

  1. There is no cleanup in the beginning. Add retractall(temp(_)) prior to T,

  2. obtain/2 will succeed with many different answers, because retract(temp(A)) will give many answers, and because the second clause obtain(S,S) will always be a solution. This can be saved by adding a cut after retract.

    | ?- obtain([],S).
S = [2,1] ? ;
S = [1] ? ;
S = [2] ? ;
S = [] ? ;
no

  3. You may want to change the order, either by using asserta/1 or by redefining obtain/2.

  4. Your definition is not re-entrant. That cannot be solved easily. You would need either some gensym like functionality or some even more advanced features.

  5. For the fine print of assert/1 vs. assertz/1 see this answer.

0
votes

Try this, us a cut (!) after retract/1 and explicitly assertz/1:

solutions(A,T,_) :- 
   T,
   assertz(temp(A)),
   fail.
solutions(_,_,S) :-
   obtain(S).

obtain([A|S]) :-
   retract(temp(A)), !,
   obtain(S).
obtain([]).

Works fine, but is not reentrant, the second query result is wrong:

?- solutions(X,between(1,3,X),L).
L = [1, 2, 3].

?- solutions(X-R,(between(1,3,X),solutions(Y,between(1,X,Y),R)),L).
L = [3-[2-[1-[1], 1, 2], 1, 2, 3]].

Edit 08.11.2020:
Here is a reentrant solution using gensym/2:

solutions(A,T,L) :-
   setup_call_cleanup(
      gensym('bag',B),
      solutions(B,A,T,L),
      retractall(temp(B,_))).

solutions(B,A,T,_) :- 
   T,
   assertz(temp(B,A)),
   fail.
solutions(B,_,_,S) :-
   obtain(B,S).

obtain(B,[A|S]) :-
   retract(temp(B,A)), !,
   obtain(B,S).
obtain(_,[]).

Now both queries work fine:

?- solutions(X,between(1,3,X),L).
L = [1, 2, 3].

?- solutions(X-R,(between(1,3,X),solutions(Y,between(1,X,Y),R)),L).
L = [1-[1], 2-[1, 2], 3-[1, 2, 3]].

Warning: A Prolog system with logical update semantics
might be unefficient during repeatedly retract/1.