cartesian products with orders #18223

dkrenn · 2015-04-16T16:13:26Z

Create cartesian products which have a particular order (lexicographically or component-wise) on its elements.

This also incorporates the proposed changes of #18586 (won't be fixed; see discussion there), namely passes keyword arguments on in cartesian_product and adds extra_category.

CC: @behackl @cheuberg @nthiery

Component: categories

Keywords: sd67

Author: Daniel Krenn

Branch/Commit: 8f9a619

Reviewer: Benjamin Hackl, Vincent Delecroix

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

The text was updated successfully, but these errors were encountered:

dkrenn · 2015-04-16T16:19:38Z

Branch: u/dkrenn/cat/cartesian

dkrenn · 2015-04-16T16:20:10Z

New commits:

`595b1c9`	`parameter 'category' for cartesian products`
`afaeb0e`	`parameter extra_category for cartesian products`
`2226fe9`	`cartesian products for comparing lexicographically and component-wise (first working draft)`
`56eda04`	`add docstrings and tests`
`46c7a04`	`extend __init_extra__`

dkrenn · 2015-04-16T16:20:10Z

Commit: 46c7a04

fchapoton · 2015-04-19T10:08:16Z

Changed branch from u/dkrenn/cat/cartesian to public/ticket/18223

fchapoton · 2015-04-19T10:08:16Z

comment:4

fixed a failing doctest

New commits:

`702a8a6`	`Merge branch 'u/dkrenn/cat/cartesian' into 6.7.b1`
`1013cca`	`trac #18223 typo in doctest`

fchapoton · 2015-04-19T10:08:16Z

Changed commit from 46c7a04 to 1013cca

dkrenn · 2015-04-19T10:16:59Z

comment:5

Replying to @fchapoton:

fixed a failing doctest

Thanks.


702a8a6	`Merge branch 'u/dkrenn/cat/cartesian' into 6.7.b1`

What was the reason for this merge?

fchapoton · 2015-04-19T11:17:48Z

comment:6

This is forced to me by git, even when the merge is trivial. I work like that:

I copy the develop branch into say branch18223
I pull the branch from trac, sitting on branch18223
git forces me to do a merge commit, often a trivial one.

dkrenn · 2015-04-19T12:09:41Z

comment:7

Replying to @fchapoton:

This is forced to me by git, even when the merge is trivial. I work like that:

I copy the develop branch into say branch18223

I pull the branch from trac, sitting on branch18223

git forces me to do a merge commit, often a trivial one.

http://www.sagemath.org/doc/developer/manual_git.html#merging-and-rebasing says at the end of the section:

[...] do nothing unless necessary: it is perfectly fine for your branch to be behind master [...]

sagetrac-git · 2015-04-24T19:16:40Z

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

`98fcf3f`	`Merge branch 'public/ticket/18223' into 6.7.b2`
`b924b94`	`trac #18223 one :: missing`

sagetrac-git · 2015-04-24T19:16:40Z

Changed commit from 1013cca to b924b94

videlec · 2015-05-03T20:08:59Z

comment:9

Hello Daniel,

There are tons of product orders that you can define on a cartesian product of posets. You want to write a category for each of them? It is not at all usable for people that wants to build a custom product. The aim of categories is to factorize code not to expand the amount of work. I think that you should seriously develop another strategy for providing an order to a product of posets.
Moreover, this looks very unnatural to me:

sage: P = Poset((srange(10), lambda left, right: left <= right))
sage: Q = cartesian_product((P, P, P),
....: extra_category=Posets().CompareLexCartesianProduct())

IMHO, something like the following would be better

sage: posets.cartesian_product((P,P,P), order = my_order)

where order could also be a custom function or a string like 'lex', 'product', ... this second remark is just from the user point of view.

If there is one product, it should be the cartesian product (or the coordinate wise product) which is the categorical one (when morphisms are the monotone functions). Though as there is a lack of definitions, I am not sure that Hom between two posets are the monotone functions. Would be interesting to settle that.
Sided remark: this will not work with cython Element classes (as there is no element_class)

self.element_class.__le__ = \
lambda left, right: left.parent().le(left, right)

Vincent

