Alternative to findall

Question

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.

Perhaps using `assertz` instead of `assert` will solve this mysterious inconsistency. — Eugene Sh., Mar 23 '15 at 19:30
@EugeneSh. I believe `assert` and `assertz` do the same thing. :) — lurker, Mar 23 '15 at 19:41
@lurker Will assert guarantee appending to the end? I can't find anything mentioning it.. — Eugene Sh., Mar 23 '15 at 19:45
@EugeneSh. If it's SWI Prolog, then I *believe* it does since [`assert/1` is deprecated in favor of `assertz/1`](http://www.swi-prolog.org/pldoc/man?predicate=assert/1). I don't know why it would not be consistent. I'm still waiting for the OP to explain what is inconsistent. :) — lurker, Mar 23 '15 at 19:47

false · Answer 1 · 2022-08-19T14:02:27.670

There are several problems with your implementation.

There is no cleanup in the beginning. Add retractall(temp(_)) prior to T,
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.
```
You may want to change the order, either by using asserta/1 or by redefining obtain/2.
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.
For the fine print of assert/1 vs. assertz/1 see this answer.

score 0 · Answer 2 · 2020-11-08T21:10:54.623

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.

Alternative to findall

2 Answers2