Re: equivalence class implementation

On 9/08/2013, at 5:09 PM, baoru wrote:

> thanks for your reply, let's say predicate(a) is person(a) (could be anything really does not really matter),

Well, the question is what you _mean_ by something like 'person(a)'.
If it's supposed to be connected with a _predicate_ called person/1
we could be in for some trouble, but if it's just a ground term,
that's fine.

> your rule resorting to the representative predicates makes sense but I am not sure if I understand the point you brought up on doing this dynamically or statically?

The question is *when you know* stuff.
If you can figure out *in advance* what is equivalent to what,
you can precompute a fixed representative/2 mapping and use it
very quickly.

If you learn new "this is like that" facts *at run time*,
then you have to have something you can update, and you have
to have code inside your program at run time to do the updating.

Representing a dynamic equivalence relation as some kind of
term is a nice idea, especially if you want to have many equivalence
relations, if changes are very common, or you want to undo changes
on backtracking.  If you only want one, changes are rare, and you
don't want to undo changes, you could store it in the Prolog
clause database.  If you choose to do that,
you want to represent it as many clauses, not a single big one.

The classic Union/Find algorithm works in terms of a tree, where
each element in the domain of the equivalence relation is has an
associated node that points to a "parent" (but no reference to
"children") and has a count of its descendants (but again, no
references to the "children").  Translating the algorithm you
will find in a data structures and algorithms book into Prolog
should be straightforward.

> What's the drawback of doing it dynamically?

A basic rule about any programming language: the earlier you know
something, the more you can tell the compiler; the more you can
tell the compiler, the more it can do for you.  More space,
more time, and less safety is the quick answer here.

> Assuming the two person is equal if they have the same name as you asked me if I know what to count as equivalent.

That's an extremely dangerous assumption about real people.
When I was an undergraduate, I was once sent another student's
marks because we had the same name.  Fortunately we hadn't taken
any of the same papers, so it was instantly obvious.

I think we might need to see something closer to your actual problem.