Re: equivalence class implementation

Firstly, we will have to do it dynamically since I can not precompute the mapping in advance and then it goes back to the first question I asked is how to represent those equivalence class and manipulate the equivalent predicates at run time.


Let's use this person example and assume what you pointed out is not important.
equal(A,B):- person(A), personName(A,Name), person(B), personName(B,Name).


then we would have to say if A == B and A == C then B ==  C once the number of facts increases it will easily clutter my knowledgebase so instead what I want to do is to use lists to represent those equivalent persons such as creating a new list if the person is not equal to anyone existed or putting him into one of the list that I already created if it happens to equal to one of the person in this list, then I can say if two persons in the same list it will be considered as equal. Then the question is how do I define those lists at run time?


Hope this set up is clear.


thanks a lot 


Bao


------------------ Original ------------------
From:  "Richard A. O'Keefe"<[email protected]>;
Date:  Fri, Aug 9, 2013 02:27 PM
To:  "keowang"<[email protected]>; 
Cc:  "swi-prolog"<[email protected]>; 
Subject:  Re: [SWIPL] 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.
-------------- next part --------------
HTML attachment scrubbed and removed