Cleanup of ModulesWithBasis and friends

[tscrim]

Currently ModulesWithBasis requires its implementations to behave like CombinatorialFreeModule, along with having an indexing set for the basis which is comparable. The aim of this ticket is to move various methods from CombintorialFreeModule and it's element class to ModulesWithBasis. This ticket will also give better generic functionality, such as a default implementation of support.

[tscrim]

Okay, I figured this was the best starting point for trying to see if the quack of a free module echoes. For this ticket, I moved many methods up and was able to generalize them. There were only minimal changes needed to remove the ordering on support (only the Macdonald basis of Sym) and make monomial_coefficients() an abstract method. I added the copy parameter to monomial coefficients for both speed and dict in the usual free modules has this API. Most of the other changes are trivial changes to doctest output.

The next thing to do would be to check to see if #10672 becomes invalid because of this ticket (execpt perhaps the iteration issue). After that, then move onto either merging CFM and (sparse?) free modules #10671 or rebasing and finalizing #18310.

---

New commits:

​f8bd451

Moving code up from CFM to modules_with_basis.

[tscrim]

Also a question mostly for Nicolas, do we still need _apply_module_morphism? Is it just a method so that we don't have to create a full morphism object?

[darij]

+1! This is the way to go, and thanks for doing it.

However, one thing I'm still missing is an explicit explanation of what methods one needs to implement in order to inherit from ModulesWithBasis. I suspect this is no longer up-to-date:

        # To implement a module_with_basis you need to implement either
        #   basis() or an _indices attribute and monomial().

(as in, we probably need more now), right?

Coercion of coefficients into the base ring needs to be carefully thought over. As of now, I am not sure if it works correctly. For instance, term does no coercion, but __invert__ does self.parent().term(one, ~mcs[one]), although the inversion operator ~ might produce an element of a bigger ring (for example, ~(ZZ(2)) returns 1/2).

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - ``matrix``   -- a matrix of size `\dim X \times \dim Y`
              or `\dim Y \times \dim X`

I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

Also, could we have doctests proving that the monomial_coefficients method works correctly (including not mutating the dictionary unless explicitly required) on various instances of ModulesWithBasis (e.g., vector spaces)? Thank you!

[git]

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

​aa444d2

Fixing doctests, trying to improve compatibility, and some changes.

[git]

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

​954e354

Added a test Darij requested.

[tscrim]

So in my latest commit I fixed doctests. Some were trivial due to support no longer being ordered (and hence changes to the k-schur book tests and the cc of Anne and Mike), some were more substantial:

• ChainComplexes when passed a field said VectorSpaces, and so it did not consider itself as having a distinguished basis. However, if you give it a ring (like ZZ), then it became in ModulesWithBasis (=FreeModules), which it currently does not live from what I saw. Since there wasn't anything using this extra functionality (any attempt to use it was likely broken), I opted to downgrade the category to just Modules. (John, I cc'ed you to let you know.)

• I added a dense_coefficient_list for finite dimensional modules with basis so that you could get an ordered list of coefficients including 0's. This was needed for hyperplane arrangements. I'm open to different names.

• I made the linear expression code be in finite dimensional modules with basis.

Replying to darij:

However, one thing I'm still missing is an explicit explanation of what methods one needs to implement in order to inherit from ModulesWithBasis. I suspect this is no longer up-to-date:

        # To implement a module_with_basis you need to implement either
        #   basis() or an _indices attribute and monomial().

(as in, we probably need more now), right?

I put that in there because that is all that should be required. However, how the code breaks and the traceback tells you everything you need to know as far as what to implement.

Coercion of coefficients into the base ring needs to be carefully thought over. As of now, I am not sure if it works correctly. For instance, term does no coercion, but __invert__ does self.parent().term(one, ~mcs[one]), although the inversion operator ~ might produce an element of a bigger ring (for example, ~(ZZ(2)) returns 1/2).

Actually my generic implementation should handle this with grace as it is coeff * self.monomial(index). However, CFM currently does not do any coercion as indicated in the docstring, but that is a discussion for another ticket.

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - ``matrix``   -- a matrix of size `\dim X \times \dim Y`
              or `\dim Y \times \dim X`

I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

I don't know and I don't really care as that is outside of the scope of this ticket.

Also, could we have doctests proving that the monomial_coefficients method works correctly (including not mutating the dictionary unless explicitly required) on various instances of ModulesWithBasis (e.g., vector spaces)?

Added.

[nthiery]

Replying to darij:

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - ``matrix``   -- a matrix of size `\dim X \times \dim Y`
              or `\dim Y \times \dim X`

I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

Which of the two it is depends on the value of the optional side argument. No worry, there is no attempt at "fixing" things by transposition.

[nthiery]

Replying to tscrim:

Also a question mostly for Nicolas, do we still need _apply_module_morphism? Is it just a method so that we don't have to create a full morphism object?

