#15425: Cleanup cartesian products
------------------------------+------------------------
Reporter: nthiery | Owner:
Type: defect | 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:
------------------------------+------------------------
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
>
> {{{cartesian_product}}} is meant to subdue {{{CartesianProduct}}}. 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 which 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*
> }}}
>
> Once this is done, we can make CartesianProduct an alias for
> cartesian_product, and maybe deprecate it in the long run.
>
> 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.
>
> Another 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.
>
> Yet another 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}}}.
>
> 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.
>
> [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:
#. 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.
#. 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}}}.
#. 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
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15425#comment:2>
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.
