Path: utzoo!mnetor!uunet!mcvax!ukc!warwick!expya!jtr
From: jtr@expya.UUCP (Jason Trenouth)
Newsgroups: comp.lang.prolog
Subject: reply to quickie
Message-ID: <427@expya.UUCP>
Date: 19 Apr 88 16:24:55 GMT
Expires: 30 May 88 23:00:00 GMT
Reply-To: jtr@expya.UUCP (Jason Trenouth)
Organization: Computer Science Dept. - University of Exeter. UK
Lines: 38

In reply to Ian Dickenson's posed "quickie":

        exactly_one(X, Y) :-
            contains(X, Y),
            p(Y),
            bagof(Y1,
                  (
                    contains(X, Y1),
                    \+(Y1 = Y),		% Assuming N unifications are better
                    q(Y1)		% than one call to "q".
                  ),
                  Ys).

The algorithm computes at worst:

	N calls to "p" (where N is the number of Ys "contain"ed in X); and

	N*(N-1) calls to "q".

By adding a lemma creation predicate (i.e. asserting) for "q" inside
the "bagof" call we could achieve linearity in full calls to "q".

[Anyone else?]

Chow.

	_______________________________________
	|                                     |
	| Jason Trenouth                      |
	|  Computer Science Department        |
	|   University of Exeter              |
	|    Devon EX4 4PT                    |
	|     United Kingdom                  |
	|                                     |
	| JANET:  jtr@uk.ac.exeter.cs         |
	| UUCP:   jtr@expya.uucp              |
	| BITNET: jtr%uk.ac.exeter.cs@ukacrl  |
	|_____________________________________|