nthiery · 2015-05-03T20:44:19Z

comment:10

Salut Vincent!

We had discussed this design with Daniel, and take my share of the blame. I am not quite happy with this solution. I am not quite happy with other solutions either. So that's a good occasion for a discussion!

I guess the main question is whether there will be other categories in
the long run where there will be several variants for the cartesian
product, and we want everything to interplay.

If not, then having a specific cartesian product for posets is
probably ok.

If yes, we would want to have some syntax where we can specify options
for the various structures.

    sage: cartesian_product([A,B,C], poset options, xxx options, ...)

This is more or less what the proposed syntax aims for. But it has the
drawbacks you mention. Possibly this would not be so bad if the
category was parametrized by a "term order":

    sage: cartesian_product([A,B,C], Posets().CartesianProducts(term_order="lex")

It would need to be checked whether we can indeed achieve this syntax
(or a similar one) without tweaking too much the functorial
construction infrastructure.

Another related question is whether a single function is sufficient to
specify the order, or not: maybe we would want to provide
implementations of other methods that apply for specific term orders.

Cheers,
Nicolas

videlec · 2015-05-03T21:21:59Z

comment:11

Salut Nicolas,

Replying to @nthiery:

We had discussed this design with Daniel, and take my share of the blame. I am not quite happy with this solution. I am not quite happy with other solutions either. So that's a good occasion for a discussion!

On the other hand the feature is clearly missing. So we need to find a solution.

I guess the main question is whether there will be other categories in
the long run where there will be several variants for the cartesian
product, and we want everything to interplay.

If not, then having a specific cartesian product for posets is
probably ok.

If yes, we would want to have some syntax where we can specify options
for the various structures.
    sage: cartesian_product([A,B,C], poset options, xxx options, ...)

This worries me a lot since cartesian product is intended for any kind of structures... not only poset. If you start adding specific options into this machinery it will be horrible as well.

This is more or less what the proposed syntax aims for. But it has the
drawbacks you mention. Possibly this would not be so bad if the
category was parametrized by a "term order":
    sage: cartesian_product([A,B,C], Posets().CartesianProducts(term_order="lex")

This is already nicer. Though, there is a problem with morphisms then (see my remark 3 in comment:9). The order in a cartesian product can not be parametrized if the morphisms are monotone functions. So doing the above will prevent defining morphisms in that way. I do not know whether it is what we want to do here.

Note that the following almost works

B = cartesian_product([A0, A1, A2])
my_cmp = lambda x,y: x[0] <= y[0] and x[1] <= y[1] and x[2] <= y[2]
P = Poset((B, my_cmp))

I say almost, because building a Poset is infinitely slow as always and works only for finite posets.

Vincent

dkrenn · 2015-05-05T07:45:41Z

comment:12

Replying to @videlec:

Note that the following almost works
B = cartesian_product([A0, A1, A2])
my_cmp = lambda x,y: x[0] <= y[0] and x[1] <= y[1] and x[2] <= y[2]
P = Poset((B, my_cmp))
I say almost, because building a Poset is infinitely slow as always and works only for finite posets.

Just a short comment: This will not work for what I have in mind, since my A0, A1, A2 will be groups or monoids or rings, and I want B to be a group or monoid or ring, resp., as well. This is also one motivation for using the category framework to add the desired comparison behavior to existing structures.

dkrenn · 2015-06-02T14:33:24Z

Changed branch from public/ticket/18223 to u/dkrenn/cat/cartesian-product-posets

dkrenn · 2015-06-02T14:33:24Z

Dependencies: #18586

dkrenn · 2015-06-02T14:33:24Z

comment:13

I've now derived a class from sets.cartesian_product.CartesianProduct for posets. One can specify by a parameter which order one wants to take. User defined orderes can be used as well.

        sage: P = Poset((srange(3), lambda left, right: left <= right))
        sage: P.CartesianProduct = sage.sets.cartesian_product.CartesianProductPosets
        sage: Cl = cartesian_product((P, P), order='lex')
        sage: Cl((1, 1)) <= Cl((2, 0))
        True
        sage: Cc = cartesian_product((P, P), order='components')
        sage: Cc((1, 1)) <= Cc((2, 0))
        False
        sage: def le_sum(left, right):
        ....:     return (sum(left) < sum(right) or
        ....:             sum(left) == sum(right) and left[0] <= right[0])
        sage: Cs = cartesian_product((P, P), order=le_sum)
        sage: Cs((1, 1)) <= Cs((2, 0))
        True

Last 10 new commits:

`7b098f7`	`parameter extra_category for cartesian products`
`c6a01f8`	`allow kwargs in CartesianProduct (to be used in inherited classes)`
`85f44f3`	`pass on keyword arguments in cartesian product of the sets category`
`ba5dab9`	`update docstring and complete doctests`
`55a7020`	`create class for cartesian products of posets`
`6ed9246`	`method "le"`
`4c9f72c`	`methods for comparing lexicographically and component-wise`
`e589e9b`	`create Element: implement <=, <, >=, >`
`69335cc`	`write a class description`
`9352031`	`change one word in docstring`

dkrenn · 2015-06-02T14:33:24Z

Changed commit from b924b94 to 9352031

dkrenn · 2015-06-02T14:33:24Z

Author: Daniel Krenn

dkrenn · 2015-09-23T07:37:36Z

comment:38

Replying to @videlec:

Replying to @dkrenn:

What is the point of adding *kwargs in the __init__ method of CartesianProduct? If this argument is not supported then it should simply not exists.

This boils down to our discussion from #18586: They are passed on to CartesianProduct where there is at least a flatten keyword. Thus there is a keyword, so arguments are simply passed.

I still do not understand at all. I am talking about sage.sets.cartesian_product.CartesianProduct. Its constructor does not pass its arguments to anybody. What is the subtle difference in behaviour between f and g below?
def f(**kwds):
   if kwds:
       raise TypeError
   ...

def g():
    ...
The only thing I see is that it needs much more to write f.

I think I see your point now and I have to admit I thought we were taking about CartesianProductPosets (and not about CartesianProduct). I agree that this is obsolete now. I've deleted it.

New commits:

`4ac4014`	`remove kwargs in CartesianProduct since not needed`

Last 10 new commits:

`e87db1a`	`rewrite (simplify) join of category`
`6714aaa`	`add comment pointing to #19269 in doctests using QQ as poset`
`298773e`	`explain keyword order better`
`08469c7`	`add module to reference/combinat docs`
`98c252f`	`allow tuples as category`
`eb711e9`	`add TestSuite`
`ca4a844`	`minor rephrase of docstring`
`693b0bd`	`add a native order option`
`f3b1387`	`use Posets.ChainPosets in a doctest`
`4ac4014`	`remove kwargs in CartesianProduct since not needed`

fchapoton · 2015-09-23T18:57:54Z

comment:39

two failing doctests

behackl · 2015-09-28T14:32:59Z

Changed branch from u/dkrenn/cat/cartesian-product-posets to u/behackl/cat/cartesian-product-posets

behackl · 2015-09-28T14:32:59Z

Changed commit from 4ac4014 to 6ca3e5f

behackl · 2015-09-28T14:32:59Z

comment:40

I fixed the two failing doctests (in 6.9.beta7 the category of the cartesian product of ZZ with itself changed) and merged 6.9.rc0 into this branch.

Vincent, as you have done quite some work here would you like to add your name to the reviewers?

Finally, as this ticket seems to have reached a stable state, this could be set to positive_review. Any objections?

Benjamin

Last 10 new commits:

`298773e`	`explain keyword order better`
`08469c7`	`add module to reference/combinat docs`
`98c252f`	`allow tuples as category`
`eb711e9`	`add TestSuite`
`ca4a844`	`minor rephrase of docstring`
`693b0bd`	`add a native order option`
`f3b1387`	`use Posets.ChainPosets in a doctest`
`4ac4014`	`remove kwargs in CartesianProduct since not needed`
`4af1dd4`	`Merge tag '6.9.rc0' into cat/cartesian-product-posets`
`6ca3e5f`	`fixed doctests`

videlec · 2015-09-28T14:34:59Z

comment:41

Replying to @behackl:

Vincent, as you have done quite some work here would you like to add your name to the reviewers?

done

Finally, as this ticket seems to have reached a stable state, this could be set to positive_review. Any objections?

The branch is in good shape. I would like to go through the whole changes a last time. If everything is fine I will set the positive review. Is that ok?

Vincent

videlec · 2015-09-28T14:34:59Z

Changed reviewer from Benjamin Hackl to Benjamin Hackl, Vincent Delecroix

behackl · 2015-09-28T14:37:42Z

comment:42

Replying to @videlec:

The branch is in good shape. I would like to go through the whole changes a last time. If everything is fine I will set the positive review. Is that ok?

Sure! Thanks for going over it once again! :-)

Benjamin

videlec · 2015-09-30T01:34:01Z

comment:43

The name CartesianProductPosets looks weird. I would rather go for CartesianProductPoset (no s) or PosetsCartesianProduct. As it is currently it looks like the set of posets that are made from cartesian products.
You should remove your name from sage/sets/cartesian_product.py. I have nothing agaist authorship but as it is, it looks like spam ;-)
There is no example testing that the coercion can get involved in comparisons. Either it is worth it and it needs a use case or it can be removed.
This is not nice

