restivo@POLYA.STANFORD.EDU.UUCP (06/30/88)
Date: Fri 17 Jun 1988 02:53-PST From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@POLYA.STANFORD.EDU> Reply-to: PROLOG@POLYA.STANFORD.EDU> US-Mail: P.O. Box 4584, Stanford CA 94305 Subject: PROLOG Digest V6 #35 To: PROLOG@POLYA.STANFORD.EDU PROLOG Digest Friday, 17 Jun 1988 Volume 6 : Issue 35 Today's Topics: Implementation - A Quickie ----------------------------------------------------------------------------------------------------------------------------- Date: 27 Mar 88 10:29:15 GMT From: quintus!ok@sun.com (Richard A. O'Keefe) Subject: Programming Quickie In article <1600011@otter.hple.hp.com>, ijd@otter.hple.hp.com (Ian Dickinson) writes: > Assume a relation "Y is contained in X", specified as: > contains( ?X, ?Y ). > Assume also, two global predicates p/1 and q/1. (As is always the case in > these problems, p and q are expensive to compute :-). > The problem is to define a predicate exactly_one/2: > 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. Let's start like this: exactly_one(X, Y) :- setof(Z, contains(X, Z), Zs), p_and_qs(Y, Zs). This much is straightforward. In the context of your actual problem, it may be easy to compute Zs directly. The tricky thing is p_and_qs. You do not say whether it is possible for p/1 and q/1 to be true of the same term. There are three cases: 1. there is exactly one element Z of Zs for which q(Z) is false and p(Z) is true of that Z. In this case Y=Z. 2. q(Z) is true of every element Z of Zs, and p(Z) is true of at least one such Z. This this case, Y is any of the Zs for which p(Y). 3. There is no solution for Y. In order to tell which of the first two cases we've got, we'll write a predicate to return the longest suffix of Zs whose head does not satisfy q/1, or the empty list if every element of Zs satisfies q/1. Then if we get a non-empty list, p must be true of the first element and q of all the rest. If we get an empty list, any member of Zs which satisfies p/1 will do. p_and_qs(Y, Zs) :- first_non_q(Zs, RestZs), p_and_qs(RestZs, Y, Zs). first_non_q([Z|Zs], RestZs) :- q(Z), !, first_non_q(Zs, RestZs). first_non_q(RestZs, RestZs). p_and_qs([Y|Qs], Y, _) :- p(Y), first_non_q(Qs, []). p_and_qs([], Y, Zs) :- member(Y, Zs), p(Y). This checks q(Z) once for each Z, and checks p(Y) either once or once for each Z unifying with Y. Without more information about p and q I don't think this can be reduced. I have tested this code. It can solve for X as well as Y. ------------------------------ Date: 28 Mar 88 13:03:51 GMT From: otter!sfk@hplabs.hp.com (Stephen Knight) Subject: Programming Quickie Here is my solution, which I submit for elegance points ... exactly_one( X, Y ) :- X contains Y, /* contains is infix in my version */ p( Y ), forall( ( X contains Y1, Y /= Y1 ), q( Y1 ) ). forall( X, Y ) :- not( (X, not(Y)) ). The inefficiency of this programs is the repeated calculation of q( Term ). One approach would be to patch this by making "q" cache, but other solutions on this problem are more efficient than that anyway. -- Steve Knight -------------------- Date: 30 Mar 88 07:51:50 GMT From: munnari!mulga!lee@uunet.uu.net (Lee Naish) Subject: Programming Quickie 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) :- solutions(Y0, X contains Y0, YList), % like setof delete(Y, YList, Remainder), p(Y), all Y1 member(Y1, Remainder) => q(Y1). % any formatting ideas? -- Lee ------------------------------ Date: 1 Apr 88 07:16:33 GMT From: pacbell!att-ih!alberta!ubc-cs!voda@AMES.ARC.NASA.GOV (Paul Voda) Subject: Programming Quickie In article <839@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) 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> > The code of Naish as edited by O'Keefe contains three list constructions/traversals: setof, forall, and select. One list operation is sufficient provided that your Prolog has a LOGICAL "all solutions" predicate ( i.e. the one looking for an ORDERED list with no repetitions of values satisfying a formula). Since I do not have such a Prolog and anyway I program mostly in Trilogy here is the solution in Trilogy: Aux = Some_notP1Q | P1_of(B) | Some_Q proc Exactly_one(x:<A, y:>B) iff all aux in listaux Contains(x,z) & if P1(z) then aux = P1_of(z) elsif Q(z) then aux = Some_Q else aux = Some_notP1Q end end & listaux = P1_of(y),w & ( w = Nil | w = Some_Q,Nil ) Assumptions: For simplicity sake (without compromising the generality of the solution) I assume the following about the predicates Contains, P, and Q. Actually I use P1 since P is a predefined identifier in Trilogy.: P1 and Q may hold for the same x. The declarations are as follows: pred Contains(x:<A,y:>B) {output B's are contained in input (given)A} proc P1(x:<B) {input x of type B satisfies P1} proc Q1(x:<B) {input x of type B satisfies Q} Explanation: 1) The all-solutions construct "all" constructs a sorted list without repetitions called listaux (of type "list Aux") containing only and all aux's (of type Aux) such that the formula Contains(x,z) .... w = Some_Q) holds for some "z". 2) The type Aux is a union type (corresponding to two atoms and one functor of Prolog). The ordering on Aux in Trilogy is automatically derived from the ordering of the domain U of Trilogy as follows: Some_notP1Q < P1_of(b1) < P1_of(b2) < Some_Q for all B's: b1 < b2. 3) The "all" solutions bactracks through the predicate Contains to obtain all z's contained in x. For each z a value aux is constructed according to whether P1, Q1 (and not P1), or not P1 not Q holds of z. 4) After the list listaux has been constructed the predicate Exactly_one succeeds iff i) listaux is non_empty, ii) listaux starts with a P1_of(y); i.e. P1(y) holds and there is no z contained in x such that not P1(z) and not Q(z). iii) listaux contains either one element, or if two then the second one is Some_Q, i.e. no other z contained in x satisfies P1. 5) The or (|) at the end of the predicate Exactly_one is compiled without a choice point, just as a boolean or in Pascal. ------------------------------ Date: 26 Mar 88 21:04:43 GMT From: maui!matthew@locus.ucla.edu (Matthew Merzbacher) Subject: Programming Quickie In article <1600011@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes: > >Here is the problem... > >Assume a relation "Y is contained in X", specified as: > contains( ?X, ?Y ). > >Assume also, two global predicates p/1 and q/1. (As is always the case in >these problems, p and q are expensive to compute :-). > >The problem is to define a predicate exactly_one/2: > > 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. > >Any offers? > Is this really supposed to be exactly_one? If so, then you want a restriction that none of the Y' satisfy p/1. Of course, you could just have a negation of p/1 as the first condition of q/1 to achieve this given the above definition. First, a little proof: Define CX as the cardinality (number of members) of X, CY as the cardinality of Y, and CY' as the cardinality of Y'. THM: If exactly_one succeeds, then q/1 will be executed AT LEAST CY' times and p/1 will be executed AT LEAST once. This is clear since you have to find the Y which will satisfy p/1 and you must also presumably check all the other Y' to make sure they satisfy q/1. Now, since CY' = CX - 1, and since we need to make CY' calls to q/1 we may make CX calls to q/1 without worrying too much more about efficiency (one extra call). Having made these calls, one of three possibilities will be true: 1. All q/1 will succeed 2. All but 1 q/1 will succeed 3. At least 2 q/1 will fail In the first case, we must go on to check each potential Y in X to find one that satisfies p/1. If there is only one, then this step will take (on average) CX/2 calls to p/1. The worst case is, of course CX, and the best case is 1 (first try). In case 2, as soon as q/1 fails, we should check to see if the offending Z satisfies p/1 if it does, then we have found Y and we must check the remaining Y' to determine if they satisfy q/1. If the offending Z does not satisfy p/1, then the algorithm fails, since we have found a Z in X which is neither Y nor in Y'. If Z satisfies p/1 and the check of the remaining unchecked member of Y' reveals a failure, then exactly_once fails. Thumbnail Analysis: 1. All q/1 will succeed -- Takes CX calls to q/1 + CX/CY (on average) calls to p/1 This is becuase all of X is checked for a candidate Y (calls to q/1). Finding none, each member of X must be checked until one satisfies p/1. Assuming the CY possible Y are evenly distributed over X, the second step will take CX/CY calls to p/1 2. All but 1 q/1 will succeed -- Takes CX calls to q/1 + 1 call to p/1 The CX calls are made since we must check all q/1 to find the only one which does not succeed. It must therefore be Y and satisfy p/1. If it does not satisfy p/1, then the algorithm takes only (on average) CX/2 calls to q/1 + 1 call to p/1. 3. At least 2 q/1 will fail -- Takes (on average) 2*CX/N+1 calls to q/1 + 1 call to p/1 -- (N is the number of members of X which fail q/1) Actually, it's better than this. We make calls to q/1 until failure occurs. When the failure occurs, if p/1 fails on that candidate, then we are done (in CX/N calls to q/1 + 1 call to p/1). On the other hand, if p/1 succeeds, then we must continue checking using q/1 until another failure. Notice that if N=1 then this degenerates to case #2. Thus, in the two cases where there is at least one Z in X which does not satisfy q/1, my algorithm makes the minimum number of calls. In the case where all X satisfy q/1, my algorithm must make CX/2 calls more than minimum. However, I maintain that this is unavoidable by any algorithm, though I can't seem to prove it. My Algorithm: % find_Z(+List, -Z, -Remainder) looks through the list of candidates and returns % the first Z which does not satisfy q/1. It also returns the remainder of the % list of candidates. If all candidates satisfy q/1, then find_Z fails. find_Z([],_,[]) :- !, fail. find_Z([Candidate|Rest], Z, Remainder) :- q(Candidate), find_Z(Rest,Z,Remainder). find_Z([Z|Remainder],Z,Remainder). % find_Y(+List,-Y) looks through the list (which is X originally) and finds a % member which satisfies p/1. If no member satisfies p/1 then find_Y fails. find_Y([],_) :- !, fail. find_Y([Candidate|Rest], Candidate) :- p(Candidate). find_Y([_|Rest], Y) :- find_Y(Rest, Y). % exactly_one(+X,-Y) uses find_Z/3 to check each member of X to find one that % does not satisfy q/1. If any Y of X do not satisfy q/1 then Y must satisfy % p/1 and all remaining X must satisfy q/1. If all X satisfy q/1 then at least % one Y of X must satisfy p/1 exactly_one(X, Y) :- find_Z(X, Y, Remainder), !, p(Y), not(find_Z(Remainder,_,[])). exactly_one(X, Y) :- find_Y(X, Y). -- Matthew Merzbacher ------------------------------ End of PROLOG Digest ********************