Meta-ticket: Cleanup cartesian products

[nthiery]

Currently we have: cartesian_product, CartesianProduct and
cartesian_product_iterator for constructing cartesian products.

• CartesianProduct is an old simple parent that focuses on the
  "enumerated sets" aspect: providing counting and enumeration over
  cartesian products of enumerated sets. It accepts any iterables as
  input.

• cartesian_product is a "functorial construction". This means
  that it uses the categories to endow the resulting parent with as
  much structure as it can lift from the input. E.g. the cartesian
  product of two monoids is a monoid.

• cartesian_product_iterator is just a function that provides an
  iterator

To be done:

1. get rid of CartesianProduct #18411: Make CartesianProduct an alias for cartesian_product, and possibly deprecated it. The missing features at this point are:

   • Accepting any iterable as input. This probably requires turning
     them into parents (e.g. with FiniteEnumeratedSet). The overhead
     is probably negligible in most cases, but one would need to double
     check that we don't have spots where CartesianProduct is used
     intensively for very small calculations. cartesian_product AssertionError #14224 can be closed once this is fixed.
   • Some features of CartesianProduct still need to be lifted to
     Sets.Finite.CartesianProducts or EnumeratedSets.CartesianProducts. The
     cardinality and is_finite methods are taken care in enhanced sets and cartesian products #18290. Some other
     are in get rid of CartesianProduct #18411.
   • Make tensor of CombinatorialFreeModule use cartesian_product, deprecate CartesianProduct_iters #19195: Fix the use of CartesianProduct in CombinatorialFreeModule

2. Deprecate sage.misc.mrange.*mrange* and cartesian_product_iterator #34337: Remove cartesian_product_iterator from the global name space, and deprecate it altogether if, after checking, it turns out to be really just a duplicated of itertools.product.

3. Fix ZZ.cartesian_product(...) #16289: Fix bug in cartesian_product (reported by Vincent Delecroix in this thread):

   sage: C = cartesian_product([ZZ,ZZ])
   ...
   AttributeError: type object 'sage.rings.integer_ring.IntegerRing_class' has no attribute 'CartesianProduct'
   

   This is a regression that is caused by a small change introduced by
   Improvements to Sets.WithRealizations #12959 in Sets.ParentMethods.CartesianProduct:

       return parents[0].__class__ -> return parents[0].__class__
   

   I (Nicolas) take a double blame for it: I was reviewer of this ticket
   and did not notice this chunk (or don't remember why it was
   introduced), and I had not written an appropriate test in the first
   place. So this needs to be fixed too.

4. Cartesian Products of additive groups #16269: Fix bug reported by Nathann Cohen in this thread: when converting a
   list to an element of a cartesian product:

   sage: Z3 = IntegerModRing(3)
   sage: C = cartesian_product([Z3,Z3])
   sage: C([Z3(2),Z3(2)])^2
   (1, 1)
   sage: C([2,2])^2   # Ooops
   (4, 4)
   

   The fix would be convert the operands of the list into the respective
   parents in
   sage.sets.cartesian_product.CartesianProduct._element_constructor.

5. Fix mixed cartesian products with modules and non modules:

   sage: A = AlgebrasWithBasis(QQ).example(); A.rename("A")
   sage: cartesian_product([A, ZZ])
   ...
   AttributeError: 'sage.rings.integer_ring.IntegerRing_class' object has no attribute 'basis'
   

   This should instead detect that not all factors are modules, and
   just use a plain cartesian product.

   Also between modules on different ring, in particular Categories are wrong for Hom/cartesian products of vector spaces #18309.

6. Import NN directly rather than lazily throughout the Sage library #34652: Fix cartesian products involving NN:

   sage: cartesian_product([NN,NN])
   170         from sage.structure.parent import Parent
   --> 171         assert(all(isinstance(parent, Parent) for parent in parents))
   172         # Should we pass a set of categories to reduce the cache size?
   173         # But then this would impose that, for any constructor, the
   AssertionError: 
   

   This is in fact a bug in the way NN is lazy imported in the global
   name space:

       sage: type(NN)
   <type 'sage.misc.lazy_import.LazyImport'>
   sage: isinstance(NN, Parent)
       False
   

   Things works if one forces the import of NN:

   sage: NN = NonNegativeIntegers()
   sage: cartesian_product([NN,NN])
   The cartesian product of (Non negative integers, Non negative integers)
   

7. Make _cartesian_product_of_elements a public method?

8. Add a tutorial in Sets.SubcategoryMethods.CartesianProducts
   describing the general scheme, possibly starting from the blurb there:
   https://groups.google.com/d/msg/sage-combinat-devel/s_aPBD6BgOg/H1aJbCI1TYoJ

9. Tidy up the documentation of sage.sets.cartesian_products:
   Return(s), the links to Sets.... don't need to be prefixed with
   the python module (Sets is found from the global name space), ...

10. Cartesian Products of additive groups #16269 and follow up Cartesian product of rings #16405 (depended on Axioms and more functorial constructions #10963): make the
    cartesian product of an additive magma into an additive magma, and
    so on; implement Distributive.CartesianProducts so that a
    cartesian product of rings is a ring.

CC: @sagetrac-sage-combinat @nathanncohen @videlec @tscrim

Component: categories

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

[videlec]

comment:4

Hello,

+1 on that ticket!

I cleaned a bit the description.

I think it is bad to hide cartesian_product_iterator as the object is very nice. We should advertise the product from itertools somewhere.

Vincent

[nathanncohen]

comment:5

I think it is bad to hide cartesian_product_iterator as the object is very nice. We should advertise the product from itertools somewhere.

We could mention it in the docstring of cartesian_product. "If you just want to list the elements, use itertools.product as it is much faster" ?

[nthiery]

comment:6

Replying to @nathanncohen:

I think it is bad to hide cartesian_product_iterator as the object is very nice. We should advertise the product from itertools somewhere.

We could mention it in the docstring of cartesian_product. "If you just want to list the elements, use itertools.product as it is much faster" ?

Sounds good to me, with 'list -> iterate through'

[videlec]

comment:13

Hello,

I think that we should get rid of _cartesian_product_of_elements. If we want speed we can either:

• add an argument coerce to the _element_constructor_
• use directly element_class

Vincent

[videlec]

comment:14

Shouldn't the two following commands give the same answer

sage: ZZ**2
Ambient free module of rank 2 over the principal ideal domain Integer Ring
sage: cartesian_product([ZZ,ZZ])
The cartesian product of (Integer Ring, Integer Ring)

[mkoeppe]

comment:20

Bugs 5 and 6 are still present in 9.7.beta8

[mkoeppe]

comment:22

Bug 6 was fixed in #34652