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

[nthiery]

Description changed:

--- 
+++ 
@@ -14,74 +14,80 @@
 - `cartesian_product_iterator` is just a function that provides an
   iterator
 
-`cartesian_product` is meant to subdue `CartesianProduct`. The
-missing features at this point are:
+To be done:
 
-- 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.
+#.  Make `CartesianProduct` an alias for `cartesian_product`,
+    and possibly deprecated it.
 
-  #14224 which can be closed once this is fixed.
+    The missing features at this point are:
 
-- Some features of CartesianProduct still need to be lifted to
-  Sets.Finite.CartesianProducts or EnumeratedSets.CartesianProducts.
-  For example, cardinality is currently calculated from the iterator (gasp):
+    - 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.
 
-  ```
-      sage: F = Permutations(10)
-      sage: C = cartesian_product([F,F])
-      sage: C.cardinality()
-      *hangs forever*
-  ```
+      #14224 can be closed once this is fixed.
 
-Once this is done, we can make CartesianProduct an alias for
-cartesian_product, and maybe deprecate it in the long run.
+    - Some features of CartesianProduct still need to be lifted to
+      Sets.Finite.CartesianProducts or EnumeratedSets.CartesianProducts.
+      For example, cardinality is currently calculated from the iterator (gasp):
 
-My 2 cents for cartesian_product_iterator: it should be removed from
-the global name space, and deprecated altogether if after checking it
-turns out to be really just a duplicated of itertools.product.
+      ```
+   	  sage: F = Permutations(10)
+   	  sage: C = cartesian_product([F,F])
+   	  sage: C.cardinality()
+   	  *hangs forever*
+      ```
 
-Another bug in cartesian_product (reported by Vincent Delecroix [1]):
+      Done by #16269/#10963 for cardinality and `__iter__`. Needs
+      double checking for the infinite cases.
 
-```
-sage: C = cartesian_product([ZZ,ZZ])
-...
-AttributeError: type object 'sage.rings.integer_ring.IntegerRing_class' has no attribute 'CartesianProduct'
-```
+#.  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.
 
-This is a regression that is caused by a small change introduced by
-#12959 in Sets.ParentMethods.CartesianProduct:
+#.  Fix bug in cartesian_product (reported by Vincent Delecroix [1]):
 
-```
-            return parents[0].__class__ -> return parents[0].__class__
-```
+    ```
+    sage: C = cartesian_product([ZZ,ZZ])
+    ...
+    AttributeError: type object 'sage.rings.integer_ring.IntegerRing_class' has no attribute 'CartesianProduct'
+    ```
 
-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.
+    This is a regression that is caused by a small change introduced by
+    #12959 in Sets.ParentMethods.CartesianProduct:
 
-Yet another bug reported by Nathann Cohen [2]: when converting a list
-to an element of a cartesian product:
+    ```
+  		return parents[0].__class__ -> return parents[0].__class__
+    ```
 
-```
-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)
-```
+    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.
 
-The fix would be convert the operands of the list into the respective
-parents in
-`sage.sets.cartesian_product.CartesianProduct._element_constructor`.
+#.  #16269: Fix bug reported by Nathann Cohen [2]: when converting a
+    list to an element of a cartesian product:
 
-Many features could be further added, like for example making the
-cartesian product of an additive magma into an additive magma and so
-on. This can go in this ticket or in later tickets.
+    ```
+    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`.
+
+#.  Many features could be further added, like for example making the
+    cartesian product of an additive magma into an additive magma and
+    so on. A good step was done with #16269. Another step needs to be
+    done after #10963 to ventilate the features in the appropriate
+    axiom categories.
 
 [1] https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M
 [2] https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J

[nthiery]

Description changed:

--- 
+++ 
@@ -47,7 +47,7 @@
     deprecate it altogether if, after checking, it turns out to be
     really just a duplicated of itertools.product.
 
-#.  Fix bug in cartesian_product (reported by Vincent Delecroix [1]):
+#.  #16289: Fix bug in cartesian_product (reported by Vincent Delecroix [1]):
 
     ```
     sage: C = cartesian_product([ZZ,ZZ])
@@ -83,11 +83,50 @@
     parents in
     `sage.sets.cartesian_product.CartesianProduct._element_constructor`.
 
+#.  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.
+
+#.  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)
+    ```
+
+
 #.  Many features could be further added, like for example making the
-    cartesian product of an additive magma into an additive magma and
+    cartesian product of an additive magma into an additive magma, and
     so on. A good step was done with #16269. Another step needs to be
     done after #10963 to ventilate the features in the appropriate
-    axiom categories.
+    axiom categories, and add Distributive.CartesianProducts.
 
 [1] https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M
 [2] https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J

[videlec]

Description changed:

--- 
+++ 
@@ -16,38 +16,25 @@
 
 To be done:
 
-#.  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.
-      For example, cardinality is currently calculated from the iterator (gasp):
+1.  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`. For example, cardinality is currently calculated from the iterator (gasp):
 
       ```
