Path: utzoo!utgpu!water!watmath!clyde!att-cb!att-ih!alberta!ubc-cs!voda
From: voda@ubc-cs (Paul Voda)
Newsgroups: comp.lang.prolog
Subject: Re: Programming Quickie
Message-ID: <1922@ubc-cs.UUCP>
Date: 1 Apr 88 07:16:33 GMT
References: <1600011@otter.hple.hp.com> <2644@mulga.oz> <839@cresswell.quintus.UUCP>
Sender: nobody@ubc-cs.UUCP
Reply-To: voda@ubc-cs.UUCP (Paul Voda)
Organization: UBC Department of Computer Science, Vancouver, B.C., Canada
Lines: 95

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.