Meta-ticket: Modules with basis: We need to separate ABC from implementation

[darijgr]

From what I recall from the discussion at https://groups.google.com/forum/#!topic/sage-combinat-devel/_dtk67RaTFA , the ModulesWithBasis and CombinatorialFreeModule classes are supposed to be an ABC (abstract base class) and a concrete implementation, respectively. However, in practice, the former provides too little abstract interface to be useful, and so a lot of code that uses a module-with-basis as input (explicitly or implicitly) expects to be given a CombinatorialFreeModule instead. Usually this kind of code fails when being passed a ModulesWithBasis instance.

I am posting this here right now because #17096 got positive review, and in that review some issues have been left aside. These issues are essentially a natural second step after cleaning up the ModulesWithBasis-vs-CombinatorialFreeModule mess, and

---

TODO: Formulate an interface and a contract for

FilteredModulesWithBasis objects. Is a CombinatorialFreeModule with a
degree_on_basis method enough? Or is basis still needed? (See the
FIXME in src/sage/categories/examples/filtered_modules_with_basis.py.)

TODO: Make sense of `A.basis(d)` for `A` a filtered module and `d` an

integer. This has always been broken.

TODO: doctesting `A.basis(d)` for `A` graded. Very easy once above is fixed.

About why I think FilteredModulesWithBasis needs a contract:

Here are the methods on F that are used in the implementations of the
methods of FilteredModulesWithBasis when F is cast as a
FilteredModulesWithBasis:

ParentMethods:
degree_on_basis
sum_of_terms
monomial
_indices

ElementMethods:
support
leading_support
is_homogeneous
is_zero

I hear the quacking of a CombinatorialFreeModule duck here (except for
degree_on_basis which should be explicitly required). Are there any
more general categories which offer these methods?

Depends on #18066

CC: @tscrim @nthiery @sagetrac-sage-combinat

Component: categories

Keywords: combinatorial free module, basis, vectors, modules, sage-combinat

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

[tscrim]

comment:1

I think a good part of this is taken care of by #18066, but there will probably be some remaining things related to filtered/graded modules that we will need to address.

[tscrim]

Dependencies: #18066

[mkoeppe]

comment:2

Is this ticket still relevant?

[mwageringel]

comment:3

Yes, I think it is. It is still quite difficult to implement a module with basis without inheriting from CombinatorialFreeModule, as the existence of some methods is implicitly assumed (especially _indices). For example, if one wants to turn polynomial rings (or a wrapper thereof) into a module with basis (possibly filtered or graded), it is not convenient to inherit from CombinatorialFreeModule.

[mkoeppe]

comment:4

So what's missing is a few abstract methods and perhaps _test methods in sage.categories.modules_with_basis?

[nthiery]

comment:5

Yes. And to resolve some conflicts in the current API; e.g. what idiom to use to iterate over pairs (indicies, coefficients), etc.

[nthiery]

comment:6

For a package of mine, I needed these uniform accessors that would work over various kinds
of vector spaces in Sage (polymomials, ...):

https://github.com/nthiery/harmonic-modules/

See: utilitiles.py, matrix_of_vectors.py and subspace.py there.

With Darij, we made an attempt at extracting a dedicated package out of it,
with the idea of integrating it into Sage once stabilized. But we did not get
to push this further.

https://github.com/darijgr/sage-subspace/blob/master/vectors.pyx

[mkoeppe]

comment:9

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:10

Setting a new milestone for this ticket based on a cursory review.

[mkoeppe]

comment:11

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.