Path: utzoo!mnetor!uunet!lll-winken!lll-tis!mordor!sri-spam!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Programming Quickie
Message-ID: <839@cresswell.quintus.UUCP>
Date: 31 Mar 88 04:03:39 GMT
References: <1600011@otter.hple.hp.com> <2644@mulga.oz>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 63

In article <2644@mulga.oz>, lee@mulga.oz (Lee Naish) writes:
: In article <1600011@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes:
: >	exactly_one( +X, ?Y )
: >	is true if X contains Y,  Y satisfies p/1 and all of the other
: >	Y' contained by X satisfy q/1.
: 
: 	% NU-Prolog solution (will generate X or Y or both)
: exactly_one(X, Y) :-
: 	setof(Y0, X contains Y0, YList),	% <edited>
: 	select(Y, YList, Remainder),		% <edited>
: 	p(Y),
: 	forall(member(Y1, Remainder), q(Y1)).	% <edited>

{Note: I have edited some of the lines not to "improve" the code but
 to make it easier for people such as myself who haven't got a copy
 of NU Prolog to try this solution.  This version _behaves_ like Lee
 Naish's original, but his code has claims to being logic.
}
This is much prettier than my solution, but it doesn't do quite the same
thing.  Recall that the original posting said that p/1 and q/1 were to
be thought of as very expensive, so the goal is to minimize the number
of calls to p/1 and q/1.

My code, as you will recall, as

	exactly_one(X, Y) :-
		setof(Z, contains(X,Z), Zs),
		first_non_q(Zs, RestZs),
		p_and_qs(RestZs, Y, Zs).

	first_non_q([Z|Zs], RestZs) :-	| first_non_q([], []).
		q(Z),			| first_non_q([Z|Zs], U) :-
		!,			|     if q(Z) then
		first_non_q(Zs, RestZs).|	  first_non_q(Zs, U)
	first_non_q(RestZs, RestZs).	|     else U = [Z|Zs].

	p_and_qs([Y|Qs], Y, _) :-	| p_and_qs([Y|Qs], Y, _) :-
		p(Y),			|     p(Y),
		first_non_q(Qs, []).    |     all Q member(Q,Qs) => q(Q).
	p_and_qs([], Y, Zs) :-		| p_and_qs([], Y, Zs) :-
		member(Y, Zs),		|     member(Y, Zs),
		p(Y).			|     p(Y).

As the right column shows (if I've got it right), a pure version is possible.
The algorithms are different.  It is interesting to see how often they call
p/1 and q/1 in various cases.  I assume that all solutions of exactly_one/2
are being found by backtracking.

p OK	q OK	p LN	q LN		situation
----	----	----	----		----------------
N	N	N	N*(N-1)		p(Y),q(Y) true for all Y

1	N	N	N-1		p(Y<I>), q(Y) for all Y but Y<I>

1	2	N	N		~q(Y<1>), ~q(Y<2>)

1	N	N	N*(N-2)+2	q(Y) for all Y but Y<N-1>,Y<N-2>

If the caller commits to the first solution, Lee Naish's code will call
p/1 less often, and will call q/1 at most N-1 times, but in that context
my code will call q/1 N times and p/1 at most once.

Another illustration of the difference between specifications and programs,
alas.