Hi,
I'm looking for a way to compare instances of a class I created for
equality. I can write my own function to do this. But basically I'm
trying to figure out:
1. If there's any generic function that I can specialize.
2. How do I use instances of class foo as keys in a hash table?
Thanks,
Vishwas
On 11 Jul., 16:00, Vishwas Narendra <················@gmail.com>
wrote:
> Hi,
>
> I'm looking for a way to compare instances of a class I created for
> equality. I can write my own function to do this. But basically I'm
> trying to figure out:
>
> 1. If there's any generic function that I can specialize.
> 2. How do I use instances of class foo as keys in a hash table?
To 1:
There is no standard generic function to compare objects or to
generate hash-values from them.
To 2:
a) You can use an EQ HASH-TABLE using (make-hash-table :test 'eq). The
test and hash functions using this method are identity based.
Depending on the implementation it could be that such a hash-table
will need to get rehashed on every garbage-collection since that could
move objects around (change addresses). An implementor could probably
workaround this by including a counter in the header information of
boxed objects and using that counter as hash-value instead of the
address. Though I don't know if something like this is done in any of
the common CL systems.
b) Use implementation-dependent user-defined hash-tables. In LispWorks
you can create hash-tables with arbitrary hash-functions and test-
functions using the keyword-attributes :test and :hash-function of
LispWork's MAKE-HASH-TABLE.
c) Wrap it up yourself. Either use SXHASH (ANSI CL) or include your
own hash-value slot into your classes and use the value of this slot
to register or unregister an instance with the hash-table. One would
then use an EQL HASH-TABLE to hash the instances based on the integer-
keys.
ciao,
Jochen
On Jul 11, 9:10 pm, ·····@codeartist.org" <····@codeartist.org> wrote:
> c) Wrap it up yourself. Either use SXHASH (ANSI CL) or include your
> own hash-value slot into your classes and use the value of this slot
> to register or unregister an instance with the hash-table. One would
> then use an EQL HASH-TABLE to hash the instances based on the integer-
> keys.
Thanks for the response. I think this option (c) suits me best since I
want to create a hash table based on object equality (as defined by a
custom equality function) and I don't have access to Lispworks.
However, it looks like I'll have to do a bit more to handle hash
collisions. But I can live with that.
Vishwas
Vishwas Narendra <················@gmail.com> writes:
> This is what I ended up creating:
>
> (defgeneric get-hash-value (obj))
> (defgeneric object-equal (x y))
>
> (defmethod get-hash-value ((obj t))
> (sxhash obj))
>
> (defmethod object-equal ((x t) (y t))
> (eql x y))
>
> (defun register-hash-entry (hashtable key value)
> (if (lookup-hash-entry hashtable key)
> ; How do I avoid the following ugliness?
> (setf (cdr (find-if #'(lambda (x) (object-equal (car x) key))
> (gethash (get-hash-value key) hashtable))) value)
> (push (cons key value) (gethash (get-hash-value key)
> hashtable))))
>
> (defun lookup-hash-entry (hashtable key)
> (cdr (find-if #'(lambda (x) (object-equal (car x) key))
> (gethash (get-hash-value key) hashtable))))
>
> ; Test to see if it works
> (defclass foo ()
> ((bar :initarg :bar :accessor bar)))
> (defmethod get-hash-value ((obj foo))
> (sxhash (slot-value obj 'bar)))
> (defmethod object-equal ((x foo) (y foo))
> (equal (slot-value x 'bar) (slot-value y 'bar)))
>
> (setq *a* (make-hash-table))
> (register-hash-entry *a* (make-instance 'foo :bar "a") "b")
> (lookup-hash-entry *a* (make-instance 'foo :bar "a"))
> (register-hash-entry *a* (make-instance 'foo :bar "a") "c")
> (register-hash-entry *a* (make-instance 'foo :bar "b") "x")
> (lookup-hash-entry *a* (make-instance 'foo :bar "a"))
> (lookup-hash-entry *a* (make-instance 'foo :bar "b"))
>
>
> Any comments on style and any suggestions for improvement would be
> greatly appreciated.
This code suggest that you don't know if your problem domain has any
equivalence relationship. IMO, either you need to work more on the
analysis, or you don't need this code.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jul 12, 4:10 am, Pascal Bourguignon <····@informatimago.com> wrote:
> This code suggest that you don't know if your problem domain has any
> equivalence relationship. IMO, either you need to work more on the
> analysis, or you don't need this code.
Well, I was trying to mimic the functionality of Java's HashMap so
that I could define object equivalence relationships later. But, your
point is taken - this is really more complicated than necessary.
Vishwas Narendra <················@gmail.com> writes:
> I'm looking for a way to compare instances of a class I created for
> equality. I can write my own function to do this. But basically I'm
> trying to figure out:
>
> 1. If there's any generic function that I can specialize.
Step 1: go read http://www.nhplace.com/kent/PS/EQUAL.html
No, none of the standard equality operators (EQ, EQL, EQUAL, EQUALP,
CHAR-EQUAL, STRING-EQUAL, TREE-EQUAL, =, CHAR=, STRING=, and related
inequalities) is a generic function.
You will have to define your own generic function, if you want it to
be generic: (defgeneric my-object-equal-p (a b)
(:documentation "Go to step 1, then fill this docstring..."))
> 2. How do I use instances of class foo as keys in a hash table?
(gethash (make-instance 'foo) table)
Now, you can make portably hash-tables only using either EQL, EQUAL or
EQUALP to compare keys. Go to step 1. Some implementations have ways
to define hash-tables using other equality functions, but I'm not sure
I'd advise to use that...
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
> Step 1: go readhttp://www.nhplace.com/kent/PS/EQUAL.html
Thanks. I will take a look.
> Now, you can make portably hash-tables only using either EQL, EQUAL or
> EQUALP to compare keys. Go to step 1. Some implementations have ways
> to define hash-tables using other equality functions, but I'm not sure
> I'd advise to use that...
>
Out of curiosity, what would you advise instead?
Vishwas Narendra <················@gmail.com> writes:
>> Step 1: go readhttp://www.nhplace.com/kent/PS/EQUAL.html
>
> Thanks. I will take a look.
>
>> Now, you can make portably hash-tables only using either EQL, EQUAL or
>> EQUALP to compare keys. Go to step 1. Some implementations have ways
>> to define hash-tables using other equality functions, but I'm not sure
>> I'd advise to use that...
>>
>
> Out of curiosity, what would you advise instead?
The point is for you to defined object equality. This is the main problem.
For CLOS objects, Common Lisp provides EQL which gives the object
identity (for CLOS objects, EQ, EQL, EQUAL and EQUALP are equivalent).
So when you want to use CLOS object as keys in a hash-table, all
standard :TEST parameters are equivalent.
If you can _define_ another equivalence relationship on your CLOS
objects, then you can implement it, either as a function or a generic
function. This detail doesn't matter much. Only perhaps you'll
rather use a generic function if you cannot define equivalence
relationship once for all objects, if it depends on the new classes
you may create.
Technically, since the symbol CL:EQ, CL:EQL, CL:EQUAL and CL:EQUALP
are bound to functions, you cannot use them and bind them to a generic
function of yours. So you'll have to use a different symbol, possibly
named differently. Note how Common Lisp provides CHAR-EQUAL,
STRING-EQUAL, etc, this could give you some inspiration.
So my advice would be to determine if a specific equivalence
relationship exists in your problem domain, if so, to define it
precisely, and then to implement it. Otherwise, object identity
should be enough.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jul 11, 7:00 am, Vishwas Narendra <················@gmail.com>
wrote:
> 2. How do I use instances of class foo as keys in a hash table?
Since you can't use arbitrary equality functions for hashing, what you
can do is write a function which reduces your object to a key. The key
is an ordinary data type---string, number, or list thereof, etc.
Keys have the property that if they are equal under some conventional
equality (like, say, EQUAL), then the corresponding original objects
are considered equal under your own equality function. Otherwise the
original objects are not equal. You can then use these keys to insert
objects into the hash table.
Of course, it will help if you wrap GETHASH, etc, with your own
functions which automatically extract the keys from objects.
A concrete example of this would be as follows. Suppose you have an
object which contains two strings and a number: last name, first name
and student number. Suppose that in your custom equality function, you
want to compare these objects as if they were simple lists (STRING
STRING INTEGER) being treated by EQUAL. In that case, you can just
write a method which reduces an object to exactly such a list, and
then just use an EQUAL hash table to store the objects, using these
lists as keys. (The list doesn't have to be consed every time; it
should be possible to produce it lazily and cache it with its
respective object).
Thus if you can express your equality as some kind of data
transformation followed by the application of EQ, EQL, EQUAL or
EQUALP, then you can do hashes.
On Jul 11, 7:00 am, Vishwas Narendra <················@gmail.com>
wrote:
> Hi,
>
> I'm looking for a way to compare instances of a class I created for
> equality. I can write my own function to do this. But basically I'm
> trying to figure out:
>
> 1. If there's any generic function that I can specialize.
> 2. How do I use instances of class foo as keys in a hash table?
You might find my FSet functional collections library of interest:
http://common-lisp.net/project/fset/
http://www.sympoiesis.com/FSet/
It will let you use your own objects as map keys.
-- Scott
On Jul 12, 11:53 am, Scott Burson <········@gmail.com> wrote:
> You might find my FSet functional collections library of interest:
>
> http://common-lisp.net/project/fset/
> http://www.sympoiesis.com/FSet/
>
> It will let you use your own objects as map keys.
Thanks. This looks interesting. I will take a look.
Vishwas