I have a prolog definition that returns multiple answers. I would like instead of this, to return a single list containing all possible answers.
E.g.
alpha;
beta;
gamma;
delta;
to
[alpha, beta, gamma, delta];
How can this be done in prolog?
-
What's the definition look like?geekosaur– geekosaur2012-04-27 08:22:02 +00:00Commented Apr 27, 2012 at 8:22
Add a comment
|
2 Answers
Note that depending on your specific need, findall/3 might not be a fit:
Consider the predicate test/2 : test(+L, -E) that unifies E with members of L that are free variables:
test(L, E) :-
member(E, L),
var(E).
Now, let's say you want to find all the free variables of a list by using this predicate (note: if you really wanna do that, that's not the right way, it's just to point out a findall/3 behaviour):
?- findall(X, test([A, 3, C], X), Xs).
Xs = [_G32, _G29].
findall/3 answers you with a good answer, but modulus a variable renaming!
?- bagof(X, test([A, 3, C], X), Xs).
Xs = [A, C].
or
?- setof(X, test([A, 3, C], X), Xs).
Xs = [A, C].
do the trick though.
I'm not sure whether what I said here applies to other Prolog systems than SWI-Prolog.
Here is the corresponding doc page.
By using findall. You have somepred(X) which gives you the answers as you specified. Now try and run findall(X,somepred(X),List) to see List unified with a list of all answers.
edit: Using setof or bagof instead of findall is wrong in the context of the question, as asked.
setof is obviously wrong as it skips valid solutions that happen to be duplicates. bagof fails when there are no solutions, whilst findall correctly "returns" an empty list [] (as requested by the OP). Oh, and both bagof and setof backtrack on alternative bindings for free variables, whereas the OP clearly asked for one list of solutions to be "returned", i.e. no backtracking. To wit:
?- [user].
|: test(L,E):- member(E,L),var(E).
|:
% user://2 compiled 0.00 sec, 124 bytes
Yes
?- findall(X, (test([A,3,A],X) , member(A,[1,2]) ) , Xs).
X = _G546
A = _G536
Xs = [1, 2, 1, 2] ;
No
?- bagof(X, (test([A,3,A],X) , member(A,[1,2]) ) , Xs).
X = _G534
A = 1
Xs = [1, 1] ;
X = _G534
A = 2
Xs = [2, 2] ;
No
?-
but the OP asked for "single list containing all possible answers" to be returned.
edit: A list of all answers when there are no answers is an empty list.
4 Comments
noted
Oh yeah, almost forgot about findall(). Thank you very much
m09
regarding @WillNess edit, it must be precised that bagof and setof have a control mechanism (
^) not to backtrack if needed, and that as precise semantics weren't given in the OP, the "wrong claims" are not properly argumented regarding the fail on no solution.
Will Ness
@Mog well I just assumed that when "one list containing all possible solutions" is wanted, the empty list naturally represents the list of no solutions.
Will Ness
@Mog you mean it is natural to expect of a list-returning computation to fail instead of returning an empty list? Usually we get a list of results, then we inspect whether it's empty or not. That's how lists are usually used, I thought.