PROLOG, Is it possible to collect all result from a predicate to a list, without using built in predicates, such as bagof or findall

Question

If for example, I have a Prolog predicate like a(A, B).

Is it possible to collect, given a value of A, is it possible to collect all values of B that succeeds the predicate a, into a list, without using built in predicates such as bagof/3 or findall/3.

Answer 1

You have two obvious options (obvious to me; it seems there is more). One is to indeed use the database to save the state. This has at least one pitfall: depending on the name you decide to use for the temporary state, you might destroy some other state your program is keeping. This is the same old "global state"/"global variable" problem that all languages suffer from.

The other option would be to use a "local variable" and non-backtracking assignment to it to keep the temporary state. This is most probably going to be implementation dependent. For starters, you can look at nb_setarg/3 for SWI-Prolog.

However, both solutions are silly, given that you have findall, bagof, setof. You must motivate the need for something else to replace those. Just saying "is it possible" is not good enough since it is possible, but completely unnecessary, unless you know something else that you aren't telling us.

Answer 2

Here's a sketch of a stupid setof that uses other builtins, though not assert, and not exactly the ones listed by @false in a comment.

We'll use a list accumulator to collect solutions:

stupid_setof(Template, Goal, Set) :-
    stupid_setof(Template, Goal, [], Set).

There are two cases to consider: Either the Goal can enumerate a solution we have not seen so far, or the only ones it can enumerate are already in our accumulator.

First, the case where there are no solutions we haven't seen. In this case we're done.

stupid_setof(Template, Goal, SolutionsSeen, Set) :-
    \+ (  call(Goal),
          \+ member(Template, SolutionsSeen) ),
    !,    
    sort(SolutionsSeen, Set).

Now for the stupid part. Consider:

foo(a).
foo(b).
foo(c).

?- SolutionsSeen = [], foo(X), \+ member(X, SolutionsSeen), !.
SolutionsSeen = [],
X = a.

?- SolutionsSeen = [a], foo(X), \+ member(X, SolutionsSeen), !.
SolutionsSeen = [a],
X = b.

?- SolutionsSeen = [a, b], foo(X), \+ member(X, SolutionsSeen), !.
SolutionsSeen = [a, b],
X = c.

?- SolutionsSeen = [a, b, c], foo(X), \+ member(X, SolutionsSeen), !.
false.

So given a list of solutions we've seen before, we can force Goal to backtrack until it gives us one that we haven't seen before. Note that these queries are independent: In each one we have a completely fresh copy of the foo(X) goal that starts enumerating from a.

We can do the same thing programmatically by copying the original goal before calling it, forcing it to start a fresh enumeration from a fresh instance of the Goal. If this finds a new solution, we can add it to our solutions, then repeat with another fresh copy of the goal, forcing it to enumerate yet another new solution, and so on:

stupid_setof(Template, Goal, SolutionsSeen, Set) :-
    copy_term(Goal-Template, GoalInstance-Solution),
    call(GoalInstance),
    \+ member(Solution, SolutionsSeen),
    !, 
    stupid_setof(Template, Goal, [Solution | SolutionsSeen], Set).

If Goal has N answers, this will enumerate on the order of N**2 of them and do corresponding linear searches in the solutions list. It will also perform any side effects that Goal has multiple times.

But it "works":

?- stupid_setof(X, foo(X), Xs).
Xs = [a, b, c].

And, despite all of its stupidity, this is still less stupid than the standard setof/3 if Goal has no solutions:

:- dynamic bar/1.  % no clauses

?- setof(X, bar(X), Set).
false.

?- stupid_setof(X, bar(X), Set).
Set = [].