Opened 7 years ago
Last modified 3 months ago
#19195 needs_work enhancement
Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters
Reported by:  Vincent Delecroix  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  combinatorics  Keywords:  
Cc:  Nicolas M. Thiéry, Travis Scrimshaw, Lorenz Panny, Vincent Delecroix, John Palmieri  Merged in:  
Authors:  Frédéric Chapoton, Matthias Koeppe, ...  Reviewers:  
Report Upstream:  N/A  Work issues:  fix sage.rings.asymptotic 
Branch:  public/19195 (Commits, GitHub, GitLab)  Commit:  997cc7cc92bebcb491594ca586eadf5cfc591271 
Dependencies:  #34374  Stopgaps: 
Description (last modified by )
The last class to use sage.combinat.cartesian_product.CartesianProduct_iters
is the CombinatorialFreeModule
.
It is not simple to get rid of this since there is no check in constructing element of a combinatorial free module... hence changing the basis from being tuples to be element of a cartesian product might lead to subtle errors (e.g. http://trac.sagemath.org/ticket/18411#comment:24). This is addressed in #18750
This will solve #18849 and probably #24900.
Part of #15425: Metaticket: Cleanup cartesian products
Change History (109)
comment:1 Changed 5 years ago by
Branch:  → public/19195 

Cc:  Travis Scrimshaw added; Nathann Cohen removed 
Commit:  → 1eac71e316a1d0c2d854092773bfa12af7330a8d 
Dependencies:  #18411 
comment:2 Changed 2 years ago by
Milestone:  sage6.9 → sage9.3 

comment:3 Changed 22 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:4 Changed 17 months ago by
Milestone:  sage9.4 → sage9.5 

comment:5 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:6 Changed 8 months ago by
Milestone:  sage9.6 → sage9.7 

comment:7 Changed 4 months ago by
Description:  modified (diff) 

comment:8 Changed 4 months ago by
Summary:  Make tensor of CombinatorialFreeModule use cartesian_product → Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters 

comment:9 Changed 4 months ago by
Description:  modified (diff) 

comment:10 Changed 4 months ago by
Commit:  1eac71e316a1d0c2d854092773bfa12af7330a8d → 75bf2bded5dec0e3d13f929b7a936b0a9e8d18fb 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
75bf2bd  work on CartesianProduct_iter

comment:11 followup: 15 Changed 4 months ago by
Rebased. Some doctests need to be updated. In particular:
********************************************************************** File "src/sage/combinat/free_module.py", line 1520, in sage.combinat.free_module.CombinatorialFreeModule.CombinatorialFreeModule_Tensor._coerce_map_from_ Failed example: S.an_element() Expected: 3*B[0] # B[1] + 2*B[0] # B[0] + 2*B[0] # B[1] ... UserWarning: Sage is not able to determine whether the factors of this Cartesian product are finite. The lexicographic ordering might not go through all elements. 3*B[0] # B[1] + B[0] # B[0] + 2*B[0] # B[1] + B[1] # B[1]
comment:12 Changed 4 months ago by
Description:  modified (diff) 

comment:13 Changed 4 months ago by
Commit:  75bf2bded5dec0e3d13f929b7a936b0a9e8d18fb → 2d81aa8abd59adadff4a1d48a281f8da9450d12f 

Branch pushed to git repo; I updated commit sha1. New commits:
2d81aa8  src/sage/combinat/cartesian_product.py: Deprecate CartesianProduct_iters

comment:14 Changed 4 months ago by
Authors:  → Frédéric Chapoton, Matthias Koeppe 

comment:15 Changed 4 months ago by
Cc:  Lorenz Panny added 

comment:16 followup: 18 Changed 4 months ago by
I think this warning (from Sets.CartesianProducts.ParentMethods.__iter__
, added in #18411) is useless and is best removed. It's essentially warning that it may be constructing an infinite order of the wrong order type. But this is irrelevant for any algorithm
comment:17 Changed 4 months ago by
Cc:  Vincent Delecroix added 

comment:18 Changed 4 months ago by
Replying to mkoeppe:
I think this warning (from
Sets.CartesianProducts.ParentMethods.__iter__
, added in #18411) is useless and is best removed. It's essentially warning that it may be constructing an infinite order of the wrong order type. But this is irrelevant for any algorithm
I take this back. I now propose that instead of issuing a warning, Cartesian products of possibly infinite factors should be enumerated using the existing, poorly named function sage.misc.mrange.cantor_product
(enumeration in the order of increasing sumsofranks).
comment:19 Changed 4 months ago by
Commit:  2d81aa8abd59adadff4a1d48a281f8da9450d12f → 8017fed68ac3df9ca4cd5e8a2f3bfcdc3df17615 

Branch pushed to git repo; I updated commit sha1. New commits:
8017fed  Sets.CartesianProducts.ParentMethods.__iter__: Use cantor_product if factors other than first are infinite

comment:20 Changed 4 months ago by
Commit:  8017fed68ac3df9ca4cd5e8a2f3bfcdc3df17615 → 97a381b413421e69f19d0a8ff995259b0d5bea14 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
97a381b  Sets.CartesianProducts.ParentMethods.__iter__: Use cantor_product if factors other than first are infinite

comment:21 Changed 4 months ago by
Commit:  97a381b413421e69f19d0a8ff995259b0d5bea14 → ea7af8b2c9174ad4ac80b0ffd12a9d563094e96b 

Branch pushed to git repo; I updated commit sha1. New commits:
ea7af8b  src/sage/combinat/free_module.py: Update doctests

comment:22 Changed 4 months ago by
Doctest failures in 2 files remain:
sage t long randomseed=231229664758049651431332547293032544509 src/sage/algebras/steenrod/steenrod_algebra.py # Timed out sage t long randomseed=231229664758049651431332547293032544509 src/sage/homology/hochschild_complex.py # 10 doctests failed
comment:23 Changed 4 months ago by
Commit:  ea7af8b2c9174ad4ac80b0ffd12a9d563094e96b → 6e8127049cb0014d574db6c3b39615cdac8128d0 

Branch pushed to git repo; I updated commit sha1. New commits:
6e81270  src/sage/homology/hochschild_complex.py: Update doctest output (an_element changed)

comment:24 Changed 4 months ago by
Cc:  John Palmieri added 

Only one file, src/sage/algebras/steenrod/steenrod_algebra.py
needs a closer look by experts:
UserWarning: Testing equality of infinite sets which will not end in case of equality TypeError: <class 'sage.sets.set_from_iterator.EnumeratedSetFromIterator_with_category'> is not hashable and does not implement _cache_key()  The following tests failed: _test_antipode (times out)
comment:25 Changed 4 months ago by
Summary:  Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters → Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters, use cantor_product for products of infinite sets 

comment:26 Changed 4 months ago by
This is the doctest that times out:
sage: d = a.change_basis('comm_long'); d.coproduct() ## line 3392 ##
sage.sets.set_from_iterator.EnumeratedSetFromIterator.__eq__
gives the warning and then indeed times out trying to compare the following sets:
(Pdb) p self basis key family of mod 2 Steenrod algebra, pst_revz basis (Pdb) p other basis key family of mod 2 Steenrod algebra, comm_revz_long basis (Pdb) p type(self) <class 'sage.sets.set_from_iterator.EnumeratedSetFromIterator_with_category'> (Pdb) p type(other) <class 'sage.sets.set_from_iterator.EnumeratedSetFromIterator_with_category'>
comment:27 Changed 4 months ago by
This equality test is needed by the UniqueRepresentation
behavior of sage.sets.cartesian_product.CartesianProduct
comment:28 Changed 4 months ago by
Unfortunately, while I see the doctest failure, I can't replicate it in an interactive session, so it's hard to debug. I think the problem arises in the lines
for (a,b), coeff in x: result.append((tensor((A._change_basis_on_basis(a, basis), A._change_basis_on_basis(b, basis))),coeff))
(lines 13768).
comment:29 Changed 4 months ago by
Here's a minimal reproducer:
sage: SteenrodAlgebra(basis='pst').Sq(0,1).coproduct() sage: a = Sq(2) sage: d = a.change_basis('comm_long'); d.coproduct()
comment:30 Changed 4 months ago by
The bases for "mod 2 Steenrod algebra, pst_revz basis" and "mod 2 Steenrod algebra, comm_revz_long basis" have the same indexing sets, although the corresponding algebra elements are different. Therefore the same will be true for their tensor squares. As a result, I'm not sure what to do about this.
comment:31 Changed 4 months ago by
sage: s_pst = SteenrodAlgebra(basis='pst') sage: s_comm_long = SteenrodAlgebra(basis='comm_long') sage: s_pst.basis() Lazy family (Term map from basis key family of mod 2 Steenrod algebra, pst_revz basis to mod 2 Steenrod algebra, pst_revz basis(i))_{i in basis key family of mod 2 Steenrod algebra, pst_revz basis} sage: s_comm_long.basis() Lazy family (Term map from basis key family of mod 2 Steenrod algebra, comm_revz_long basis to mod 2 Steenrod algebra, comm_revz_long basis(i))_{i in basis key family of mod 2 Steenrod algebra, comm_revz_long basis} sage: s_pst.basis() == s_comm_long.basis() /Users/mkoeppe/s/sage/sagerebasing/local/var/lib/sage/venvpython3.9/lib/python3.9/sitepackages/sage/sets/set_from_iterator.py:311: UserWarning: Testing equality of infinite sets basis key family of mod 2 Steenrod algebra, pst_revz basis and basis key family of mod 2 Steenrod algebra, comm_revz_long basis, which will not end in case of equality
comment:32 Changed 4 months ago by
It seems we either need a better __eq__
for LazyFamily
in general, or just more specific Family
implementation for these basis key families
comment:33 Changed 4 months ago by
Commit:  6e8127049cb0014d574db6c3b39615cdac8128d0 → 2a17576cdff070ab24e22cd5c317987e701e1071 

Branch pushed to git repo; I updated commit sha1. New commits:
2a17576  LazyFamily.__eq__: Check hashes first, then check repr, then check the possibly infinite set of keys

comment:34 Changed 4 months ago by
This fixes the comparison in comment:31, but not the original problem
comment:35 Changed 4 months ago by
sage: s_pst = SteenrodAlgebra(basis='pst') sage: s_comm_long = SteenrodAlgebra(basis='comm_long') sage: s_pst.basis().keys() == s_comm_long.basis().keys() /Users/mkoeppe/s/sage/sagerebasing/local/var/lib/sage/venvpython3.9/lib/python3.9/sitepackages/sage/sets/set_from_iterator.py:311: UserWarning: Testing equality of infinite sets basis key family of mod 2 Steenrod algebra, pst_revz basis and basis key family of mod 2 Steenrod algebra, comm_revz_long basis, which will not end in case of equality
comment:37 Changed 4 months ago by
Although they have different string representations, so I don't know why the latest change doesn't catch it.
comment:38 Changed 4 months ago by
The latest change was for LazyFamily
, not for EnumeratedSetFromIterator
.
comment:39 Changed 4 months ago by
EnumeratedSetFromIterator
does not look at names; __eq__
is equality as sets
comment:40 Changed 4 months ago by
This fixes the problem for me, but I don't know if it's the right thing to do:

src/sage/sets/set_from_iterator.py
diff git a/src/sage/sets/set_from_iterator.py b/src/sage/sets/set_from_iterator.py index 3a2360383e..90218aa426 100644
a b class EnumeratedSetFromIterator(Parent): 297 297 True 298 298 """ 299 299 if isinstance(other, EnumeratedSetFromIterator): 300 if repr(self) != repr(other): 301 return False 300 302 # trick to allow equality between infinite sets 301 303 # this assume that the function does not return randomized data! 302 304 if (self._func == other._func and
comment:41 Changed 4 months ago by
If we want to go in the direction (making the factors "less unique"), I'd think we could give EnumeratedSetFromIterator
an additional argument unique_tag
(default None), which would be compared (instead of repr)
comment:42 Changed 4 months ago by
They have a "name" attribute already; we could use that. Edit: a "name" argument, not an attribute.
comment:44 Changed 4 months ago by

src/sage/sets/set_from_iterator.py
diff git a/src/sage/sets/set_from_iterator.py b/src/sage/sets/set_from_iterator.py index 3a2360383e..dbb448b829 100644
a b class EnumeratedSetFromIterator(Parent): 297 297 True 298 298 """ 299 299 if isinstance(other, EnumeratedSetFromIterator): 300 if hasattr(self, '__custom_name') or hasattr(other, '__custom_name'): 301 if repr(self) != repr(other): 302 return False 300 303 # trick to allow equality between infinite sets 301 304 # this assume that the function does not return randomized data! 302 305 if (self._func == other._func and
comment:45 Changed 4 months ago by
I think this is too dangerous, it's breaking the extensionality of sets
comment:46 Changed 4 months ago by
I think a solution may be to change sage.sets.cartesian_product.CartesianProduct
so that it only uses UniqueRepresentation
if it can safely do so
comment:47 Changed 4 months ago by
Commit:  2a17576cdff070ab24e22cd5c317987e701e1071 → 377d0bfc11130123c21a686f21325d4581ffb774 

Branch pushed to git repo; I updated commit sha1. New commits:
377d0bf  src/sage/sets/cartesian_product.py: Do not use UniqueRepresentation when a factor is an EnumeratedSetFromIterator

comment:49 Changed 4 months ago by
This produces a lot of doctest failures:
sage t long randomseed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/asymptotic_expansion_generators.py # 86 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/symbolic/expression.pyx # 3 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/doctest/forker.py # 3 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/homology/hochschild_complex.py # 2 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/categories/pushout.py # 6 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/asymptotic_ring.py # 236 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/algebras/hecke_algebras/ariki_koike_algebra.py # 13 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/term_monoid.py # 99 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/algebras/askey_wilson.py # 2 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/growth_group.py # 114 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/combinat/root_system/extended_affine_weyl_group.py # 404 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/growth_group_cartesian.py # 118 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/symbolic/ring.pyx # 5 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/categories/sets_cat.py # 2 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/algebras/schur_algebra.py # 1 doctest failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/categories/magmas.py # 4 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/doc/en/thematic_tutorials/lie/affine.rst # 1 doctest failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/groups/group_semidirect_product.py # 35 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/sets/family.py # 3 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/rings/big_oh.py # 2 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/sets/cartesian_product.py # 2 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/combinat/posets/cartesian_product.py # 48 doctests failed sage t long randomseed=269458505477710295233910752449959854719 src/sage/combinat/cartesian_product.py # 2 doctests failed
comment:50 Changed 4 months ago by
Commit:  377d0bfc11130123c21a686f21325d4581ffb774 → 6d5f261a6e6cfcd8a49b9f5af2ae0bfb21b1201e 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6d5f261  src/sage/sets/cartesian_product.py: Do not use UniqueRepresentation when a factor is an EnumeratedSetFromIterator

comment:52 Changed 4 months ago by
But hey, no failures in algebras/steenrod
, homology,
or topology
, so it's all good with me. ;)
comment:53 Changed 4 months ago by
OK some of the failures were already present in 2a17576 (comment:33)
comment:54 Changed 4 months ago by
Commit:  6d5f261a6e6cfcd8a49b9f5af2ae0bfb21b1201e → e9694481061f271fbbedd3434629568ccf0b5928 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e969448  LazyFamily.__eq__: Check hashes of the index sets only, not the hashes of self, other

comment:55 Changed 4 months ago by
I'm still seeing a lot of error messages of the form
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage9.7.beta8/src/sage/rings/asymptotic/growth_group_cartesian.py", line 320, in __init__ GenericGrowthGroup.__init__(self, sets[0], Vars, self.category(), **kwds) TypeError: __init__() got an unexpected keyword argument 'flatten'
Also a few in pushout.py
:
File "sage/misc/classcall_metaclass.pyx", line 320, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ return cls.classcall(cls, *args, **kwds) TypeError: __classcall__() missing 1 required positional argument: 'category'
comment:56 Changed 4 months ago by
https://github.com/sagemath/sagetracmirror/actions/runs/2850051513 only sees the error in steenrod with e969448
comment:58 Changed 4 months ago by
Commit:  e9694481061f271fbbedd3434629568ccf0b5928 → 3de34ae68444f6a883a9e268f34f792e38042e0c 

Branch pushed to git repo; I updated commit sha1. New commits:
3de34ae  src/sage/sets/cartesian_product.py: Do not use UniqueRepresentation when a factor is an EnumeratedSetFromIterator

comment:59 Changed 4 months ago by
OK here's a better version of the same approach, it passes all tests for me
comment:60 Changed 4 months ago by
Commit:  3de34ae68444f6a883a9e268f34f792e38042e0c → c30e0da0df8e6798f78704876b3f636097f32dfa 

Branch pushed to git repo; I updated commit sha1. New commits:
c30e0da  src/sage/sets/cartesian_product.py: Do use UniqueRepresentation when sets are finite; add tests

comment:61 Changed 4 months ago by
Status:  new → needs_review 

comment:62 Changed 4 months ago by
Commit:  c30e0da0df8e6798f78704876b3f636097f32dfa → 1c303121d6e407fd0906f745826fc37b4db3bf58 

Branch pushed to git repo; I updated commit sha1. New commits:
1c30312  src/sage/categories/sets_cat.py: Update documentation  cantor_product refines with revlex

comment:63 followups: 64 65 68 81 93 Changed 4 months ago by
Thank you for working on this. It definitely would be good to have things more centralized. Hopefully these comments are fairly simple to incorporate.
I think this is a very dangerous test:
if not repr(self) == repr(other):
(which it should use !=
anyways) because
sage: x = 1.0 sage: y = 1 sage: repr(x) == repr(y) False sage: x == y True sage: hash(x) == hash(y) True
Equal objects need not have equal (string) representations. So you have introduced a change in behavior in a way that does not respect equality.
On the other hand, I disagree with this reasoning:
Two :class:`EnumeratedSetFromIterator` objects that are not known to be finite cannot be reliably tested for equality. Therefore, we do not put such objects in the :class:`~sage.structure.unique_representation.UniqueRepresentation` cache.
It depends on what you mean by equality. Now we normally think of equality of sets as containment in both ways, but it might be better to think of them like knots or polytopes. You might have the same polytope (same subset of R^{n}) but different representations. So it could make sense for them to not be equal. Consequently, I do not support this disabling of UniqueRepresentation
. Either you need to remove that altogether, which I strongly oppose because of the consequences with parents and how much nicer UniqueRepresentation
behavior makes things, or you test by equality, which uses whatever definition of equality the object uses.
This statement is needs correcting:
When the first factor is infinite (or not known to be finite), it still +When all but the first factor is known to be finite, it uses the lexicographic order::
I believe your code would produce
sage: list(islice(cantor_product(NN, NN, GF(2)), 6)) [(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (2, 0, 0), (1, 1, 0)]
Something else to be aware of is elements of cartesian_product
are actual Sage elements rather than list
s. So this could lead to performance regressions. Lots of things use the CFM_tensor
class; all of the Hopf algebras basically. We might want a base or sub class of the cartesian_product
that acts as a façade parent for tuples. So the only difference is essentially in the _element_constructor_
and/or __call__
.
I am wondering why we did not put EnumeratedSets().CartesianProducts()
in the category of EnumeratedSets()
. We might want to do this to have access to some of the generic methods from there, such as unrank()
. Likewise, it would be good to port over some of these extra methods to cartesian_product
, which would improve the (generic) implementation, and/or move things into the category.
comment:64 followup: 67 Changed 4 months ago by
Replying to tscrim:
I think this is a very dangerous test:
if not repr(self) == repr(other):(which it should use
!=
anyways) becausesage: x = 1.0 sage: y = 1 sage: repr(x) == repr(y) False sage: x == y True sage: hash(x) == hash(y) TrueEqual objects need not have equal (string) representations. So you have introduced a change in behavior in a way that does not respect equality.
No, the repr
comparison was already in the old method. It's only reordered.
comment:65 followups: 69 86 Changed 4 months ago by
Replying to tscrim:
On the other hand, I disagree with this reasoning:
Two :class:`EnumeratedSetFromIterator` objects that are not known to be finite cannot be reliably tested for equality. Therefore, we do not put such objects in the :class:`~sage.structure.unique_representation.UniqueRepresentation` cache.It depends on what you mean by equality. Now we normally think of equality [...] or you test by equality, which uses whatever definition of equality the object uses.
I think you are trying to tell me that when I disabled UniqueRepresentation
, I also need to disable WithEqualityById
.
I agree with this, it needs to be corrected.
sage: from sage.sets.set_from_iterator import EnumeratedSetFromIterator sage: F = EnumeratedSetFromIterator(lambda: iter([1, 2])) sage: F.category() Category of facade enumerated sets sage: cartesian_product([F, F]) is cartesian_product([F, F]) # as intended False sage: cartesian_product([F, F]) == cartesian_product([F, F]) # BUG False
comment:66 Changed 4 months ago by
Status:  needs_review → needs_work 

comment:67 followup: 70 Changed 4 months ago by
Replying to mkoeppe:
Replying to tscrim:
I think this is a very dangerous test:
if not repr(self) == repr(other):(which it should use
!=
anyways) becausesage: x = 1.0 sage: y = 1 sage: repr(x) == repr(y) False sage: x == y True sage: hash(x) == hash(y) TrueEqual objects need not have equal (string) representations. So you have introduced a change in behavior in a way that does not respect equality.
No, the
repr
comparison was already in the old method. It's only reordered.
I misread the original code; after that test was true, it would compare the repr
. This is very strange logic. I agree that it does not change the behavior. However, I still stand by my statement about it being a dangerous test.
comment:68 Changed 4 months ago by
Replying to tscrim:
I am wondering why we did not put
EnumeratedSets().CartesianProducts()
in the category ofEnumeratedSets()
. We might want to do this
+1
comment:69 followup: 71 Changed 4 months ago by
Replying to mkoeppe:
Replying to tscrim:
On the other hand, I disagree with this reasoning:
Two :class:`EnumeratedSetFromIterator` objects that are not known to be finite cannot be reliably tested for equality. Therefore, we do not put such objects in the :class:`~sage.structure.unique_representation.UniqueRepresentation` cache.It depends on what you mean by equality. Now we normally think of equality [...] or you test by equality, which uses whatever definition of equality the object uses.
I think you are trying to tell me that when I disabled
UniqueRepresentation
, I also need to disableWithEqualityById
.
No, that is not what I am saying. I am saying you should either fully and completely remove UniqueRepresentation
from being a base class (likely downgrading to CachedRepresentation
) or understand and learn to live with equality is not always mathematical equality. IMO, what you are doing has a very strong code smell as it is breaking many rules of OOP.
comment:70 Changed 4 months ago by
Replying to tscrim:
I still stand by my statement about it being a dangerous test.
I fully agree, but I consider it beyond the scope of this ticket
comment:71 followups: 74 96 Changed 4 months ago by
Replying to tscrim:
IMO, what you are doing has a very strong code smell as it is breaking many rules of OOP.
Sure it is, but I don't agree with your conclusion.
There is a simple fix  we can just push this a level lower, namely into the implementation of CachedRepresentation/UniqueRepresentation?.
comment:72 followup: 75 Changed 4 months ago by
Commit:  1c303121d6e407fd0906f745826fc37b4db3bf58 → 278b7c7ec6eccc9125cd4066c15c3c16268b1382 

Branch pushed to git repo; I updated commit sha1. New commits:
278b7c7  src/sage/categories/enumerated_sets.py: Make (finitary) Cartesian products of enumerated enumerated

comment:74 followup: 79 Changed 4 months ago by
Replying to mkoeppe:
Replying to tscrim:
IMO, what you are doing has a very strong code smell as it is breaking many rules of OOP.
Sure it is, but I don't agree with your conclusion.
There is a simple fix  we can just push this a level lower, namely into the implementation of CachedRepresentation/UniqueRepresentation?.
I don't understand this last part. The issue is you have a subclass of UniqueRepresentation
that does not implement the UniqueRepresentation
protocol (only a CachedRepresentation
). So it should be a CachedRepresentation
. This is okay, and you could have a subclass for those Cartesian products of finite sets that inherits from UniqueRepresentation
. Not only does this make the code more complicated, it also effects the speed and reliability of other implementations.
comment:75 Changed 4 months ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
278b7c7 src/sage/categories/enumerated_sets.py: Make (finitary) Cartesian products of enumerated enumerated
This caused some doctest failures:
File "sage/categories/sets_cat.py", line 2273, in sage.categories.sets_cat.Sets.CartesianProducts.ParentMethods.__iter__ Failed example: it = iter(cartesian_product([ZZ, GF(2)])) Exception raised: Traceback (most recent call last): File "/__w/sagetracmirror/sagetracmirror/src/sage/doctest/forker.py", line 695, in _run self.compile_and_execute(example, compiler, test.globs) File "/__w/sagetracmirror/sagetracmirror/src/sage/doctest/forker.py", line 1093, in compile_and_execute exec(compiled, globs) File "<doctest sage.categories.sets_cat.Sets.CartesianProducts.ParentMethods.__iter__[13]>", line 1, in <module> it = iter(cartesian_product([ZZ, GF(Integer(2))])) File "/__w/sagetracmirror/sagetracmirror/src/sage/categories/enumerated_sets.py", line 238, in __iter__ raise NotImplementedError("iterator called but not implemented") NotImplementedError: iterator called but not implemented
comment:76 Changed 4 months ago by
Let's do these category improvements in a separate ticket, #34356.
comment:77 Changed 4 months ago by
Commit:  278b7c7ec6eccc9125cd4066c15c3c16268b1382 → 1c303121d6e407fd0906f745826fc37b4db3bf58 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:78 Changed 4 months ago by
Commit:  1c303121d6e407fd0906f745826fc37b4db3bf58 → d132fb7f0808b421988bfccc9672038707ca960d 

comment:79 Changed 4 months ago by
Replying to tscrim:
The issue is you have a subclass of
UniqueRepresentation
that does not implement theUniqueRepresentation
protocol (only aCachedRepresentation
). So it should be aCachedRepresentation
.
Actually, not even a CachedRepresentation
. I've now introduced a new class WithPicklingByInitArgs
, which CachedRepresentation
subclasses.
comment:80 Changed 4 months ago by
Commit:  d132fb7f0808b421988bfccc9672038707ca960d → 85fd255aa2df8003505ccce096d5e9baad3bd903 

Branch pushed to git repo; I updated commit sha1. New commits:
85fd255  src/sage/categories/sets_cat.py: Rephrase cartesian product docstring

comment:81 Changed 4 months ago by
Replying to tscrim:
This statement is needs correcting:
When the first factor is infinite (or not known to be finite), it still +When all but the first factor is known to be finite, it uses the lexicographic order::
I have rephrased in a similar way for clarity
comment:82 Changed 4 months ago by
Commit:  85fd255aa2df8003505ccce096d5e9baad3bd903 → 2f84a4c93b0d4bd0ba6f4cd888d343e62a489109 

Branch pushed to git repo; I updated commit sha1. New commits:
2f84a4c  src/sage/categories/{sets_cat.py,category_singleton.pyx}: Update doctest output

comment:84 Changed 4 months ago by
Commit:  2f84a4c93b0d4bd0ba6f4cd888d343e62a489109 → aea2ba69af0cdcf7fffa12c13ee042173fb63af1 

Branch pushed to git repo; I updated commit sha1. New commits:
aea2ba6  src/sage/sets/cartesian_product.py: Remove unused import

comment:85 Changed 4 months ago by
Commit:  aea2ba69af0cdcf7fffa12c13ee042173fb63af1 → c91bcfa94e5a54c27238fc2e04c95679f4fff885 

Branch pushed to git repo; I updated commit sha1. New commits:
c91bcfa  src/sage/sets/cartesian_product.py: Add doctest for equality (1 failure)

comment:86 Changed 4 months ago by
Replying to mkoeppe:
when I disabled
UniqueRepresentation
, I also need to disableWithEqualityById
.I agree with this, it needs to be corrected.
sage: from sage.sets.set_from_iterator import EnumeratedSetFromIterator sage: F = EnumeratedSetFromIterator(lambda: iter([1, 2])) sage: F.category() Category of facade enumerated sets sage: cartesian_product([F, F]) is cartesian_product([F, F]) # as intended False sage: cartesian_product([F, F]) == cartesian_product([F, F]) # BUG False
I have added this test (still fails)
comment:87 Changed 4 months ago by
Maybe this is a stupid question, but should that doctest pass? According to the documentation for EnumeratedSetFromIterator
:
 ``category``  (default: ``None``) an optional category for that enumerated set. If you know that your iterator will stop after a finite number of steps you should set it as :class:`FiniteEnumeratedSets`, conversely if you know that your iterator will run over and over you should set it as :class:`InfiniteEnumeratedSets`.
If we use
F = EnumeratedSetFromIterator(lambda: iter([1, 2]), category=FiniteEnumeratedSets())
then the doctest passes. How is it supposed to function if it doesn't know whether the arguments are finite?
comment:88 Changed 4 months ago by
At the moment, there's no code for it because CartesianProduct
just relies on WithEqualityById
.
To give equality to Cartesian products without WithEqualityById
, we could just compare the factors for equality (this is ifandonlyif because no flattening is implemented in our Cartesian products). In the example, the factors are EnumeratedSetFromIterator
, and for these __eq__
just loops to exhaustion to decide equality.
comment:89 Changed 4 months ago by
Commit:  c91bcfa94e5a54c27238fc2e04c95679f4fff885 → 246a158cc3e1c4e87ec9ae2da0a73e30fdb636b7 

Branch pushed to git repo; I updated commit sha1. New commits:
246a158  src/sage/sets/cartesian_product.py: Implement __eq__, __hash__ for nonUniqueRepresentation case (mockup)

comment:90 Changed 4 months ago by
Commit:  246a158cc3e1c4e87ec9ae2da0a73e30fdb636b7 → f7f099c84585ba7bf1b2a722d67a856053f0939b 

Branch pushed to git repo; I updated commit sha1. New commits:
f7f099c  src/sage/sets/cartesian_product.py (CartesianProduct): Factor through new class CartesianProduct_base

comment:91 Changed 4 months ago by
Commit:  f7f099c84585ba7bf1b2a722d67a856053f0939b → 5561d3fb4145516069cdc48f1fe2cf537f13544c 

Branch pushed to git repo; I updated commit sha1. New commits:
5561d3f  Fix comments

comment:92 Changed 4 months ago by
Commit:  5561d3fb4145516069cdc48f1fe2cf537f13544c → 7570978e7bab8af93860db866b2aadec75a1508b 

Branch pushed to git repo; I updated commit sha1. New commits:
7570978  src/sage/sets/cartesian_product.py (CartesianProduct): Factor through new class CartesianProduct_with_element_wrapper

comment:93 Changed 4 months ago by
Replying to tscrim:
Something else to be aware of is elements of
cartesian_product
are actual Sage elements rather thanlist
s. So this could lead to performance regressions. Lots of things use theCFM_tensor
class; all of the Hopf algebras basically. We might want a base or sub class of thecartesian_product
that acts as a façade parent for tuples. So the only difference is essentially in the_element_constructor_
and/or__call__
.
The choice of element class is now set in the subclass CartesianProduct_with_element_wrapper
of CartesianProduct_base
comment:94 Changed 4 months ago by
Commit:  7570978e7bab8af93860db866b2aadec75a1508b → 911b548ff955635a03c75da6652b56b460c857fb 

Branch pushed to git repo; I updated commit sha1. New commits:
911b548  src/sage/sets/cartesian_product.py (CartesianProduct): Dispatch to implementation classes CartesianProduct_eq_by_factors, CartesianProduct_unique

comment:95 Changed 4 months ago by
Work issues:  → Add missing doctests 

comment:96 Changed 4 months ago by
comment:97 Changed 4 months ago by
Commit:  911b548ff955635a03c75da6652b56b460c857fb → 434aaea4fed9738f7108f7bc11f75c1181802f70 

Branch pushed to git repo; I updated commit sha1. New commits:
434aaea  src/sage/combinat/posets/cartesian_product.py: Fixup use of CartesianProduct

comment:98 Changed 4 months ago by
Commit:  434aaea4fed9738f7108f7bc11f75c1181802f70 → 1718618aea48ab99941c7e2bee4348bb15fe88c3 

Branch pushed to git repo; I updated commit sha1. New commits:
1718618  src/sage/sets/cartesian_product.py: Update copyright according to git blame w date=format:%Y FILE  sort k2

comment:101 Changed 4 months ago by
Dependencies:  → #34374 

comment:102 Changed 4 months ago by
Summary:  Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters, use cantor_product for products of infinite sets → Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters 

comment:103 Changed 4 months ago by
Commit:  1718618aea48ab99941c7e2bee4348bb15fe88c3 → 32f227b551a021de34c18ec862bc0327910b5b98 

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
aabcca5  src/sage/sets/cartesian_product.py: Add doctest for equality (1 failure)

6268de8  src/sage/sets/cartesian_product.py: Implement __eq__, __hash__ for nonUniqueRepresentation case (mockup)

ed7ddeb  src/sage/sets/cartesian_product.py (CartesianProduct): Factor through new class CartesianProduct_base

9f16cef  Fix comments

be359bf  src/sage/sets/cartesian_product.py (CartesianProduct): Factor through new class CartesianProduct_with_element_wrapper

7c303cb  src/sage/sets/cartesian_product.py (CartesianProduct): Dispatch to implementation classes CartesianProduct_eq_by_factors, CartesianProduct_unique

e875dd2  src/sage/combinat/posets/cartesian_product.py: Fixup use of CartesianProduct

ca5ee17  src/sage/sets/cartesian_product.py: Update copyright according to git blame w date=format:%Y FILE  sort k2

d7af40f  WIP documentation

32f227b  src/sage/sets/cartesian_product.py: Make MRO consistent

comment:104 Changed 4 months ago by
The MRO errors are gone now, but in the same files I get errors like the following.
File "/Users/mkoeppe/s/sage/sagerebasing/local/var/lib/sage/venvpython3.9/lib/python3.9/sitepackages/sage/structure/unique_representation.py", line 569, in __classcall__ instance = typecall(cls, *args, **options) File "sage/misc/classcall_metaclass.pyx", line 471, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:2380) return (<PyTypeObject*>type).tp_call(cls, args, kwds) File "/Users/mkoeppe/s/sage/sagerebasing/local/var/lib/sage/venvpython3.9/lib/python3.9/sitepackages/sage/rings/asymptotic/growth_group_cartesian.py", line 1444, in __init__ super(UnivariateProduct, self).__init__( File "/Users/mkoeppe/s/sage/sagerebasing/local/var/lib/sage/venvpython3.9/lib/python3.9/sitepackages/sage/rings/asymptotic/growth_group_cartesian.py", line 311, in __init__ CartesianProductPoset.__init__(self, sets, category, order, **kwds) File "/Users/mkoeppe/s/sage/sagerebasing/local/var/lib/sage/venvpython3.9/lib/python3.9/sitepackages/sage/combinat/posets/cartesian_product.py", line 114, in __init__ super().__init__(sets, category, **kwargs) TypeError: __init__() missing 1 required positional argument: 'category'
I think what's happening there is that super().__init__
is being used in a situation where the __init__
methods do not have compatible signatures.
class GenericGrowthGroup(UniqueRepresentation, Parent, WithLocals): def __init__(self, base, category, var): ... class CartesianProduct_base(WithPicklingByInitArgs, Parent): def __init__(self, sets, category, flatten=False): ... class CartesianProductPoset(CartesianProduct_unique): def __init__(self, sets, category, order=None, **kwargs):
comment:105 Changed 4 months ago by
Commit:  32f227b551a021de34c18ec862bc0327910b5b98 → 997cc7cc92bebcb491594ca586eadf5cfc591271 

comment:106 Changed 4 months ago by
Now what remains are lots of infinite recursions involving _element_constructor_
in sage/rings/asymptotic
comment:107 Changed 4 months ago by
Authors:  Frédéric Chapoton, Matthias Koeppe → Frédéric Chapoton, Matthias Koeppe, ... 

Work issues:  Add missing doctests → fix sage.rings.asymptotic 
comment:108 Changed 3 months ago by
Description:  modified (diff) 

comment:109 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

New commits:
work on CartesianProduct_iter