With some restrictions/variations that may be crucial to a particular
situation, a "pure" Prolog equivalent to findall is possible, though
With a "goal" like:
the Prolog engine succeeds if L unifies with the list of different
values that A binds to on consecutive backtracking invocations on the
compound goal (p(A),q(A,B),s(B)).
Without side-effects it would be impossible to "remember" all of these
bindings as a consequence of a failure driven backtrack directly into
the given goal.
However we can mostly work around that restriction with a recursive
construction as outlined here:
Essentially the my_findall_pqs builds a list of the distinct values
for A that make the original goal (p(A),q(A,B),s(B)) succeed, calling
itself recursively with a successively longer list of "old" successes
recorded in L. When no new successes are possible, the predicate
succeeds by binding the last argument to the middle one.
To use this goal we would start it off with an empty list for the
second argument L, and a free variable M for the third argument:
Some objections are in order. First the list M here is returned in
opposite order to what would be produced by findall, a fairly
technical point that could be remedied by a call to a list reversing
predicate. Potentially more important is the absence of duplicate
entries in our version of M.
Second one might object to the use of not( ), as technically this is a
meta-predicate. However I used it for clarity above. The
not(member(A,L)) call can be replaced by a custom predicate:
Third one might object to the use of "cuts" ! as not pure Prolog.
Although this objection is not related to meta-predicates versus
regular predicates, of the two places where cuts are used, the
essential one is actually in the replacement my_not_member above
(which would eventually always succeed through backtracking without
the strategically placed cut). The use of ! in my_findall_pqs is
something of an efficiency matter, allowing for example the
optimization called tail-recursion elimination.
Continuing briefly with the issue of efficiency, the my_findall_pqs
predicate suffers from a quadratic-time overhead, even with
tail-recursion elimination, due to the necessity of revisiting the
sequence of possible bindings for A again and again.