#15425: Cleanup cartesian products
------------------------------+------------------------
Reporter: nthiery | Owner:
Type: task | Status: new
Priority: major | Milestone: sage-6.2
Component: categories | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------+------------------------
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:
>
> #. 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 cases.
>
> #. 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]):
> {{{
> 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.
>
> #. #16269: Fix bug reported by Nathann Cohen [2]: 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}}}.
>
> #. 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
> 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
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. 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}}}.
--
Comment (by 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
--
Ticket URL: <http://trac.sagemath.org/ticket/15425#comment:4>
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.
