Path: utzoo!attcan!uunet!mailrus!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!ucsd!ucbvax!hplabs!hpfcso!hpldola!patch
From: patch@hpldola.HP.COM (Pat Chkoreff)
Newsgroups: comp.lang.prolog
Subject: Re: Duplicate Solutions
Message-ID: <11500024@hpldola.HP.COM>
Date: 22 Mar 90 19:01:14 GMT
References: <11500023@hpldola.HP.COM>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 58

Thank you for your responses, both here and by mail.

A number of responses suggested using a cut.  What I failed to specify in my
posting was that cuts, and red ones in particular, are undesirable.  Sharon
Correll's solution, which filters the square of the set of nodes, moves the
cut down into an auxiliary predicate so that it's green from the perspective
of the main predicate.  This is a natural solution, but it still has a cut,
and as Richard O'Keefe pointed out, it has performance problems in certain
call modes.

What's interesting about this problem is that duplicate solutions have no
LOGICAL consequence.  That is why I wondered aloud whether or not I should
care.  Most seem to think that I should, and I agree primarily for aesthetic
reasons.  To me, duplicate solutions are ugly and indicate potential logical
problems.

My solution required the use of bagof (or setof).  Ken Johnson's solution
required pre-grouping the class of edges between any pair of nodes.  Richard
O'Keefe's solution suggested using a distinguished representative of each
class of edges.

All three of these solutions involve the common notion of a partitioned set,
or a set of equivalence classes.  Therefore, the best solution is to
represent the concept of partitioned sets in a purely logical manner.  This
concept is extremely useful -- I'm using it for lots of different things in
my current work.  In a partitioned set, each "element" (e.g., edge) resides
in a single "class" (e.g., hyperedge between nodes), and each class contains
zero or more elements.  It is easy to constrain the classes to be nonempty,
which is appropriate for my directed acyclic graph example.

This scheme allows one to:

    1.  Determine the class to which an element belongs.

    2.  Recurse over the elements of a class.

All of this can be done without using cuts, leaving choice points, or
requiring the use of setof/3 and the like.  And if you don't mind using
assert and retract, it's possible to transfer the elements of a class to
another class in constant time.  To support such updates in pure logic, I
would have to use a structural representation instead of a relational one,
and that's farther than I'm willing to go.  This, by the way, is an
unpleasant dichotomy -- what's going on in higher-order logic programming
these days?

When you get right down to it, I'm using doubly-linked "lists" which are
represented using relations.  The use of dual links is NOT just an
implementation trick, however -- it is essential for expressing the
constraint that every element is in exactly one class.  Without dual links,
I would have to resort to setof/3 to express this constraint, and it would
be slow.  Once again, efficiency and pure logic demonstrate their affinity
for one another, as O'Keefe is so fond of noting (:-).

Enough talk.  When I get an example ready, I'll post it.


Patrick Chkoreff   719-590-5983
{hpfcla,hplabs}!hpldola!patch