move ProductTree and prod_with_derivative() to sage.rings.generic

[yyyyx4]

The class ProductTree and the function prod_with_derivative() were introduced in #34303. Both are fully generic in principle, but they remained in hom_velusqrt.py in the heat of the moment.

We should move them to a more suitable place; it seems sage.rings.generic is an appropriate choice. Slight tweaks to ProductTree while we're at it.

CC: @jhpalmieri

Component: algebra

Author: Lorenz Panny

Branch/Commit: c3dcb9b

Reviewer: Kwankyu Lee

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

[mezzarobba]

comment:2

I think ProductTree could even go to its own file, since it may well be extended or ported to cython. Also, most of misc.py has a more number-theoretic flavor. (But that's just a suggestion and I'm fine with misc.py too.)

[yyyyx4]

comment:3

Currently sage.misc.misc_c contains the highly related prod() function. I think this could also be in a location such as sage.rings.generic (which doesn't currently exist), similar to how sage.groups.generic contains generic-group algorithms. Personally I don't have a preference.

[kwankyu]

comment:4

I believe importing it by default is a good idea to increase visibility and ease of use.

-1. I don't think it has so general use. But I would hear John.

[jhpalmieri]

comment:5

First, especially if there might be expansions to ProductTree, it might very well make sense to put it in its own file. Second, regarding increased visibility, I would say no right now. For example I look at the documentation and I can't tell what it does. (There is one line of description, "A simple product tree," there is one line saying what the inputs are, and that's pretty much the extent of the documentation. I think it should have much more.) You should make sure it's in the reference manual, and if you think it's particularly useful, write a thematic tutorial about it and add that to the documentation — that's a good way to increase visibility.

[sagetrac-git]

Changed commit from 3ff3cdf to 8e6d94c

[sagetrac-git]

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

8e6d94c

Revert "import ProductTree with sage.arith.all"

[kwankyu]

comment:7

Replying to John Palmieri:

For example I look at the documentation and I can't tell what it does. (There is one line of description, "A simple product tree," there is one line saying what the inputs are, and that's pretty much the extent of the documentation. I think it should have much more.)

+1. In the ProductTree class docstring, there is no description about a product tree. It may be described in terms of leaves, layers, and the root in a couple of sentences.

Instead of a sequence of (which sounds mathematical), a list of would be pythonic, and avoid an unnecessary confusion.

The ALGORITHM section of prod_with_derivative just describes the source code. Thus it is too much detailed but useless for a user. I suggest to remove it.

The paragraph The main reason for this function ... may be moved up and replace the aforementioned ALGORITHM section.

[yyyyx4]

comment:8

Thanks for the feedback, everyone. I'll work on the documentation.

Replying to Kwankyu Lee:

Instead of a sequence of (which sounds mathematical), a list of would be pythonic, and avoid an unnecessary confusion.

But in Python "a list" is much more specific than "a sequence"! For example, a tuple is a sequence but not a list. Indeed, the Python documentation does have a concept of "sequence": https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range

The paragraph The main reason for this function ... may be moved up and replace the aforementioned ALGORITHM section.

Are you suggesting to move it outside of theEXAMPLES block? Or just swap the two examples?

[kwankyu]

comment:9

Replying to Lorenz Panny:

Thanks for the feedback, everyone. I'll work on the documentation.

Replying to Kwankyu Lee:

Instead of a sequence of (which sounds mathematical), a list of would be pythonic, and avoid an unnecessary confusion.

But in Python "a list" is much more specific than "a sequence"! For example, a tuple is a sequence but not a list. Indeed, the Python documentation does have a concept of "sequence": https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range

Strictly speaking, you are right. But it is usual to say "a tuple of" or "a list of" when an input of any sequence type is allowed. I think it is rather unusual to say "a sequence of" for an input of a sequence type (it makes one to think twice).

Again this is not a rule, but a suggestion of a style for uniformity.

The paragraph The main reason for this function ... may be moved up and replace the aforementioned ALGORITHM section.

Are you suggesting to move it outside of theEXAMPLES block? Or just swap the two examples?

To move it to the place of ALGORITHM (perhaps removing alpha). If you do not, please write a new paragraph to explain the purpose (or usage) of the function at the place of the removed ALGORITHM.

[kwankyu]

Reviewer: Kwankyu Lee

[jhpalmieri]

comment:11

Replying to Kwankyu Lee:

Replying to Lorenz Panny:

Thanks for the feedback, everyone. I'll work on the documentation.

Replying to Kwankyu Lee:

Instead of a sequence of (which sounds mathematical), a list of would be pythonic, and avoid an unnecessary confusion.

But in Python "a list" is much more specific than "a sequence"! For example, a tuple is a sequence but not a list. Indeed, the Python documentation does have a concept of "sequence": https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range

Strictly speaking, you are right. But it is usual to say "a tuple of" or "a list of" when an input of any sequence type is allowed. I think it is rather unusual to say "a sequence of" for an input of a sequence type (it makes one to think twice).

Again this is not a rule, but a suggestion of a style for uniformity.

I've seen "an iterable" used in documentation. That would be another option.

[sagetrac-git]

Changed commit from 8e6d94c to 9ad5848

[sagetrac-git]

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

6ff8acf	Merge tag '9.8.beta5' into public/move_product_tree_and_prod_with_derivatives
6fffd92	more detailed documentation
cd1a782	move ProductTree and prod_with_derivative() to sage.rings.generic
77a75ea	sequence -> iterable
9ad5848	illustrate correctness of DFT example

[yyyyx4]

comment:13

Tweaked documentation according to your suggestions, and moved the code in question to a new file sage.rings.generic. Some other functions from sage.arith.misc should probably also end up there, but perhaps not in this ticket.

(I didn't remove the ALGORITHM: block entirely, only reduced detail, and I clarified the text in the main docstring that was already alluding to the example instead of moving the example. Hopefully that'll make everyone happy.)

[kwankyu]

comment:14

Replying to Lorenz Panny:

...Hopefully that'll make everyone happy.

Thanks. LGTM, though I am not completely happy with the overuse of iterable where common and simple list is enough. It's hard to make everyone happy :)

One last thing. Please insert spaces around // in

+            X = [X[i//2] % V[i] for i in range(len(V))]

You can set positive review for me. Thanks!

[sagetrac-git]

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

c3dcb9b

style tweak

[sagetrac-git]

Changed commit from 9ad5848 to c3dcb9b

[yyyyx4]

comment:17

Thank you!

(By the way, regarding the "list" vs. "iterable" question, writing list has the opposite effect on me. It's the one that makes me think twice: Will passing a tuple or a generator work as well, and can I rely on it to keep working in the future? That's why I prefer specifying the correct technical requirement, even if such details are currently indeed rather non-uniform in the Sage codebase.)

[kwankyu]

comment:18

Replying to Lorenz Panny:

... writing list has the opposite effect on me. It's the one that makes me think twice: Will passing a tuple or a generator work as well, and can I rely on it to keep working in the future? That's why I prefer specifying the correct technical requirement, even if such details are currently indeed rather non-uniform in the Sage codebase.)

That is a good reason. Okay!

[vbraun]

Changed branch from public/move_product_tree_and_prod_with_derivatives to c3dcb9b