Enable hash for FreeMonoid_class

[jhpalmieri]

As in #26162 and other tickets, removing __eq__ does the job. Also:

• use UniqueRepresentation instead of UniqueFactory for constructing instances of FreeMonoid.
• clean up caching of subclasses: no need to do this by hand, since they will now inherit from UniqueRepresentation.

Without this change, there are Python 3 doctest failures in sage/algebras/lie_algebras, among other places. For example,

File "src/sage/algebras/lie_algebras/lie_algebra.py", line 1402, in sage.algebras.lie_algebras.lie_algebra.LiftMorphismToAssociative.preimage
Failed example:
    L = LieAlgebra(associative=R)
Exception raised:
    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 1000, in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6175)
        return self.cache[k]
      File "sage/misc/weak_dict.pyx", line 706, in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (build/cythonized/sage/misc/weak_dict.c:3538)
        cdef PyObject* wr = PyDict_GetItemWithError(self, k)
    TypeError: unhashable type: 'FreeMonoid_class_with_category'

...

Part of #24551.

Component: python3

Author: John Palmieri

Branch/Commit: 8d3b505

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26221

[jhpalmieri]

Branch: u/jhpalmieri/free-monoid-hash

[jhpalmieri]

Commit: d6c3b5f

[jhpalmieri]

New commits:

d6c3b5f

trac 26221: enable hash for FreeMonoid_class_with_category

[tscrim]

comment:3

Doctest failures (see patchbots):

sage -t --long src/sage/crypto/classical.py  # 8 doctests failed
sage -t --long src/sage/crypto/classical_cipher.py  # 5 doctests failed

The issue comes from the fact that StringMonoid_class inherits from FreeMonoid_class, but because the FreeMonoid_class uses UniqueFactory, it does not have UniqueRepresentation behavior inherited. Moreover, all of the subclasses of StringMonoid_class have their own hand-rolled caches. The proper thing to do would be to rename FreeMonoid_class -> FreeMonoid and have it inherit from UniqueRepresentation and get rid of all of those custom caches. It is a bit of work, but it will be a good improvement to the code.

[tscrim]

Reviewer: Travis Scrimshaw

[jhpalmieri]

comment:4

I think I would prefer to keep FreeMonoid as a function, since it forks depending on whether the monoid is abelian or not, but I can try to work on having FreeMonoid_class inherit from UniqueRepresentation.

[tscrim]

comment:5

Replying to @jhpalmieri:

I think I would prefer to keep FreeMonoid as a function, since it forks depending on whether the monoid is abelian or not, but I can try to work on having FreeMonoid_class inherit from UniqueRepresentation.

You can absorb this behavior into the __classcall_private__, but perhaps considering the documentation, it might be better to actually keep it separate. I don't have a particularly strong opinion either way.

[sagetrac-git]

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

8c1e9ea

trac 26221: FreeMonoid: use UniqueRepresentation instead of UniqueFactory.

[sagetrac-git]

Changed commit from d6c3b5f to 8c1e9ea

[jhpalmieri]

comment:7

Okay, here is a branch using UniqueRepresentation, but I'm confused by

Moreover, all of the subclasses of StringMonoid_class have their own hand-rolled caches.

Can you clarify?

[tscrim]

comment:8

Replying to @jhpalmieri:

Okay, here is a branch using UniqueRepresentation, but I'm confused by

Great, thank you. Small detail: the doc from __classcall_private__ should almost entirely be moved into the class-level doc so it is visible under FreeMonoid? and in the html docs.

Moreover, all of the subclasses of StringMonoid_class have their own hand-rolled caches.

Can you clarify?

See the _cache module variable and def BinaryStrings() in string_monoid.py. So they are double-caching with your current changes.

[sagetrac-git]

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

24dedf5

trac 26221: fix the docstrings.

[sagetrac-git]

Changed commit from 8c1e9ea to 24dedf5

[sagetrac-git]

Changed commit from 24dedf5 to f7d2046

[sagetrac-git]

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

f7d2046

trac 26221: remove superfluous caching in string_monoid.py.

[jhpalmieri]

comment:11

Okay, how about this? (Independently, I realized the same thing about the docstrings, which is why I made that change almost immediately after your comment.) I also thought about just renaming BinaryStringMonoid -> BinaryStrings, but both are used in different parts of the Sage library, so I left it as is.

[tscrim]

comment:14

The docstrings still will not show in the ? and html doc if they are in the __init__ because there is already a class-level doc. I would rather have it in the class-level doc so we can use the __init__ to discuss implementation details. You also should be able to just call the index_set as n in the __init__.

I am okay with leaving the alias for now, but it should really be uniformized at some point. Yet, I've already asked quite a lot from you on this ticket.

[sagetrac-git]

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

8d3b505

trac 26221: fix a bug and add a doctest for it. Move the main

[sagetrac-git]

Changed commit from f7d2046 to 8d3b505

[jhpalmieri]

comment:16

Okay, how about this?

[tscrim]

comment:17

Yep. LGTM. Thank you.

[vbraun]

Changed branch from u/jhpalmieri/free-monoid-hash to 8d3b505