hashCode for polynomial does not work

[rklaehn]

scala> Polynomial("(1)").##
res1: Int = -135076863

scala> Polynomial("(1)").##
res2: Int = 776699639

scala> Polynomial("(1)").##
res3: Int = 797295762

scala> Polynomial("(1)").##
res4: Int = 639834089

Both PolyDense and PolySparse use arrays internally. So the hashCode method generated for case classes is not sufficient. Also, hashCode would have to be implemented in such a way that both PolyDense and PolySparse representations of the same polynomial return the same hash code.

At the very least, hashCode needs to be implemented to be 0 to fulfill the equals/hashCode contract.

[pleira]

Just to provide some insights, I have found this thread in Scala-User about case classes and hashcode involving arrays. The workaround suggested by Jason Zaugg is to use scala.collection.mutable.WrappedArray, which offers access to the raw array but provides structural equality. For PolySparse, the exponentials, the exp first parameter, would be a WrappedArray[Int]. For the coefficients, I do not know how to create the appropriate WrappedArray[C] instances. I would leave that parameter untouched, just going only for the exponentials.

[non]

@pleira: Interesting, thanks!

I think for our case, we should come up with a hashing algorithm that just uses the coefficients and exponents, to easily ensure that sparse and dense hash do the same thing.

We should also ensure that "constant" polynomials hash to the constant coefficient's hash code.

[rklaehn]

@pleira I think using wrapped arrays would be inefficient, because they are another level of indirection. And as @non mentioned, we will need to implement hashCode for PolyDense and PolySparse anyway.

Why do constant polynomials have to have the same hashCode as the scalars? Is there cooperative equality between constant polynomials and scalars?

[non]

Currently there is (again to support things like == 0). We could choose not to support that, but it's not a lot of work (IMO at least) so I will probably try to do it.

[rklaehn]

I am not sure if this is even possible. At least PolyDense does not have a typeclass instance that could be used to get the value for Polynomial.zero.hashCode, and the zero polynomial is encoded as a polynomial with zero exponents and coefficients, so we don't have a value to call hashCode on...

At the very least, the representation of Polynomial.zero would have to be changed to have a constant value of the zero element. On the plus side, this would also solve #409

[tixxit]

@rklaehn yeah, we'd have to go the other way and "ignore" 0s in dense polynomials. Doing this is pretty sketchy, since it'll only work for numbers that support "cooperative equality", but we do it with Complex...

[tixxit]

This points to the more annoying problem of having universal equality + hashCode baked in to start :\

[non]

So I have gone ahead and made a best effort to support universal equality and hashCode as they would need to be done to be consistent. Definitely let me know what you think.

[rklaehn]

Exactly. Having equals and hashCode always drives you to an object oriented style, which in this case would mean capturing the type classes on creation (or at least something that lets you find out if something is zero).

[non]

As @rklaehn implies this approach is somewhat unprincipled. Alternate approaches that I see are:

1. Capture Eq and Semiring at construction time for all polynomials.
2. Hack PolyDense to track zero-ness explicitly (maybe via a bitset or something -- quite fiddly).
3. Give up on universal equality / hash code working consistently
4. Simplify or redesign polynomial (e.g. remove dense polynomials to allow structural comparisons of remaining sparse polynomials)

[rklaehn]

1. Wouldn't it be enough to capture Semiring? All we need is a way to figure out if things are zero.
2. Yuck!
3. I think even if you give up on universal equality / hash code you still need a way to figure out if something is zero
4. Then you would have to make sure that sparse polynomials never contain zero coefficients. Is that the case?

[non]

Yes, you are right that (1) only requires a Semiring. And also that (4) is not sufficient. I feel like the PR we have in now might be the best option, but I'm definitely interested in your opinions.

[rklaehn]

I think the PR is a good compromise for now. It just seems imprecise to use == 0 to check if something is zero. But if somebody is using Eq, everything will work fine. And if you want to use equals/hashCode you must make sure that your T has zero.hashCode == 0 and zero == 0.

[non]

Great. Well, if @tixxit signs-off then I will merge this. We definitely need to fix this for 0.9.2.