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: sage-9.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:

Status badges

Description (last modified by Matthias Köppe)

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: Meta-ticket: Cleanup cartesian products

Change History (109)

comment:1 Changed 5 years ago by Frédéric Chapoton

Branch: public/19195
Cc: Travis Scrimshaw added; Nathann Cohen removed
Commit: 1eac71e316a1d0c2d854092773bfa12af7330a8d
Dependencies: #18411

New commits:

1eac71ework on CartesianProduct_iter

comment:2 Changed 2 years ago by Matthias Köppe

Milestone: sage-6.9sage-9.3

comment:3 Changed 22 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:4 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:5 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:6 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:7 Changed 4 months ago by Matthias Köppe

Description: modified (diff)

comment:8 Changed 4 months ago by Matthias Köppe

Summary: Make tensor of CombinatorialFreeModule use cartesian_productMake tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters

comment:9 Changed 4 months ago by Matthias Köppe

Description: modified (diff)

comment:10 Changed 4 months ago by git

Commit: 1eac71e316a1d0c2d854092773bfa12af7330a8d75bf2bded5dec0e3d13f929b7a936b0a9e8d18fb

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

75bf2bdwork on CartesianProduct_iter

comment:11 Changed 4 months ago by Matthias Köppe

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 Matthias Köppe

Description: modified (diff)

comment:13 Changed 4 months ago by git

Commit: 75bf2bded5dec0e3d13f929b7a936b0a9e8d18fb2d81aa8abd59adadff4a1d48a281f8da9450d12f

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

2d81aa8src/sage/combinat/cartesian_product.py: Deprecate CartesianProduct_iters

comment:14 Changed 4 months ago by Matthias Köppe

Authors: Frédéric Chapoton, Matthias Koeppe

comment:15 in reply to:  11 Changed 4 months ago by Matthias Köppe

Cc: Lorenz Panny added

Replying to mkoeppe:

    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]

Related recent discussion in #33287

comment:16 Changed 4 months ago by Matthias Köppe

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

Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:17 Changed 4 months ago by Matthias Köppe

Cc: Vincent Delecroix added

comment:18 in reply to:  16 Changed 4 months ago by Matthias Köppe

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 sums-of-ranks).

Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:19 Changed 4 months ago by git

Commit: 2d81aa8abd59adadff4a1d48a281f8da9450d12f8017fed68ac3df9ca4cd5e8a2f3bfcdc3df17615

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

8017fedSets.CartesianProducts.ParentMethods.__iter__: Use cantor_product if factors other than first are infinite

comment:20 Changed 4 months ago by git

Commit: 8017fed68ac3df9ca4cd5e8a2f3bfcdc3df1761597a381b413421e69f19d0a8ff995259b0d5bea14

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

97a381bSets.CartesianProducts.ParentMethods.__iter__: Use cantor_product if factors other than first are infinite

comment:21 Changed 4 months ago by git

Commit: 97a381b413421e69f19d0a8ff995259b0d5bea14ea7af8b2c9174ad4ac80b0ffd12a9d563094e96b

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

ea7af8bsrc/sage/combinat/free_module.py: Update doctests

comment:22 Changed 4 months ago by Matthias Köppe

Doctest failures in 2 files remain:

sage -t --long --random-seed=231229664758049651431332547293032544509 src/sage/algebras/steenrod/steenrod_algebra.py  # Timed out
sage -t --long --random-seed=231229664758049651431332547293032544509 src/sage/homology/hochschild_complex.py  # 10 doctests failed
Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:23 Changed 4 months ago by git

Commit: ea7af8b2c9174ad4ac80b0ffd12a9d563094e96b6e8127049cb0014d574db6c3b39615cdac8128d0

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

6e81270src/sage/homology/hochschild_complex.py: Update doctest output (an_element changed)

comment:24 Changed 4 months ago by Matthias Köppe

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 Matthias Köppe

Summary: Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_itersMake tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters, use cantor_product for products of infinite sets

comment:26 Changed 4 months ago by Matthias Köppe

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'>
Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:27 Changed 4 months ago by Matthias Köppe