-   	  sage: F = Permutations(10)
-   	  sage: C = cartesian_product([F,F])
-   	  sage: C.cardinality()
-   	  *hangs forever*
+          sage: F = Permutations(10)
+          sage: C = cartesian_product([F,F])
+          sage: C.cardinality()
+          *hangs forever*
       ```
+      Done by #16269/#10963 for cardinality and `__iter__`. Needs double checking for the infinite and zero cases.
 
-      Done by #16269/#10963 for cardinality and `__iter__`. Needs
-      double checking for the infinite cases.
+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`.
 
-#.  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.
-
-#.  #16289: Fix bug in cartesian_product (reported by Vincent Delecroix [1]):
+3.  #16289: Fix bug in cartesian_product (reported by Vincent Delecroix in [this thread](https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M)):
 
     ```
     sage: C = cartesian_product([ZZ,ZZ])
@@ -56,7 +43,7 @@
     ```
 
     This is a regression that is caused by a small change introduced by
-    #12959 in Sets.ParentMethods.CartesianProduct:
+    #12959 in `Sets.ParentMethods.CartesianProduct`:
 
     ```
   		return parents[0].__class__ -> return parents[0].__class__
@@ -67,7 +54,7 @@
     introduced), and I had not written an appropriate test in the first
     place. So this needs to be fixed too.
 
-#.  #16269: Fix bug reported by Nathann Cohen [2]: when converting a
+4.  #16269: Fix bug reported by Nathann Cohen in [this thread](https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J): when converting a
     list to an element of a cartesian product:
 
     ```
@@ -83,7 +70,7 @@
     parents in
     `sage.sets.cartesian_product.CartesianProduct._element_constructor`.
 
-#.  Fix mixed cartesian products with modules and non modules:
+5.  Fix mixed cartesian products with modules and non modules:
 
     ```
     sage: A = AlgebrasWithBasis(QQ).example(); A.rename("A")
@@ -94,7 +81,7 @@
     This should instead detect that not all factors are modules, and
     just use a plain cartesian product.
 
-#.  Fix cartesian products involving NN:
+6.  Fix cartesian products involving `NN`:
 
     ```
    	sage: cartesian_product([NN,NN])
@@ -104,7 +91,7 @@
    	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
+    This is in fact a bug in the way `NN` is lazy imported in the global
     name space:
 
     ```
@@ -113,7 +100,7 @@
    	sage: isinstance(NN, Parent)
            False
     ```
-    Things works if one forces the import of NN:
+    Things works if one forces the import of `NN`:
 
     ```
    	sage: NN = NonNegativeIntegers()
@@ -122,12 +109,4 @@
     ```
 
 
-#.  Many features could be further added, like for example making the
-    cartesian product of an additive magma into an additive magma, and
-    so on. A good step was done with #16269. Another step needs to be
-    done after #10963 to ventilate the features in the appropriate
-    axiom categories, and add Distributive.CartesianProducts.
-
-[1] https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M
-[2] https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J
-
+7.  Many features could be further added, like for example making the cartesian product of an additive magma into an additive magma, and so on. A good step was done with #16269. Another step needs to be done after #10963 to ventilate the features in the appropriate axiom categories, and add `Distributive.CartesianProducts`.

[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'

[nthiery]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Currently we have: `cartesian_product`, `CartesianProduct` and
+eCurrently we have: `cartesian_product`, `CartesianProduct` and
 `cartesian_product_iterator` for constructing cartesian products.
 
 - `CartesianProduct` is an old simple parent that focuses on the
@@ -108,5 +108,17 @@
    	The cartesian product of (Non negative integers, Non negative integers)
     ```
 
+8.  Make `_cartesian_product_of_elements` a public method?
 
-7.  Many features could be further added, like for example making the cartesian product of an additive magma into an additive magma, and so on. A good step was done with #16269. Another step needs to be done after #10963 to ventilate the features in the appropriate axiom categories, and add `Distributive.CartesianProducts`.
+9.  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
+
+7.  Many features could be further added, like for example making the
+    cartesian product of an additive magma into an additive magma, and
+    so on. A good step was done with #16269. Another step needs to be
+    done after #10963 to ventilate the features in the appropriate
+    axiom categories, and implement
+    `Distributive.CartesianProducts` so that a cartesian product
+    of rings would be a ring.
+

[nthiery]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-eCurrently we have: `cartesian_product`, `CartesianProduct` and
+Currently we have: `cartesian_product`, `CartesianProduct` and
 `cartesian_product_iterator` for constructing cartesian products.
 
 - `CartesianProduct` is an old simple parent that focuses on the
@@ -108,13 +108,17 @@
    	The cartesian product of (Non negative integers, Non negative integers)
     ```
 
-8.  Make `_cartesian_product_of_elements` a public method?
+7.  Make `_cartesian_product_of_elements` a public method?
 
-9.  Add a tutorial in `Sets.SubcategoryMethods.CartesianProducts`
+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
 
-7.  Many features could be further added, like for example making the
+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. Many features could be further added, like for example making the
     cartesian product of an additive magma into an additive magma, and
     so on. A good step was done with #16269. Another step needs to be
     done after #10963 to ventilate the features in the appropriate