unique_soln/2

Appeared in Volume 7/1, February 1994

brahme@netcom.com
brahme
10th September 1993

I have a predicate that returns multiple solutions. When I backtract into it, it returns a new solution, which is often the same solution that was returned earlier. I would like it to only return new solutions, or, if there are no more solutions, to fail.

There are two ways to obtain this behaviour:
1. setof(E, Goal, List), member(Ans, List).

The problem is that this approach forces me to evaluate all the solutions at once. Thus it could result in a great increase in computation.

2. I can start asserting the solutions and when I backtrack match with previous solutions to ensure that only new answers are returned. I do not want to do this, since it is like rewritting setof/3 with all the problems with recursive calls, etc.

I want a new predicate called:
unique_soln(E, Goal).

Instead of writing goal(A, B, Ans), I will write:
unique_soln(Ans, goal(A, B, Ans))

and get a unique solution.

How easy is this to implement in existing Prologs? It should be fairly easy, since the level of difficulty is about the same as setof/3.

micha@ecrc.de
Micha Meier
13th September 1993

You can try the XSB Prolog system, it should be able to do what you want. However, you will not find this functionality in standard Prolog systems. One reason is that using setof/3 and member/2 has the same complexity (provided you compute all solutions). The other reason is that rejecting a solution only after computing it does not give you any increase in efficiency. If you don't want to spend your time computing old solutions, you have to change your algorithm so that they are not produced in the first place (I know, it is often not possible, but quite frequently it is).

paul@cs.keele.ac.uk
Paul Singleton
13th September 1993

I think that there are valid reasons for wanting the behaviour of unique_soln/2 other than for complexity reduction or efficiency gain (it's not clear to me that the original poster expects either of these anyway).

In an interactive program, it may be useful to deliver the first solution before computing the last. We may wish to generate distinct solutions from an infinite generator (and 'cut' at some point). I have implemented special cases of unique_soln/2 for such applications, but I realise that, as with setof/3, implementation of a general (re-entrant, free-variable-handling) version is fraught with pitfalls.

I suspect the "real" reason it isn't part of Prolog culture is that the obvious underlying data structure for checking for uniqueness on-the-fly (a heap) can't be implemented neatly/efficiently on top of the usual assertable/retractable database.

alberto@cs.umd.edu
Jose Alberto Fernandez R
13th September 1993

There are many implementations of delay mechanisms for Prolog. It would be interesting to see a delayed implementation of set_of/3 (without the order) that works lazily. Only when a new element of the list of solutions is accessed, is the new solution computed.

Perhaps, the demand for the list produced by set-of to be ordered is not such a good idea.