This equality test is needed by the UniqueRepresentation behavior of sage.sets.cartesian_product.CartesianProduct

comment:28 Changed 4 months ago by John Palmieri

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 1376-8).

comment:29 Changed 4 months ago by Matthias Köppe

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 John Palmieri

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 Matthias Köppe

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/sage-rebasing/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/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 Matthias Köppe

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 git

Commit: 6e8127049cb0014d574db6c3b39615cdac8128d02a17576cdff070ab24e22cd5c317987e701e1071

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

2a17576LazyFamily.__eq__: Check hashes first, then check repr, then check the possibly infinite set of keys

comment:34 Changed 4 months ago by Matthias Köppe

This fixes the comparison in comment:31, but not the original problem

comment:35 Changed 4 months ago by Matthias Köppe

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/sage-rebasing/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/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:36 Changed 4 months ago by John Palmieri

Right, these sets of keys are the same.

comment:37 Changed 4 months ago by John Palmieri

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 Matthias Köppe

The latest change was for LazyFamily, not for EnumeratedSetFromIterator.

comment:39 Changed 4 months ago by Matthias Köppe

EnumeratedSetFromIterator does not look at names; __eq__ is equality as sets

comment:40 Changed 4 months ago by John Palmieri

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): 
    297297            True
    298298        """
    299299        if isinstance(other, EnumeratedSetFromIterator):
     300            if repr(self) != repr(other):
     301                return False
    300302            # trick to allow equality between infinite sets
    301303            # this assume that the function does not return randomized data!
    302304            if (self._func == other._func and

comment:41 Changed 4 months ago by Matthias Köppe

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 John Palmieri

They have a "name" attribute already; we could use that. Edit: a "name" argument, not an attribute.

Last edited 4 months ago by John Palmieri (previous) (diff)

comment:43 Changed 4 months ago by John Palmieri

Of course that boils down to use repr.

comment:44 Changed 4 months ago by John Palmieri

  • 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): 
    297297            True
    298298        """
    299299        if isinstance(other, EnumeratedSetFromIterator):
     300            if hasattr(self, '__custom_name') or hasattr(other, '__custom_name'):
     301                if repr(self) != repr(other):
     302                    return False
    300303            # trick to allow equality between infinite sets
    301304            # this assume that the function does not return randomized data!
    302305            if (self._func == other._func and

comment:45 Changed 4 months ago by Matthias Köppe

I think this is too dangerous, it's breaking the extensionality of sets

comment:46 Changed 4 months ago by Matthias Köppe

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 git

Commit: 2a17576cdff070ab24e22cd5c317987e701e1071377d0bfc11130123c21a686f21325d4581ffb774

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

377d0bfsrc/sage/sets/cartesian_product.py: Do not use UniqueRepresentation when a factor is an EnumeratedSetFromIterator

comment:48 Changed 4 months ago by Matthias Köppe

This fixes comment:29. Haven't checked yet if it breaks anything

comment:49 Changed 4 months ago by John Palmieri

This produces a lot of doctest failures:

sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/asymptotic_expansion_generators.py  # 86 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/symbolic/expression.pyx  # 3 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/doctest/forker.py  # 3 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/homology/hochschild_complex.py  # 2 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/categories/pushout.py  # 6 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/asymptotic_ring.py  # 236 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/algebras/hecke_algebras/ariki_koike_algebra.py  # 13 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/term_monoid.py  # 99 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/algebras/askey_wilson.py  # 2 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/growth_group.py  # 114 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/combinat/root_system/extended_affine_weyl_group.py  # 404 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/rings/asymptotic/growth_group_cartesian.py  # 118 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/symbolic/ring.pyx  # 5 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/categories/sets_cat.py  # 2 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/algebras/schur_algebra.py  # 1 doctest failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/categories/magmas.py  # 4 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/doc/en/thematic_tutorials/lie/affine.rst  # 1 doctest failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/groups/group_semidirect_product.py  # 35 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/sets/family.py  # 3 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/rings/big_oh.py  # 2 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/sets/cartesian_product.py  # 2 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/combinat/posets/cartesian_product.py  # 48 doctests failed
sage -t --long --random-seed=269458505477710295233910752449959854719 src/sage/combinat/cartesian_product.py  # 2 doctests failed

comment:50 Changed 4 months ago by git

Commit: 377d0bfc11130123c21a686f21325d4581ffb7746d5f261a6e6cfcd8a49b9f5af2ae0bfb21b1201e

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

6d5f261src/sage/sets/cartesian_product.py: Do not use UniqueRepresentation when a factor is an EnumeratedSetFromIterator

comment:51 Changed 4 months ago by Matthias Köppe

Here's a simpler version that also creates such failures

comment:52 Changed 4 months ago by John Palmieri

But hey, no failures in algebras/steenrod, homology, or topology, so it's all good with me. ;)

comment:53 Changed 4 months ago by Matthias Köppe

OK some of the failures were already present in 2a17576 (comment:33)

comment:54 Changed 4 months ago by git

Commit: 6d5f261a6e6cfcd8a49b9f5af2ae0bfb21b1201ee9694481061f271fbbedd3434629568ccf0b5928

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

e969448LazyFamily.__eq__: Check hashes of the index sets only, not the hashes of self, other

comment:55 Changed 4 months ago by John Palmieri

I'm still seeing a lot of error messages of the form

File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.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 Matthias Köppe

https://github.com/sagemath/sagetrac-mirror/actions/runs/2850051513 only sees the error in steenrod with e969448

comment:57 Changed 4 months ago by Matthias Köppe

Note I backed out 6d5f261

comment:58 Changed 4 months ago by git

Commit: e9694481061f271fbbedd3434629568ccf0b59283de34ae68444f6a883a9e268f34f792e38042e0c

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

3de34aesrc/sage/sets/cartesian_product.py: Do not use UniqueRepresentation when a factor is an EnumeratedSetFromIterator

comment:59 Changed 4 months ago by Matthias Köppe

OK here's a better version of the same approach, it passes all tests for me

comment:60 Changed 4 months ago by git

Commit: 3de34ae68444f6a883a9e268f34f792e38042e0cc30e0da0df8e6798f78704876b3f636097f32dfa

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

c30e0dasrc/sage/sets/cartesian_product.py: Do use UniqueRepresentation when sets are finite; add tests

comment:61 Changed 4 months ago by Matthias Köppe

Status: newneeds_review

comment:62 Changed 4 months ago by git

Commit: c30e0da0df8e6798f78704876b3f636097f32dfa1c303121d6e407fd0906f745826fc37b4db3bf58

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

1c30312src/sage/categories/sets_cat.py: Update documentation - cantor_product refines with revlex

comment:63 Changed 4 months ago by Travis Scrimshaw

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 Rn) 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 lists. 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 in reply to:  63 ; Changed 4 months ago by Matthias Köppe