+        CartesianProductPosets = LazyImport(
+            'sage.combinat.posets.cartesian_product', 'CartesianProductPosets')
+        CartesianProduct = CartesianProductPosets

because

sage: E = Posets().example()
sage: E.Car<tab>
E.CartesianProduct        E.CartesianProductPosets

which actually point toward the exact same thing. Please change for

+        CartesianProduct = LazyImport(
+            'sage.combinat.posets.cartesian_product', 'CartesianProductPosets')

And some questions:

Most methods of finite posets are actually not available in this class... this is very annoying (but I do not see what can be done at the level of this ticket).
Are you aware that

sage: C = cartesian_product([ZZ, ZZ], extra_category=Posets())
sage: from sage.combinat.posets.cartesian_product import CartesianProductPosets
sage: isinstance(C, CartesianProductPosets)
False

and indeed

sage: TestSuite(C).run()
Failure in _test_not_implemented_methods:
...
AssertionError: Not implemented method: le
------------------------------------------------------------
The following tests failed: _test_not_implemented_methods

dkrenn · 2015-09-30T11:21:43Z

Changed branch from u/behackl/cat/cartesian-product-posets to u/dkrenn/cat/cartesian-product-posets

dkrenn · 2015-09-30T11:32:08Z

Changed commit from 6ca3e5f to 8f9a619

