#19016: Better hash for Element
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_work
Type: | Milestone: sage-6.9
defect | Resolution:
Priority: | Merged in:
blocker | Reviewers:
Component: misc | Work issues:
Keywords: | Commit:
Authors: | 754dc5794a1a7004c8844cf7cfb64220957c36a5
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/19016 |
Dependencies: |
-------------------------+-------------------------------------------------
Old description:
> As reported on sage-devel [1], both `Element` and `CategoryObject`
> implement their hash based on their string representation. This causes a
> lot of troubles
>
> - it breaks the {{{equality => same hash}}} assumption for finitely
> presented groups
> {{{
> sage: G = groups.presentation.Cyclic(4)
> sage: G.cayley_graph().vertices()
> [1, a, a^2, a^-2, a^3, a^-1]
> }}}
> and symbolic expressions
> {{{
> sage: f=sin(x)^2
> sage: g=1-cos(x)^2
> sage: bool(f == g)
> True
> sage: hash(f) == hash(g)
> False
> }}}
> and possibly many others
>
> - it is highly incompatible with the `rename` feature (see also #8119)
> {{{
> sage: from sage.structure.element import Element
> sage: class E(Element):
> ....: def __init__(self):
> ....: Element.__init__(self, Parent())
> sage: e = E()
> sage: hash(e)
> -4965357552728411610
> sage: e.rename('hey')
> sage: hash(e)
> -6429308858210906323
> }}}
> and similarly, hashing should not be available on any mutable object.
>
> - it might be very bad for performance: see #18215 and #18239 for
> examples
>
> There are several possibilities that are currently being discussed:
> - make it return `0` by default (original proposition of the ticket)
> - make it raise a `TypeError` by default (as it the case for
> `SageObject`, see #18246)
> - let it as it is but raise a Warning
>
> [1] https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/discussion
New description:
As reported on sage-devel [1], both `Element` implement their hash based
on their string representation. This causes a lot of troubles
- it breaks the {{{equality => same hash}}} assumption for finitely
presented groups
{{{
sage: G = groups.presentation.Cyclic(4)
sage: G.cayley_graph().vertices()
[1, a, a^2, a^-2, a^3, a^-1]
}}}
and symbolic expressions
{{{
sage: f=sin(x)^2
sage: g=1-cos(x)^2
sage: bool(f == g)
True
sage: hash(f) == hash(g)
False
}}}
and possibly many others
- it is highly incompatible with the `rename` feature (see also #8119)
{{{
sage: from sage.structure.element import Element
sage: class E(Element):
....: def __init__(self):
....: Element.__init__(self, Parent())
sage: e = E()
sage: hash(e)
-4965357552728411610
sage: e.rename('hey')
sage: hash(e)
-6429308858210906323
}}}
and similarly, hashing should not be available on any mutable object.
- it might be very bad for performance: see #18215 and #18239 for examples
There are several possibilities that are currently being discussed:
- make it return `0` by default (original proposition of the ticket)
- make it raise a `TypeError` by default (as it the case for `SageObject`,
see #18246)
- let it as it is but raise a Warning
[1] https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/discussion
--
Comment (by vdelecroix):
Arghhh... there are two category tests which ask explicitely for
`parent.one()` and `parent.zero()` to return hashable elements! These are
- `Magmas.Unital.ParentMethods._test_one`
- `AdditiveMagmas.AdditiveUnital.ParentMethods._test_zero`
(I do think that those tests are good because most of the time the result
is cached)
In other words, any (additive or multiplicative) magma element should be
immutable or adopt an mutable/immutable framework... might be a lot of
work to fix!
Concerning `Parent` and `CategoryObject` from which it inherits I do not
think it is a good idea to touch it for now. Most of the time we expect a
`Parent` to be immutable.
--
Ticket URL: <http://trac.sagemath.org/ticket/19016#comment:35>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