Replying to tscrim:

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.

No, the repr comparison was already in the old method. It's only reordered.

comment:65 in reply to:  63 ; Changed 4 months ago by Matthias Köppe

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
Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:66 Changed 4 months ago by Matthias Köppe

Status: needs_reviewneeds_work

comment:67 in reply to:  64 ; Changed 4 months ago by Travis Scrimshaw

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) 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.

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 in reply to:  63 Changed 4 months ago by Matthias Köppe

Replying to tscrim:

I am wondering why we did not put EnumeratedSets().CartesianProducts() in the category of EnumeratedSets(). We might want to do this

+1

comment:69 in reply to:  65 ; Changed 4 months ago by Travis Scrimshaw

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 disable WithEqualityById.

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 in reply to:  67 Changed 4 months ago by Matthias Köppe

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 in reply to:  69 ; Changed 4 months ago by Matthias Köppe

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 Changed 4 months ago by git

Commit: 1c303121d6e407fd0906f745826fc37b4db3bf58278b7c7ec6eccc9125cd4066c15c3c16268b1382

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

278b7c7src/sage/categories/enumerated_sets.py: Make (finitary) Cartesian products of enumerated enumerated

comment:73 Changed 4 months ago by Matthias Köppe

Here's the fix for the category

comment:74 in reply to:  71 ; Changed 4 months ago by Travis Scrimshaw

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 in reply to:  72 Changed 4 months ago by Matthias Köppe