dkrenn · 2015-09-30T11:32:08Z

comment:45

Replying to @videlec:

The name CartesianProductPosets looks weird. I would rather go for CartesianProductPoset (no s) or PosetsCartesianProduct. As it is currently it looks like the set of posets that are made from cartesian products.

Ok (I don't have an opinion on this); changed to CartesianProductPoset.

You should remove your name from sage/sets/cartesian_product.py. I have nothing agaist authorship but as it is, it looks like spam ;-)

Ooops...forgotten to remove it (when moving to the code to combinat.posets). Thanks; removed.

There is no example testing that the coercion can get involved in comparisons. Either it is worth it and it needs a use case or it can be removed.

I've added a doctest. This test can and will be rewritten once #18182 is merged.

This is not nice

+        CartesianProductPosets = LazyImport(
+            'sage.combinat.posets.cartesian_product', 'CartesianProductPosets')
+        CartesianProduct = CartesianProductPosets

because

sage: E = Posets().example()
sage: E.Car<tab>
E.CartesianProduct        E.CartesianProductPosets

which actually point toward the exact same thing.

I completly agree.

Please change for

+        CartesianProduct = LazyImport(
+            'sage.combinat.posets.cartesian_product', 'CartesianProductPosets')

I wasn't aware that this works, but it is clear that it works :) Changed.

Most methods of finite posets are actually not available in this class... this is very annoying (but I do not see what can be done at the level of this ticket).

True; I think this should be fixed by using the Posets-category, but definitely not on this ticket.

Are you aware that

sage: C = cartesian_product([ZZ, ZZ], extra_category=Posets())
sage: from sage.combinat.posets.cartesian_product import CartesianProductPosets
sage: isinstance(C, CartesianProductPosets)
False

