Opened 18 months ago

Closed 17 months ago

Last modified 17 months ago

#25586 closed enhancement (fixed)

py3: adding hash function for orders and fraction fields

Reported by: chapoton Owned by:
Priority: major Milestone: sage-8.3
Component: python3 Keywords: days94
Cc: tscrim, embray, jdemeyer Merged in:
Authors: Frédéric Chapoton Reviewers: Vincent Delecroix, Travis Scrimshaw, Erik Bray
Report Upstream: N/A Work issues:
Branch: 6806c37 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by chapoton)

+ a few other details

Change History (39)

comment:1 Changed 18 months ago by chapoton

  • Branch set to u/chapoton/25586
  • Commit set to a0f9b866f19dd5e3843cb4e11aac8e3a23be067e
  • Status changed from new to needs_review

New commits:

a0f9b86py3: adding hash to congruence groups and fraction fields + other details

comment:2 Changed 18 months ago by chapoton

  • Description modified (diff)
  • Summary changed from py3: adding some hash function to py3: adding hash function for congruence groups and fraction fields

comment:3 Changed 18 months ago by chapoton

  • Status changed from needs_review to needs_work

some failing doctests

comment:4 Changed 18 months ago by git

  • Commit changed from a0f9b866f19dd5e3843cb4e11aac8e3a23be067e to ac1563141fc541500802fefa24c07cfdd7c85557

Branch pushed to git repo; I updated commit sha1. New commits:

ac15631trac 25586 fixing new hash of congruence groups

comment:5 Changed 18 months ago by chapoton

  • Status changed from needs_work to needs_review

comment:6 Changed 18 months ago by vdelecroix

Similar to #25591: the hash of a fraction field should be different from the hash of its underlying ring.

What you did for congruence subgroups is not a very good idea as it will break equality

sage: G = Gamma(2)
sage: H = G.as_permutation_group()
sage: G == H
True

One (expensive) possibility for now would be

def __hash__(self):
    return hash(self.as_permutation_group())

comment:7 Changed 18 months ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

comment:8 Changed 18 months ago by git

  • Commit changed from ac1563141fc541500802fefa24c07cfdd7c85557 to a56f9735ea74cacadf2947165fb7a191f8345fca

Branch pushed to git repo; I updated commit sha1. New commits:

a56f973fixing hash of fraction fields and congruence groups

comment:9 Changed 18 months ago by chapoton

  • Status changed from needs_work to needs_review

Merci. C'est fait aussi.

comment:10 Changed 18 months ago by chapoton

ping ?

comment:11 Changed 18 months ago by vdelecroix

  • Status changed from needs_review to positive_review

désolé... d'autres sollicitations.

comment:12 Changed 18 months ago by chapoton

Je comprends. Merci beaucoup.

comment:13 Changed 18 months ago by vbraun

  • Status changed from positive_review to needs_work

See patchbot

comment:14 Changed 18 months ago by git

  • Commit changed from a56f9735ea74cacadf2947165fb7a191f8345fca to 97d8e09ab04a0c8551d7ba64540d910a1287ae60

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

97d8e09py3: adding hash to orders and fraction fields + other details

comment:15 Changed 18 months ago by chapoton

  • Status changed from needs_work to needs_review
  • Summary changed from py3: adding hash function for congruence groups and fraction fields to py3: adding hash function for orders and fraction fields

the case of congruence groups being harder, it is no longer handled here.

comment:16 Changed 18 months ago by chapoton

ping ? I have removed the controversial part..

EDIT: and this is an important ticket for progress in python3

Last edited 18 months ago by chapoton (previous) (diff)

comment:17 Changed 18 months ago by chapoton

and bot is green

comment:18 Changed 18 months ago by chapoton

  • Cc tscrim embray jdemeyer added

please, someone ?

comment:19 Changed 18 months ago by tscrim

  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:20 Changed 18 months ago by embray

  • Status changed from positive_review to needs_work