Replying to git:

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

278b7c7src/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/sagetrac-mirror/sagetrac-mirror/src/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/__w/sagetrac-mirror/sagetrac-mirror/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/sagetrac-mirror/sagetrac-mirror/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 Matthias Köppe

Let's do these category improvements in a separate ticket, #34356.

comment:77 Changed 4 months ago by git

Commit: 278b7c7ec6eccc9125cd4066c15c3c16268b13821c303121d6e407fd0906f745826fc37b4db3bf58

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

comment:78 Changed 4 months ago by git

Commit: 1c303121d6e407fd0906f745826fc37b4db3bf58d132fb7f0808b421988bfccc9672038707ca960d

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

ef18d05src/sage/structure/unique_representation.py: Refactor CachedRepresentation through new class WithPicklingByInitArgs
d132fb7src/sage/sets/cartesian_product.py: Remove code duplication

comment:79 in reply to:  74 Changed 4 months ago by Matthias Köppe

Replying to tscrim:

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.

Actually, not even a CachedRepresentation. I've now introduced a new class WithPicklingByInitArgs, which CachedRepresentation subclasses.

comment:80 Changed 4 months ago by git

Commit: d132fb7f0808b421988bfccc9672038707ca960d85fd255aa2df8003505ccce096d5e9baad3bd903

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

85fd255src/sage/categories/sets_cat.py: Rephrase cartesian product docstring

comment:81 in reply to:  63 Changed 4 months ago by Matthias Köppe

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 git

Commit: 85fd255aa2df8003505ccce096d5e9baad3bd9032f84a4c93b0d4bd0ba6f4cd888d343e62a489109

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

2f84a4csrc/sage/categories/{sets_cat.py,category_singleton.pyx}: Update doctest output

comment:83 Changed 4 months ago by John Palmieri

Passes tests for me.

comment:84 Changed 4 months ago by git

Commit: 2f84a4c93b0d4bd0ba6f4cd888d343e62a489109aea2ba69af0cdcf7fffa12c13ee042173fb63af1

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

aea2ba6src/sage/sets/cartesian_product.py: Remove unused import

comment:85 Changed 4 months ago by git

Commit: aea2ba69af0cdcf7fffa12c13ee042173fb63af1c91bcfa94e5a54c27238fc2e04c95679f4fff885

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

c91bcfasrc/sage/sets/cartesian_product.py: Add doctest for equality (1 failure)

comment:86 in reply to:  65 Changed 4 months ago by Matthias Köppe

Replying to mkoeppe:

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

I have added this test (still fails)

comment:87 Changed 4 months ago by John Palmieri

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 Matthias Köppe

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 if-and-only-if 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.

Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:89 Changed 4 months ago by git

Commit: c91bcfa94e5a54c27238fc2e04c95679f4fff885246a158cc3e1c4e87ec9ae2da0a73e30fdb636b7

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

246a158src/sage/sets/cartesian_product.py: Implement __eq__, __hash__ for non-UniqueRepresentation case (mockup)

comment:90 Changed 4 months ago by git

Commit: 246a158cc3e1c4e87ec9ae2da0a73e30fdb636b7f7f099c84585ba7bf1b2a722d67a856053f0939b

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

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

comment:91 Changed 4 months ago by git

Commit: f7f099c84585ba7bf1b2a722d67a856053f0939b5561d3fb4145516069cdc48f1fe2cf537f13544c

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

5561d3fFix comments

comment:92 Changed 4 months ago by git

Commit: 5561d3fb4145516069cdc48f1fe2cf537f13544c7570978e7bab8af93860db866b2aadec75a1508b

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

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

comment:93 in reply to:  63 Changed 4 months ago by Matthias Köppe

Replying to tscrim:

Something else to be aware of is elements of cartesian_product are actual Sage elements rather than lists. 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__.

The choice of element class is now set in the subclass CartesianProduct_with_element_wrapper of CartesianProduct_base

Last edited 4 months ago by Matthias Köppe (previous) (diff)

comment:94 Changed 4 months ago by git

