On 10/07/2011 04:06 PM, Jamison Hope wrote:
I was a little surprised today to discover that
(equal? (byte[] 1 2) (byte[] 1 2))
returns #f. Obviously Java arrays are outside the scope of the
Scheme report, but it would seem to be in the spirit of equal?
for that to return true. Would it be worthwhile to write a patch
for IsEqual.java to defer to java.util.Arrays#equals() and
java.util.Arrays#deepEquals() in the case of arrays?
Well, it's reasonable but not correct. Using Arrays#equals is fine
for primitive array types, but not object arrays. The main problem
with Arrays#deepEqual is the "base case" is Object#equals, but for
us the base case should be IsEqual#apply. However, doing deepEqual
by hand is easy enough - just use the same logic as FVector.
The basic cycle-safe equal? implementation is as follows:
Maintain a mapping (Object,Object)->boolean for previously-seen calls.
(This mapping uses the System.identityHashCode on both operands.)
recursiveEquals(Object arg1, Object arg2, Map2 seen) {
if (arg1 == arg2)
return true;
if (arg1 == null || arg2 == null)
return false;
Boolean wasSeen = seen.lookup(arg1, arg2);
if (wasSeen != null)
return wasSeen.booleanValue();
seen.set(arg1, arg2, Boolean.TRUE); // protect against cycles
boolean r = coreEquals(arg1, arg2, seen);
seen.set(arg1, arg2, Boolean.valueOf(r));
return r;
}
One might try to be clever so the seen table is only allocated
if we recursing, in some way or other.
The Map2 data structure is somewhat unusual. One possibility is
to just use an
IdentityHashMap<Object,IdnetityHashMap<Object,Boolean>>.
A custom hash table has hash is calculated as
(System.identityHashCode(arg1) ^ System.identityHashCode(arg2))
could be more efficient.