Set bug?
Mark Engelberg
(= a 123) ; this prints true
(= (hash a) (hash 123)) ; this also prints true
So how come (count #{a 123}) prints 2 ?
I'm aware that a and 123 have different types, but I was under the
impression that the hash set implementation was supposed to just rely
on hash codes and equality. Why does the type come into play, and is
this really the desired behavior?
If this is the way it's supposed to work, then I'll probably add a
"normalize" function to the math library which reduces an integer down
to the correct Clojure type to avoid these sorts of problems when
interoperating with other libraries and using results from other
libraries in sets and maps.
Konrad Hinsen
> I'm aware that a and 123 have different types, but I was under the
> impression that the hash set implementation was supposed to just rely
> on hash codes and equality. Why does the type come into play, and is
> this really the desired behavior?
It looks like a bug to me, for the reasons you mention.
BTW, hash sets are implemented in terms of hash maps, which show the
same behaviour:
(def a (BigInteger. "123"))
({a :found} 123)
returns nil.
Looking at the implementation of PersistentHashMap, I note that the
ultimate key equality test is (line 560):
public LeafNode find(int hash, Object key){
if(hash == this.hash && Util.equals(key, this.key))
return this;
return null;
}
The test applied is Util.equals, so let's try that:
(. clojure.lang.Util equals a 123)
This returns false, unlike
(. clojure.lang.Util equiv a 123)
which returns true. clojure.core/= calls equiv, which is why (= a
123) is true. equiv is the same as equals EXCEPT for numbers and
Clojure collections, so perhaps sets and maps also have some surprise
behaviour for collections.
I don't know if there is a good reason for using equals rather than
equiv in testing for key equality in maps. Using equiv would better
agree with my expectations.
Konrad.
Rich Hickey
Well, the community simply has to get together on what they want here,
variously:
- Clojure sets and maps should implement java.util.Set and Map
- Clojure Numbers are the same Integer/Float/Long/Double as Java's,
and math works with Java's Numbers.
- (= 1 1.0) -> true
This latter 'feature' is a bear to maintain, as (.equals 1 1.0) -> false
In order to satisfy the requirements of Set and Map, hash sets and
maps must compare their keys using .equals, otherwise:
(= (hash-set 1 2.0 3) (java.util.HashSet. [1 2 3])) -> true
(= (java.util.HashSet. [1 2 3]) (hash-set 1 2.0 3)) ->false
I don't own the Integer/Long/Float/Double types, and can't broaden
their notion of equality - the type test is built in.
It would be a lot easier and more consistent if (= 1 1.0) -> false,
but that also implies (= 1 (long 1)) -> false, and people complained
when that was the case. clojure.lang.Numbers should be pretty good
about reducing during math ops, but you still can get Long 1 from a
Java source.
If people were willing to accept type-matching = for numbers, all the
special casing for Numbers and collections would go away.
So, the compromise is that hash map/set keys must be of a consistent
type for any particular value.
Rich
Konrad Hinsen
> Well, the community simply has to get together on what they want here,
> variously:
>
> - Clojure sets and maps should implement java.util.Set and Map
Not something I care much about, though I understand those who do.
> - Clojure Numbers are the same Integer/Float/Long/Double as Java's,
> and math works with Java's Numbers.
That looks much more fundamental for Clojure/Java interop, but on the
other hand Java's number model is hardly the one of my dreams.
> - (= 1 1.0) -> true
>
> This latter 'feature' is a bear to maintain, as (.equals 1 1.0) ->
> false
OK, I see now why there is equiv in addition to equals. What a mess...
> It would be a lot easier and more consistent if (= 1 1.0) -> false,
> but that also implies (= 1 (long 1)) -> false, and people complained
> when that was the case. clojure.lang.Numbers should be pretty good
> about reducing during math ops, but you still can get Long 1 from a
> Java source.
Is there a function that converts any Java number to a canonical
Clojure representation? With such a function at the Java->Clojure
interface, the current state would probably be quite bearable, even
though Java numbers could still sneak in and cause unexpected behaviour.
> If people were willing to accept type-matching = for numbers, all the
> special casing for Numbers and collections would go away.
I don't like that idea. The fundamental abstraction for me is
"number", not "integer" or "float" which are merely convenient
representations for certain subsets of numbers.
Konrad.
Mark Engelberg
I don't expect 1 to equal 1.0 (because I think of inexact numbers as
fundamentally different from exact numbers). I think of 1.0 as a
"number that's so close to 1 that we can't tell the difference, but it
still might not be 1".
I do expect 1 to equal 1/1, and I expect a long 1 to equal an int 1 to
equal a BigInteger 1. I think of these as all different ways of
writing or storing the same number.
I also expect 1 to equal 1.0M (which currently it does not) since 1.0M
is also an exact representation of the same number. But it's a
sufficiently different representation, it doesn't bother me as much to
have these treated as not-equal.
A fix that would feel consistent to me:
Drop equality of 1 and 1.0. Alter hash-map and hash-set to special
case on assoc,dissoc,getting Longs and BigIntegers to always
clojure.lang.Numbers/reduce these keys before storing and/or comparing
in the hash table. So only reduced integers will ever be stored as
keys, and different representations of the same value will behave as
expected.
I don't know whether this fix would be worth the performance penalty,
though, but it's what would "feel right" to me.
Mark Engelberg
<mark.en...@gmail.com> wrote:
> I don't know whether this fix would be worth the performance penalty,
> though, but it's what would "feel right" to me.
>
If it's not practical to always reduce integers when used as keys,
then I think it would be useful for a variation of
clojure.lang.Numbers/reduce to be exposed as a common function in the
API so that users can easily do their own reduction upon interop with
Java, before storing in a hash-map or hash-set. Note that
clojure.lang.Numbers/reduce does not accept a regular Integer as an
input, so the API version should also cover that case, and just return
the same Integer. I'm thinking num-reduce might be a good name.
Maybe num-reduce could also convert float to double (doubles are what
Clojure uses internally, right?). So basically, it would guarantee
that your number is converted into Clojure's standard representation
for that kind of thing so that it can be compared/hashed/etc. with
Clojure's numeric computation results with no surprises.
If something like this is not put in the API, I can add something like
this to clojure.contrib.math, but it seems like it would be a
generally valuable tool for numeric interop, and thus worthy of
inclusion in the core.
Rich Hickey
want to always use, e.g. Longs as keys.
Rich
Rich Hickey
On Mar 30, 2:54 pm, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> On Mon, Mar 30, 2009 at 10:45 AM, Mark Engelberg
>
contrib.math will end up in core soon.
Towards that end, I wonder if someone would do some analysis of the
costs of contrib.math using multimethods vs e.g. the dispatching
techniques of clojure.lang.Numbers for some of the operations. Are
there places where the multimethod dispatch dominates the math? IMO
math ops are not necessarily the best place for the elegance of
multimethods, but, depending on the op, it might not matter.
Rich