Commit: 7570978e7bab8af93860db866b2aadec75a1508b911b548ff955635a03c75da6652b56b460c857fb

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

911b548src/sage/sets/cartesian_product.py (CartesianProduct): Dispatch to implementation classes CartesianProduct_eq_by_factors, CartesianProduct_unique

comment:95 Changed 4 months ago by Matthias Köppe

Work issues: Add missing doctests

comment:96 in reply to:  71 Changed 4 months ago by Matthias Köppe

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

I have a clean implementation now

comment:97 Changed 4 months ago by git

Commit: 911b548ff955635a03c75da6652b56b460c857fb434aaea4fed9738f7108f7bc11f75c1181802f70

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

434aaeasrc/sage/combinat/posets/cartesian_product.py: Fixup use of CartesianProduct

comment:98 Changed 4 months ago by git

Commit: 434aaea4fed9738f7108f7bc11f75c1181802f701718618aea48ab99941c7e2bee4348bb15fe88c3

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

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

comment:99 Changed 4 months ago by Matthias Köppe

Some MRO problems in sage/rings/asymptotic

comment:100 Changed 4 months ago by John Palmieri

Yes, I see those, too.

comment:101 Changed 4 months ago by Matthias Köppe

Dependencies: #34374

comment:102 Changed 4 months ago by Matthias Köppe

Summary: Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters, use cantor_product for products of infinite setsMake tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters

comment:103 Changed 4 months ago by git

Commit: 1718618aea48ab99941c7e2bee4348bb15fe88c332f227b551a021de34c18ec862bc0327910b5b98

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

aabcca5src/sage/sets/cartesian_product.py: Add doctest for equality (1 failure)
6268de8src/sage/sets/cartesian_product.py: Implement __eq__, __hash__ for non-UniqueRepresentation case (mockup)
ed7ddebsrc/sage/sets/cartesian_product.py (CartesianProduct): Factor through new class CartesianProduct_base
9f16cefFix comments
be359bfsrc/sage/sets/cartesian_product.py (CartesianProduct): Factor through new class CartesianProduct_with_element_wrapper
7c303cbsrc/sage/sets/cartesian_product.py (CartesianProduct): Dispatch to implementation classes CartesianProduct_eq_by_factors, CartesianProduct_unique
e875dd2src/sage/combinat/posets/cartesian_product.py: Fixup use of CartesianProduct
ca5ee17src/sage/sets/cartesian_product.py: Update copyright according to git blame -w --date=format:%Y FILE | sort -k2
d7af40fWIP documentation
32f227bsrc/sage/sets/cartesian_product.py: Make MRO consistent

comment:104 Changed 4 months ago by Matthias Köppe

The MRO errors are gone now, but in the same files I get errors like the following.

      File "/Users/mkoeppe/s/sage/sage-rebasing/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/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/sage-rebasing/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/asymptotic/growth_group_cartesian.py", line 1444, in __init__
        super(UnivariateProduct, self).__init__(
      File "/Users/mkoeppe/s/sage/sage-rebasing/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/asymptotic/growth_group_cartesian.py", line 311, in __init__
        CartesianProductPoset.__init__(self, sets, category, order, **kwds)
      File "/Users/mkoeppe/s/sage/sage-rebasing/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/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 git

Commit: 32f227b551a021de34c18ec862bc0327910b5b98997cc7cc92bebcb491594ca586eadf5cfc591271

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

46f4bf3src/sage/rings/asymptotic/growth_group_cartesian.py: CartesianProduct -> CartesianProduct_unique
997cc7csrc/sage/rings/asymptotic, src/sage/combinat/posets: Replace some super().__init__ by direct calls

comment:106 Changed 4 months ago by Matthias Köppe

Now what remains are lots of infinite recursions involving _element_constructor_ in sage/rings/asymptotic

comment:107 Changed 4 months ago by Matthias Köppe

Authors: Frédéric Chapoton, Matthias KoeppeFrédéric Chapoton, Matthias Koeppe, ...
Work issues: Add missing doctestsfix sage.rings.asymptotic

comment:108 Changed 3 months ago by Matthias Köppe

Description: modified (diff)

comment:109 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.