#15425: Cleanup cartesian products
------------------------------+------------------------
Reporter: nthiery | Owner:
Type: task | Status: new
Priority: major | Milestone: sage-6.3
Component: categories | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------+------------------------
Description changed by nthiery:
Old description:
> 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. 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*
> }}}
> Done by #16269/#10963 for cardinality and `__iter__`. Needs double
> checking for the infinite and zero 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}}}.
>
> 3. #16289: Fix bug in cartesian_product (reported by Vincent Delecroix
> in [https://groups.google.com/forum/#!topic/sage-combinat-
> devel/8Aw63kro_0M 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
> [https://groups.google.com/forum/#!msg/sage-
> devel/tyAxhqxk3ZI/rff7pTrGIQ4J 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.
>
> 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. 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.
New description:
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. 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*
}}}
Done by #16269/#10963 for cardinality and `__iter__`. Needs double
checking for the infinite and zero 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}}}.
3. #16289: Fix bug in cartesian_product (reported by Vincent Delecroix in
[https://groups.google.com/forum/#!topic/sage-combinat-devel/8Aw63kro_0M
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
[https://groups.google.com/forum/#!msg/sage-devel/tyAxhqxk3ZI/rff7pTrGIQ4J
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.
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.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15425#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
