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. #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. #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 #18290. Some other are in #18411.
   • #19195: Fix the use of CartesianProduct in CombinatorialFreeModule

2. 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. #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 #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. #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 #18309.

6. 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. #16269 and follow up #16405 (depended on #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.

[vdelecroix]

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

[ncohen]

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]

Replying to ncohen:

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'

[vdelecroix]

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

[vdelecroix]

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)