and indeed

sage: TestSuite(C).run()
Failure in _test_not_implemented_methods:
...
AssertionError: Not implemented method: le
------------------------------------------------------------
The following tests failed: _test_not_implemented_methods

Yes, I am aware of. Adding an extra category only makes sense if the underlying object is a poset (thus has le). Since ZZ is not a poset (see #19269), the cartesian product is not a poset (and has no le) and therefore is not an instance of CartesianProductPoset. Thus, the failure of the test suite is correct.
FYI: The class used for the cartesian product is determined by its first factor (and not by the category).

New commits:

`70aa9c4`	`rename CartesianProductPosets to CartesianProductPoset`
`f21990d`	`code-simplify CartesianProduct assignment`
`8f9a619`	`add a doctest dealing with coercion while comparing`

videlec · 2015-09-30T13:32:46Z

Changed dependencies from #18586 to none

videlec · 2015-09-30T13:32:46Z

comment:46

All right. Thanks for the last changes.

Vincent

vbraun · 2015-10-12T07:16:36Z

Changed branch from u/dkrenn/cat/cartesian-product-posets to 8f9a619

dkrenn added this to the sage-6.7 milestone Apr 16, 2015

dkrenn added c: categories labels Apr 16, 2015

dkrenn added the s: needs review label Apr 16, 2015

videlec added s: needs work and removed s: needs review labels May 3, 2015

This comment has been minimized.

Sign in to view

dkrenn changed the title ~~new categories for cartesian products with orders~~ cartesian products with orders Jun 2, 2015

dkrenn removed the s: needs work label Jun 2, 2015

dkrenn added s: needs review and removed s: needs info labels Sep 23, 2015

videlec added s: needs work and removed s: needs review labels Sep 30, 2015

dkrenn added s: needs review and removed s: needs work labels Sep 30, 2015

videlec added s: positive review and removed s: needs review labels Sep 30, 2015

vbraun removed the s: positive review label Oct 12, 2015

vbraun closed this as completed in 9481c0b Oct 12, 2015

behackl mentioned this issue Dec 29, 2022

Meta ticket: Asymptotic Expansions in SageMath #17601

Open

dkrenn mentioned this issue Jan 29, 2023

provide <=, <, >=, > for poset elements by the category #18222

Open

videlec mentioned this issue Aug 16, 2015

passing on parameters and extra_category for cartesian products #18586

Closed

This was referenced Oct 21, 2015

cartesian products of growth groups #18587

Closed

categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups #19073

Closed

cartesian products with orders #18223

cartesian products with orders #18223

Comments

dkrenn commented Apr 16, 2015

dkrenn commented Apr 16, 2015

dkrenn commented Apr 16, 2015

dkrenn commented Apr 16, 2015

fchapoton commented Apr 19, 2015

fchapoton commented Apr 19, 2015

fchapoton commented Apr 19, 2015

dkrenn commented Apr 19, 2015

fchapoton commented Apr 19, 2015

dkrenn commented Apr 19, 2015

sagetrac-git mannequin commented Apr 24, 2015

sagetrac-git mannequin commented Apr 24, 2015

videlec commented May 3, 2015

nthiery commented May 3, 2015

videlec commented May 3, 2015

dkrenn commented May 5, 2015

dkrenn commented Jun 2, 2015

This comment has been minimized.

dkrenn commented Jun 2, 2015

dkrenn commented Jun 2, 2015

dkrenn commented Jun 2, 2015

dkrenn commented Jun 2, 2015

dkrenn commented Sep 23, 2015

fchapoton commented Sep 23, 2015

behackl commented Sep 28, 2015

behackl commented Sep 28, 2015

behackl commented Sep 28, 2015

videlec commented Sep 28, 2015

videlec commented Sep 28, 2015

behackl commented Sep 28, 2015

videlec commented Sep 30, 2015

dkrenn commented Sep 30, 2015

dkrenn commented Sep 30, 2015

dkrenn commented Sep 30, 2015

videlec commented Sep 30, 2015

videlec commented Sep 30, 2015

vbraun commented Oct 12, 2015