CODEWITHSUNDEEP
prologprolog-findall
PablodeAcero
PablodeAcero

Reputation: 411

Alternative to findall

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.

Upvotes: 2

Views: 1015

Answers (2)

false
false

Reputation: 10102

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 = []
;  false.

  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.

Upvotes: 2

user502187
user502187

Reputation:

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.

Upvotes: 0

Related Questions