get rid of CartesianProduct

[videlec]

The features of sage.combinat.cartesian_product.CartesianProduct are now completely integrated into the category framework (see #18290). We remove all occurrences of CartesianProduct to either cartesian_product or itertools.product. We deprecate the CartesianProduct from sage.combinat.cartesian_product.

In order to support all features of the old class we also:

• move the __iter__ from EnumeratedSets.CartesianProducts.ParentMethods to Sets.CartesianProducts.ParentMethods
• allows cartesian_product to be called with list, tuple, set, frozenset
• make cartesian_product([]) works
• introduce a function some_tuples in sage.misc.misc that is intensively used in the testing framework (and incidentally speed up some doc test)
• refine the category of Set([1,2,3]) to be finite
• implement a (very naive) random_element for Set([1,2,3])
• implement a (naive) hash for EnumeratedSetFromIterator

see also : #15425, #19195 one that can be closed as duplicate: #14224, #19192

Depends on #17411

CC: @nthiery @nathanncohen

Component: combinatorics

Author: Vincent Delecroix

Branch/Commit: 6e27dde

Reviewer: Nicolas M. Thiéry

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3661ec0	Trac 18411: more explicit error catch in sets_cat
7d12709	Trac 18411: composition: FiniteEnumeratedSet instead of Set
35b76c6	Trac 18411: simpler code in root_lattice_realizations.py
643e2f7	Trac 18411: restore some tests in family.py
6f7b379	Trac 18411: use itertools.product instead of product
2741384	Trac 18411: small edits in combinat/tutorial.py
ca0a907	Trac 18411: explanations about the transition

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e7a2ff2 to ca0a907

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ca0a907 to 34a392f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9978ba2	Trac 18411: more spaces in categories/rings.py
34a392f	Trac 18411: the empty cartesian product

[videlec]

Description changed:

--- 
+++ 
@@ -3,6 +3,7 @@
 In order to support all features of the old class we also:
 - move the `__iter__` from `EnumeratedSets.CartesianProducts.ParentMethods` category to `Sets`
 - allows `cartesian_product` to be called with `list`, `tuple`, `set`, `frozenset`
+- make `cartesian_product([])` works
 - introduce a function `bounded_number_of_tuples` in `sage.misc.misc` that is intensively used in the testing framework
 - refine the category of `Set([1,2,3])` to be finite
 - implement a (very naive) `random_element` for `Set([1,2,3])`

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

07cc001

18411: Fixed unused import

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 34a392f to 07cc001

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7c103df

18411: cleanup spacing for optional arguments

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 07cc001 to 7c103df

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7c103df to a35ef8a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a35ef8a

18411: proofreading

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

22f8b77

18411: proofreading

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a35ef8a to 22f8b77

[nthiery]

comment:38

Here is a trace of the non trivial points we discussed privately with Vincent:

• enumerated_set_from_iterator: do we want instead to start filling the cache in case it does not exist yet?

Nope. The cache might be never used in that class. And when it exists it is automatically filled since it is a lazy_list.

Oh, I had not noticed that, in EnumeratedSetFromIterator, the existence of the cache was decided upon construction. +1 then.

• Why moving __iter__ from EnumeratedSets.CartesianProducts to Sets.CartesianProducts?

Because otherwise there are some failing doctests. For example Set([1,2,3]) is iterable but the following was not cartesian_product([Set(1,2,3), Set([1,2,3])])

The fact that something is iterable does not necessarily mean that it belongs to EnumeratedSet. At least for me and the current class FiniteEnumeratedSet, the enumerated set {1, 2, 3} is not equal to the enumerated set {3, 2, 1}. But they are equal as sets. And the set {1, 2, 3} should be iterable.

I see your point. Yet this is annoying; where do we want to put the exact limit between Set and EnumeratedSet? Where should, e.g. features like cardinality_from_iterator live?

Hmm, I am not sure what to do here.

Right. My main motivation was to fix some doctests were previous code expected that the result was iterable. I do not exactly remind where it was.

Would it make sense to put it in Sets.Finite.CartesianProduct, given that it only works in the finite case?

The iterator is mandatory for cardinality_from_iterator, as it is not for Sets I would not put there.

Yeah, that's a good point.

• Do we want to systematically use itertools.product when in some cases it's memory complexity is not as good as what we can do when we have iterables and not iterators as input?

Clearly not. But we are lacking something better. Once the list is expanded, you can not beat itertools. So in most cases, it is what you want since the size of factors is small compared to the size of the product.

• Sets 2034: is_empty: - don't catch all exceptions - is it about parents not implementing is_empty, or about returning Unknown or raising an exception? In which case we should specify that exception and only catch that one.

done

• CartesianProduct_iters: Make the difference with cartesian_product more explicit and add a link?

done

• Compositions: return FiniteEnumeratedSet([self])

done

or make cartesian_product() return FiniteEnumeratedSet([xxx]) or Set([xxx]) where xxx is the trivial tuple.

This is not a good idea. The interface should be uniform when you do elt[i] to access the i-th cartesian projection.

• partition_tuple: could there not be other combinations, like (())?

I did not found any. The empty tuple comes from the iteration with product.

• root_lattice_realization: is the conversion to FiniteEnumeratedSet still necessary?

C = cartesian_product([PositiveIntegers(),
FiniteEnumeratedSet(Q.roots())])

If so, should instead cartesian_product do more input tidying work?

Indeed, it is not. done.

• sets.family: maybe that test was about checking that things work when a parent C is just in EnumeratedSets but C.cardinality() == infinity

I reintroduced the test using cartesian_product instead of CartesianProduct

... about cartesian_product() ...

So what about returning:

         sage: from sage.sets.cartesian_product import CartesianProduct
         sage: CartesianProduct((), Sets().CartesianProducts())
         The cartesian product of ()

I vaguely remember we discussed this at some point, but don't remember what the outcome was. Of course if the user did not specify a category to cartesian_product(), we don't quite know what's the category he expects, but Sets().CartesianProducts() sounds like a reasonable starting point.

I also remember that we discussed it. And indeed, for the sake of backward compatibility it needs to be done in that ticket... we had

sage: CartesianProduct()
Cartesian product of
sage: CartesianProduct().cardinality()
1
sage: CartesianProduct().an_element()
[]

There is an other commit for that.

Thanks!

I made some minor review changes. Since the spacing commit for the tutorial was going the wrong way w.r.t. Python's convention, I allowed myself to revert it, and actually fix accordingly the surrounding lines (which I had written incorrectly a couple years ago). I hope that's ok.

Up to the final position of the __iter__ method which I am not yet quite comfortable with, I am happy with the current state.

Anyone a point of view on this final sticking point?

Cheers, Nicolas

[videlec]

comment:39

If we switch back, only the following fails (from sage.combinat.tutorial):

sage: Suits = Set(["Hearts", "Diamonds", "Spades", "Clubs"])
sage: Values = Set([2, 3, 4, 5, 6, 7, 8, 9, 10,
....:               "Jack", "Queen", "King", "Ace"])
sage: Cards = cartesian_product([Values, Suits])
sage: Hands = Subsets(Cards, 5)
Traceback (most recent call last):
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'

and the reason is because you can not do the list of Cards...

sage: list(Cards)
Traceback (most recent call last):
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'

There are of course other ways to fix it, but I found that it was the simplest. Using FiniteEnumeratedSet instead of Set in the tutorial seems unnatural to me since you want to keep it as simple as possible...

Vincent

[nthiery]

comment:40

Replying to @videlec:

If we switch back, only the following fails (from sage.combinat.tutorial):

sage: Suits = Set(["Hearts", "Diamonds", "Spades", "Clubs"])
sage: Values = Set([2, 3, 4, 5, 6, 7, 8, 9, 10,
....:               "Jack", "Queen", "King", "Ace"])
sage: Cards = cartesian_product([Values, Suits])
sage: Hands = Subsets(Cards, 5)
Traceback (most recent call last):
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'

and the reason is because you can not do the list of Cards...

sage: list(Cards)
Traceback (most recent call last):
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'list'

There are of course other ways to fix it, but I found that it was the simplest. Using FiniteEnumeratedSet instead of Set in the tutorial seems unnatural to me since you want to keep it as simple as possible...

I tend to agree indeed; this would be annoying.

Maybe we should eventually make the distinction between sets, sets admitting an iterator, and sets with a distinguished enumeration.

For now, let's say that this will do, unless someone has some additional insight to provide.

Still, any thought about moving this feature to Sets.Finite.CartesianProducts?

[videlec]

comment:41

Replying to @nthiery:

Replying to @videlec:

Maybe we should eventually make the distinction between sets, sets admitting an iterator, and sets with a distinguished enumeration.

Ideally, we would do a conditional inheritance based on the presence of __iter__. I am not sure it is worth it to complicate anymore the various set categories with an IterableSets.

For now, let's say that this will do, unless someone has some additional insight to provide.

Still, any thought about moving this feature to Sets.Finite.CartesianProducts?

Before it was in EnumeratedSets.CartesianProducts and not EnumeratedSets.Finite.CartesianProducts. So I tend to prefer the place it is. Of course, we should support better infinite factors.

Vincent

[videlec]

Description changed:

--- 
+++ 
@@ -1,10 +1,10 @@
 The features of `sage.combinat.cartesian_product.CartesianProduct` are now completely integrated into the category framework (see #18290). We remove all occurrences of `CartesianProduct` to either `cartesian_product` or `itertools.product`. We deprecate the `CartesianProduct` from `sage.combinat.cartesian_product`.

 In order to support all features of the old class we also:
-- move the `__iter__` from `EnumeratedSets.CartesianProducts.ParentMethods` category to `Sets`
+- move the `__iter__` from `EnumeratedSets.CartesianProducts.ParentMethods` to `Sets.CartesianProducts.ParentMethods`
 - allows `cartesian_product` to be called with `list`, `tuple`, `set`, `frozenset`
 - make `cartesian_product([])` works
-- introduce a function `bounded_number_of_tuples` in `sage.misc.misc` that is intensively used in the testing framework
+- introduce a function `some_tuples` in `sage.misc.misc` that is intensively used in the testing framework (and incidentally speed up some doc test)
 - refine the category of `Set([1,2,3])` to be finite
 - implement a (very naive) `random_element` for `Set([1,2,3])`
 - implement a (naive) hash for `EnumeratedSetFromIterator`

[videlec]

comment:43

ping: are we good?

[videlec]

comment:44

ping ping: are we good good?

[nthiery]

comment:45

Oh, sorry, I missed the ping in my mailbox. Yes, given that noone commented about the Sets thing, I believe we are good. Moving to positive review.

[nthiery]

comment:47

Oh, I had not noticed the startup module plugin failure. If you see a trivial way to avoid loading the following modules on startup, that would be nice. Otherwise we can live without it:

+    sage.combinat.rigged_configurations.itertools
+    sage.geometry.itertools
+    sage.geometry.polyhedron.itertools

[videlec]

comment:48

Replying to @nthiery:

Oh, I had not noticed the startup module plugin failure. If you see a trivial way to avoid loading the following modules on startup, that would be nice. Otherwise we can live without it:

+    sage.combinat.rigged_configurations.itertools
+    sage.geometry.itertools
+    sage.geometry.polyhedron.itertools

It is a problem with the patchbot plugin, Not with my code ;-). The module is itertools and not whatever.the.patchbot.thinks.itertools.

sage: sage.combinat.rigged_configurations.itertools
Traceback (most recent call last):
...
AttributeError: 'module' object has no attribute 'itertools'

[videlec]

comment:49

More precisely, see issue 71.

[nthiery]

comment:50

Oh, I see. Back to positive review then.

Thanks for all the hard work!!!

[nthiery]

Changed reviewer from Nicolas Thiéry to Nicolas M. Thiéry

[videlec]

comment:52

Thanks Nicolas for the careful review.

[vbraun]

comment:53

Doctest failure, possibly due to one of these:

0e16148 Trac #18338: bell_polynomial(n,k) should always return a polynomial
1d39e65 Trac #18284: Implement left top and right bottom maps for rigged configurations
9481c0b Trac #18223: cartesian products with orders
a677b85 Trac #18044: Implement categories for super algebras/modules
2fef51e Trac #17716: AsymptoticRing and AsymptoticExpression
dbd82f3 Trac #17693: mutable poset: a data structure for asymptotic expressions
34f358b Trac #17190: Error in conversion from RR['x,y'] to RR['x']
a87d70f Trac #19357: Bug in Multivariate Laurent Polynomial Ring
20616e0 Trac #19321: provide better hash functions

[vbraun]

Dependencies: 17411

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

d063050	Fix doctest from update to Coxeter groups.
5f32618	trac #17411 a few doc typo corrections and also some pep8 code changes
66a2290	trac #17411 final pep8 cleanup
0350849	trac #17411 insertion in module_list
0b56cd3	trac #17411 one typo found
24b4b4f	trac #17411 lazy import
e9d30dc	Merge branch 'public/combinat/colored_permutation_groups-17411' of trac.sagemath.org:sage into public/combinat/colored_permutation_groups-17411
4595847	Making changes based upon Kevin's comments.
3a98f7e	Trac 18411: merge 17411
fe857fe	Trac 18411: fix doctest from #17411

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 22f8b77 to fe857fe

[videlec]

comment:56

fixed the issue from #17411... hoping it is the only one.

[videlec]

Changed dependencies from 17411 to #17411

[vbraun]

comment:57

Try again with the next beta

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4a9fd81	Trac 18411: merge Sage 6.10.beta0
525d038	Trac 18411: Fix doctest in colored_permutations.py

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fe857fe to 525d038

[nthiery]

comment:60

The change sounds fine to me! Assuming all test pass, back to positive review.

[videlec]

comment:61

... does not...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 525d038 to 41af762

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

41af762

Trac 18411: pass keywords in __call__

[videlec]

comment:63

...waiting for the patchbot green light...

[videlec]

comment:64

Bueno!

[vbraun]

comment:65

Merge conflict

[videlec]

comment:66

With what?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6e27dde

Trac 18411: merge sage-6.10.beta1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 41af762 to 6e27dde

[videlec]

comment:68

Hoping I will not have to rebase once more...

[vbraun]

Changed branch from public/18411 to 6e27dde