More list(map(...))s that might as well be list comprehensions:

  • src/sage/manifolds/differentiable/affine_connection.py

    diff --git a/src/sage/manifolds/differentiable/affine_connection.py b/src/sage/manifolds/differentiable/affine_connection.py
    index e1d6601..e307a9c 100644
    a b class AffineConnection(SageObject): 
    11861186        if index_labels is None and isinstance(frame, CoordFrame) and \
    11871187          coordinate_labels:
    11881188            ch = frame.chart()
    1189             index_labels = map(str, ch[:])
    1190             index_latex_labels = map(latex, ch[:])
     1189            index_labels = list(map(str, ch[:]))
     1190            index_latex_labels = list(map(latex, ch[:]))
    11911191        return self.coef(frame=frame).display(symbol,
    11921192              latex_symbol=latex_symbol, index_positions='udd',
    11931193              index_labels=index_labels, index_latex_labels=index_latex_labels,

I think I've mentioned elsewhere (and forgive me if this concern was dismissed and I didn't see it), but I don't like these usesless hash example tests like:

  • src/sage/rings/fraction_field.py

    diff --git a/src/sage/rings/fraction_field.py b/src/sage/rings/fraction_field.py
    index 201e132..024d83d 100644
    a b class FractionField_generic(ring.Field): 
    688688        """
    689689        return not (self == other)
    690690
     691    def __hash__(self):
     692        """
     693        Compute the hash of ``self``.
     694
     695        EXAMPLES::
     696
     697            sage: h = hash(Frac(ZZ['x']))
     698        """
     699        return hash(self._R) ^ 147068341996611
     700
    691701    def ngens(self):
    692702        """
    693703        This is the same as for the parent object.

All this tests is that, at best, it doesn't crash (which is almost completely trivial). It should instead demonstrate at least a case where two hashes compare the same as expected, and where two hashes differ, as expected.

I agree it's annoying to write these tests which is why I've been pokey about making tickets for __hash__ implementations in the first place :)

comment:21 Changed 18 months ago by git

  • Commit changed from 97d8e09ab04a0c8551d7ba64540d910a1287ae60 to dab8b92a5d70ce10554b9faafcc0cc5ca2c3d929

Branch pushed to git repo; I updated commit sha1. New commits:

c91be02Merge branch 'u/chapoton/25586' in 8.3.b7
dab8b92more doctests for hash

comment:22 Changed 18 months ago by chapoton

  • Status changed from needs_work to needs_review

done

comment:23 follow-up: Changed 18 months ago by embray

This is a stupid question and I think I might have already answered it in my head but, just for my edification:

  • src/sage/rings/fraction_field.py

    diff --git a/src/sage/rings/fraction_field.py b/src/sage/rings/fraction_field.py
    index 201e132..909f10b 100644
    a b class FractionField_generic(ring.Field): 
    688688        """
    689689        return not (self == other)
    690690
     691    def __hash__(self):
     692        """
     693        Compute the hash of ``self``.
     694
     695        EXAMPLES::
     696
     697            sage: h0 = hash(Frac(ZZ['x']))
     698            sage: h1 = hash(Frac(ZZ['x']))
     699            sage: h2 = hash(Frac(QQ['x']))
     700            sage: h3 = hash(ZZ['x'])
     701            sage: h0 == h1 and h1 != h2 and h1 != h3
     702            True
     703        """
     704        return hash(self._R) ^ 147068341996611
     705
    691706    def ngens(self):
    692707        """
    693708        This is the same as for the parent object.

Why not just hash(self._R)? Is it possible for instances of these fields to have a parent ring that's equivalent to itself, or something (in which case we'd need this in order for them to have unique hashes)? And where does the magic number come from?

comment:24 Changed 18 months ago by chapoton

This was modeled after the case of Laurent Polynomial at the request of Vincent, to avoid having trivially the same hash. The number is a random number.

comment:25 Changed 18 months ago by embray

I see, he wrote:

For Laurent polynomial ring it is not a good idea to give it the same hash as the underlying multi-polynomial ring. You would better xor it with a random number

But why is that? It doesn't matter if they have the same hash unless they can also compare equal to each other.

In any case, even if there is a good reason, this should probably be noted. It's not obvious.

comment:26 Changed 18 months ago by embray

My guess is that maybe you can have a polynomial ring over elements of another polynomial ring, so in that case it does make sense to do that.

comment:27 Changed 18 months ago by chapoton