As far as I know, that was indeed the motivation when Mike H implemented it. I imagine it can make sense in certain cases where many different morphisms are applied. But I don't have a strong opinion either.

[nthiery]

Thanks for the progress on that btw!

[tscrim]

Replying to nthiery:

Replying to tscrim:

Also a question mostly for Nicolas, do we still need _apply_module_morphism? Is it just a method so that we don't have to create a full morphism object?

As far as I know, that was indeed the motivation when Mike H implemented it. I imagine it can make sense in certain cases where many different morphisms are applied. But I don't have a strong opinion either.

I ended up doing something for diagram algebras where I found this to be useful (although I could have used a full morphism to work around it), so I'm happy enough to keep it around for now.

[darij]

Replying to nthiery:

Replying to darij:

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - ``matrix``   -- a matrix of size `\dim X \times \dim Y`
              or `\dim Y \times \dim X`

I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

Which of the two it is depends on the value of the optional side argument. No worry, there is no attempt at "fixing" things by transposition.

Ah, thank you! I didn't see this, as the argument is hidden inside the **keywords.

[git]

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

​2a935f5

Made FreeModules in the category of finite dimensional free modules with basis.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​570bc49	Merge branch 'public/categories/super_categories-18044' into 6.9.b1
​b91cd82	trac #18044 correct one typo in the doc
​7fd1df2	Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
​0579337	Some reviewer tweaks and doc additions.
​aec22cc	Added one more test.
​4b2046f	Merge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
​3f67b6b	Fixing trivial doctest due to changes in category heirarchy.
​fa476dd	Fixing double-colon in INPUT block.
​6cc8b84	Reviewer changes with Darij.
​7c0223a	Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/cleanup_CFM_modules_wBasis-18066

[tscrim]

It wasn't letting me post this comment:

To fix the failing doctests, I made the free modules be in the category of finite dimensional modules with basis, which I believe they should have been awhile ago. I also merged in the filtered algebras patch.

[git]

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

​caa5323	Merge branch 'develop' into public/categories/cleanup_CFM_modules_wBasis-18066
​c504110	Merge branch 'develop' into public/categories/cleanup_CFM_modules_wBasis-18066

[git]

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

​913a0c1

Fixing doctest/tab issues from merge.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​07cc001	18411: Fixed unused import
​7c103df	18411: cleanup spacing for optional arguments
​a35ef8a	18411: proofreading
​22f8b77	18411: proofreading
​4a9fd81	Trac 18411: merge Sage 6.10.beta0
​525d038	Trac 18411: Fix doctest in colored_permutations.py
​41af762	Trac 18411: pass keywords in __call__
​6e27dde	Trac 18411: merge sage-6.10.beta1
​b21396c	Merge branch '18411' into HEAD
​b32e479	further changes (mostly doc)

[git]

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

​dbb5789	Further fixes
​e2fb14a	remove _test_keytype since submodules of free modules are currently failing it

[darij]

Great job, Travis. If you are fine with my edits and the doctests agree, this is a positive_review.

I am somewhat unhappy about the fact that submodules of free modules don't play nicely with monomial_coefficients (if M is a submodule of R^n given as the span of some vectors, then m.monomial_coefficients for m \in M gives me the monomial coefficients of m with respect to the standard basis of R^n, not with respect to any basis of M), but this is hardly a flaw of this particular ticket.

[vbraun]

How about running the tests before setting something to positive review?

sage -t --long src/sage/geometry/linear_expression.py
**********************************************************************
File "src/sage/geometry/linear_expression.py", line 183, in sage.geometry.linear_expression.LinearExpression.monomial_coefficients
Failed example:
    sorted(linear.monomial_coefficients().items()
Exception raised:
    Traceback (most recent call last):
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 856, in compile_and_execute
        compiled = compiler(example)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 494, in <lambda>
        example.source, filename, "single", compileflags, 1)
      File "<doctest sage.geometry.linear_expression.LinearExpression.monomial_coefficients[3]>", line 1
        sorted(linear.monomial_coefficients().items()
                                                    ^
    SyntaxError: unexpected EOF while parsing
**********************************************************************
1 item had failures:
   1 of   5 in sage.geometry.linear_expression.LinearExpression.monomial_coefficients
    [165 tests, 1 failure, 1.47 s]

[git]

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

​96004df

Darij...

[darij]

Thanks Travis! (I've just fired up my virtual machine a few minutes ago to deal with this...)

Note to self: do test sage/geometry...

[dimpase]

in src/sage/categories/modules_with_basis.py one still sees

   Once :trac:`18066` is merged

namely here:

9bc28fd5fdb (Travis Scrimshaw  2015-03-26 23:33:19 -0700  129)         This category currently requires an implementation of an
6cc8b8460df (Travis Scrimshaw  2015-10-04 16:20:51 -0500  130)         element method ``support``. Once :trac:`18066` is merged, an
6cc8b8460df (Travis Scrimshaw  2015-10-04 16:20:51 -0500  131)         implementation of an ``items`` method will be required.