Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters

[videlec]

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. #18411 comment:24). This is addressed in #18750

This will solve #18849 and probably #24900.

Part of #15425: Meta-ticket: Cleanup cartesian products

Depends on #34374

CC: @nthiery @tscrim @yyyyx4 @videlec @jhpalmieri

Component: combinatorics

Work Issues: fix sage.rings.asymptotic

Author: Frédéric Chapoton, Matthias Koeppe, ...

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

[fchapoton]

Commit: 1eac71e

[fchapoton]

Branch: public/19195

[fchapoton]

Changed dependencies from #18411 to none

[fchapoton]

New commits:

1eac71e

work on CartesianProduct_iter

[mkoeppe]

comment:3

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

[sagetrac-git]

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

75bf2bd

work on CartesianProduct_iter

[sagetrac-git]

Changed commit from 1eac71e to 75bf2bd

[mkoeppe]

comment:11

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]

[sagetrac-git]

Changed commit from 75bf2bd to 2d81aa8

[sagetrac-git]

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

2d81aa8

src/sage/combinat/cartesian_product.py: Deprecate CartesianProduct_iters

[mkoeppe]

Author: Frédéric Chapoton, Matthias Koeppe

[mkoeppe]

comment:15

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

[jhpalmieri]

comment:100

Yes, I see those, too.

[mkoeppe]

Dependencies: #34374

[sagetrac-git]

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 non-UniqueRepresentation 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

[sagetrac-git]

Changed commit from 1718618 to 32f227b

[mkoeppe]

comment:104

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

[sagetrac-git]

Changed commit from 32f227b to 997cc7c

[sagetrac-git]

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

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

[mkoeppe]

comment:106

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

[mkoeppe]

Changed work issues from Add missing doctests to fix sage.rings.asymptotic

[mkoeppe]

Changed author from Frédéric Chapoton, Matthias Koeppe to Frédéric Chapoton, Matthias Koeppe, ...

[mkoeppe]

Removed branch from issue description; replaced by PR #35282

[mantepse]

comment:106

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

I had a brief look. One symptom is that in line

sage/src/sage/rings/asymptotic/growth_group.py

Line 2234 in 0c390a0

raw_element = self._convert_(data)

self._convert_ is referring to <bound method GenericGrowthGroup._convert_ of Growth Group x^ZZ * y^ZZ> (the abstract method) instead of <bound method MonomialGrowthGroup._convert_ of Growth Group x^ZZ>.

I noticed that several super calls have been replaced with calls to the class inheriting from, eg.

sage/src/sage/combinat/posets/cartesian_product.py

Line 114 in 0c390a0

super().__init__(sets, category, **kwargs)

was replaced with CartesianProduct_unique.__init__(self, sets, category, **kwargs). I don't know super so well, might this be the source of the problem?