Do you want a note in the doc of the hash method ?

comment:28 Changed 18 months ago by embray

In the doc or just in a comment. Up to you.

comment:29 Changed 18 months ago by git

  • Commit changed from dab8b92a5d70ce10554b9faafcc0cc5ca2c3d929 to 6806c3791dcd65a2648e421a26f506616b111403

Branch pushed to git repo; I updated commit sha1. New commits:

6806c37trac 25586 adding comment

comment:30 Changed 18 months ago by chapoton

done

comment:31 Changed 17 months ago by chapoton

ping ?

comment:32 follow-up: Changed 17 months ago by chapoton

PING ? This is a major hurting point..

comment:33 in reply to: ↑ 23 Changed 17 months ago by vdelecroix

Replying to embray:

This is a stupid question and I think I might have already answered it in my head but, just for my edification:

  • src/sage/rings/fraction_field.py

    diff --git a/src/sage/rings/fraction_field.py b/src/sage/rings/fraction_field.py
    index 201e132..909f10b 100644
    a b class FractionField_generic(ring.Field): 
    688688        """
    689689        return not (self == other)
    690690
     691    def __hash__(self):
     692        """
     693        Compute the hash of ``self``.
     694
     695        EXAMPLES::
     696
     697            sage: h0 = hash(Frac(ZZ['x']))
     698            sage: h1 = hash(Frac(ZZ['x']))
     699            sage: h2 = hash(Frac(QQ['x']))
     700            sage: h3 = hash(ZZ['x'])
     701            sage: h0 == h1 and h1 != h2 and h1 != h3
     702            True
     703        """
     704        return hash(self._R) ^ 147068341996611
     705
    691706    def ngens(self):
    692707        """
    693708        This is the same as for the parent object.

Why not just hash(self._R)?

To avoid collisions. We do have dictionaries whose keys are parent (e.g. coercions).

comment:34 Changed 17 months ago by vdelecroix

For matter of equality, it is true that the polynomial ring on the zero ring is isomorphic to the base ring. Though, Sage does not know about it.

sage: S = Zmod(1)
sage: R = S['x']
sage: S == R
False

And even worse

sage: f = R.coerce_map_from(S)
sage: f.is_injective()
True
sage: f.is_surjective()
False

comment:35 follow-up: Changed 17 months ago by vdelecroix

([EDITED] see #25586 #25753 for the bug about surjectivity)

Last edited 17 months ago by vdelecroix (previous) (diff)

comment:36 in reply to: ↑ 35 ; follow-up: Changed 17 months ago by tscrim

  • Keywords days94 added
  • Reviewers changed from Vincent Delecroix, Travis Scrimshaw to Vincent Delecroix, Travis Scrimshaw, Erik Bray
  • Status changed from needs_review to positive_review

Replying to vdelecroix:

(see #25586 for the bug about surjectivity)

See this ticket?

I am going to set this back to positive review as Erik's concerns have been addressed.

comment:37 in reply to: ↑ 36 Changed 17 months ago by vdelecroix

Replying to tscrim:

Replying to vdelecroix:

(see #25586 for the bug about surjectivity)

See this ticket?

Oups: #25753

I am going to set this back to positive review as Erik's concerns have been addressed.

comment:38 Changed 17 months ago by vbraun

  • Branch changed from u/chapoton/25586 to 6806c3791dcd65a2648e421a26f506616b111403
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:39 in reply to: ↑ 32 Changed 17 months ago by embray

  • Commit 6806c3791dcd65a2648e421a26f506616b111403 deleted

Replying to chapoton:

PING ? This is a major hurting point..

Please try to show some patience. I have tickets that I believe are important that haven't been merged or even reviewed in months (a situation I'm not happy with, but there is only so much attention to go around).

If you've already fixed the issue then there's nothing holding you back--this is why I have my private Python 3 branch--everything I fix gets merged into it immediately and then I can carry on (even if that fix is not ultimately the accepted fix; at least it works in the meantime).

The rest of us have vacations, family, sickness, and other tasks to work on and adding "ping" to a ticket does not (at least in my case) make it any more likely that I'll see it sooner.

Note: See TracTickets for help on using tickets.