Make IndexedFreeModuleElement compatible with collections.abc, change method support to return a SupportView

[mkoeppe]

This is the element class of a CombinatorialFreeModule.

Its implementation of __iter__, __contains__, __len__ are not compatible with anything in the collections.abc protocols. Specifically,

sage: F = CombinatorialFreeModule(QQ, ['a','b','c'])
sage: B = F.basis()
sage: f = B['a'] + 3*B['c']; f
sage: import collections.abc
sage: isinstance(f, collections.abc.Collection)
True

but __iter__ating over this collection gives objects that are not __contain__ed in it.

To improve interoperability, we propose to make the following changes:

• Deprecate the __contains__ method (currently testing whether a given index is in the support). After its removal, the class would no longer be considered by Python to be a subclass of collections.abc.Collection, but merely a Sized Iterable.
• As a replacement for this functionality, revise the method support to return an instance of a new class SupportView, which provides a fast __contains__ method, instead of a list.

(Similarly, in #24815, it was proposed to make the elements of free modules from sage.modules a collections.abc.Sequence.)

Part of Meta-ticket #30309: Unify free module elements API: methods dict, monomial_coefficients, etc.

Depends on #34505

CC: @fchapoton @tscrim @mwageringel @nthiery @anneschilling

Component: linear algebra

Author: Matthias Koeppe

Branch/Commit: 2fe3b98

Reviewer: Travis Scrimshaw

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

[mkoeppe]

Dependencies: #34505

[tscrim]

comment:5

I am against this change. They are vectors and only on their backend are implemented as a dict, but they are not dictionaries, nor mappings. Likewise, I strongly oppose changing them to iterating over keys. This brings their implementation further from the other free module vectors. The reason we iterate over both is because there is no natural way to order the basis so the sequence of coefficients occurs in a particular order (which will unfortunately be a source of incompatibility). Hence, most of the time when iterating we want to use both the support index and the coefficient. Being vectors, they don’t have keys and values, but support and coefficients. Nor do they have a reasonable notion of containment.

Contrast this to the “usual” free modules, where they have a natural compatibility with sequence as elements in Rⁿ, which are also how we think of finite sequences.

[mkoeppe]

comment:6

Replying to Travis Scrimshaw:

Being vectors, they don’t have keys and values, but support and coefficients. Nor do they have a reasonable notion of containment.

It does define __contains__ currently; no change to that is proposed.

    def __contains__(self, x):
        """
        Returns whether or not a combinatorial object x indexing a basis
        element is in the support of self.
    ...

[mkoeppe]

comment:7

Replying to Travis Scrimshaw:

I strongly oppose changing them to iterating over keys. This brings their implementation further from the other free module vectors.

This makes no sense.

[mkoeppe]

comment:8

Replying to Travis Scrimshaw:

most of the time when iterating we want to use both the support index and the coefficient.

Yes, and there are two interpretations of this when the parent is a submodule.

• one is monomial_coefficients, which refers to the basis of the submodule
• one is the proposed new items, which will refer to the ambient. (This will be compatible with sparse vectors in sage.modules.)

[tscrim]

comment:10

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

I strongly oppose changing them to iterating over keys. This brings their implementation further from the other free module vectors.

This makes no sense.

We want the two implementations to have the same API as much as possible. Rⁿ vectors iterate over coefficients, but iterating over keys/supports here would be the exact opposite of that behavior.

[mkoeppe]

comment:11

Yes, it makes no sense to say that returning (key,value) pairs is closer to being the "same API" as returning values.

[tscrim]

comment:13

Replying to Matthias Köppe:

Yes, it makes no sense to say that returning (key,value) pairs is closer to being the "same API" as returning values.

So actually returning the coefficient as part of the iterator instead of saying you should access it by a completely different method is exactly the same by your logic. You wouldn’t agree that it is a much smaller change to have Rⁿ vector iterators change to return the pairs?

[mkoeppe]

comment:14

Replying to Travis Scrimshaw:

change to have Rⁿ vector iterators change to return the pairs?

That would be a really bad change for dense vectors, which clearly want to be a collections.abc.Sequence

[tscrim]

comment:15

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

most of the time when iterating we want to use both the support index and the coefficient.

Yes, and there are two interpretations of this when the parent is a submodule.

• one is monomial_coefficients, which refers to the basis of the submodule
• one is the proposed new items, which will refer to the ambient. (This will be compatible with sparse vectors in sage.modules.)

Unfortunately because of different implementation goals (mainly the speed that is needed for the Rⁿ modules), we cannot enforce compatibility for everything. I would rather all vectors follow what CFM vectors do from a more abstract mathematical point of view, but we have to make trade-offs. This one is here very clear-cut.

Also, it isn’t just limited to sparse vectors, right?

[tscrim]

comment:16

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

change to have Rⁿ vector iterators change to return the pairs?

That would be a really bad change for dense vectors, which clearly want to be a collections.abc.Sequence

I am not saying we should change it (see comment:15), but if we did, it would be smaller.

[mkoeppe]

comment:17

Replying to Travis Scrimshaw:

Unfortunately because of different implementation goals (mainly the speed that is needed for the Rⁿ modules), we cannot enforce compatibility for everything.

You'll have to be more concrete than that. There's nothing in the proposed change that has anything to do with performance.

[mkoeppe]

comment:18

I do see lots of uses of the idiom ... for (i, c) in self in sage.combinat.

So maybe an easier change would be to get rid of the __contains__ method (with deprecation, of course) to resolve this incompatibility. Then only uses of if i in self would have to be changed to if i in self.support()

[tscrim]

comment:19

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

Unfortunately because of different implementation goals (mainly the speed that is needed for the Rⁿ modules), we cannot enforce compatibility for everything.

You'll have to be more concrete than that. There's nothing in the proposed change that has anything to do with performance.

If we change the iterator for Rⁿ modules to make it compatible with what IndexedFreeModuleElement does, then this would lead to slow downs because the Rⁿ module elements are fairly likely to be used in time-critical code sections (where extra indirections can matter).

[tscrim]

comment:20

Replying to Matthias Köppe:

I do see lots of uses of the idiom ... for (i, c) in self in sage.combinat.

So maybe an easier change would be to get rid of the __contains__ method (with deprecation, of course) to resolve this incompatibility. Then only uses of if i in self would have to be changed to if i in self.support()

+1 on this basically. I doubt anyone is using the support containment check where speed really matters, but that is my only slight hesitancy because that change would make it much slower (via the additional temporary object from support()). Perhaps a self.index_in_support(i) method instead?

[mkoeppe]

comment:21

Replying to Travis Scrimshaw:

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

Unfortunately because of different implementation goals (mainly the speed that is needed for the Rⁿ modules), we cannot enforce compatibility for everything.

You'll have to be more concrete than that. There's nothing in the proposed change that has anything to do with performance.

If we change the iterator for Rⁿ modules to make it compatible with what IndexedFreeModuleElement does

OK, yes, that's just one of several reasons why this change would be bad. It's not being proposed here.

[mkoeppe]

comment:22

Replying to Travis Scrimshaw:

Replying to Matthias Köppe:

I do see lots of uses of the idiom ... for (i, c) in self in sage.combinat.

So maybe an easier change would be to get rid of the __contains__ method (with deprecation, of course) to resolve this incompatibility. Then only uses of if i in self would have to be changed to if i in self.support()

+1 on this basically. I doubt anyone is using the support containment check where speed really matters, but that is my only slight hesitancy because that change would make it much slower (via the additional temporary object from support()). Perhaps a self.index_in_support(i) method instead?

Yes, of course the current implementation of support() is bad. It's another Python2-ish leftover of returning lists all the time.

[mkoeppe]

comment:23

By the way, can _monomial_coefficients really contain keys that have a zero value? I looked briefly and it seemed that for example arithmetic would always remove the zeros

[mkoeppe]

comment:24

If there's no zero value in _monomial_coefficients, then support can just return the _monomial_coefficients.keys() view.

[mkoeppe]

comment:25

Either way instead of inventing a new name such as index_in_support, we should just have support return a suitable object with a __contains__ method.

[sagetrac-git]

Changed commit from 026d8a5 to a417411

[sagetrac-git]

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

a417411

SupportView.__eq__, __ne__: New

[sagetrac-git]

Changed commit from a417411 to b80989f

[sagetrac-git]

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

b80989f

src/sage/combinat/sf/character.py: Use list(....support())

[mkoeppe]

comment:66

ok, done

[tscrim]

comment:67

Should we also do comparisons with different SupportView objects, following python?

sage: d = {1:1, 2:2}
sage: dp = {1:-1, 2:-2}
sage: d.keys() == dp.keys()
True

Sorry if this was something you were planning to support and hadn’t gotten to that stage yet.

[tscrim]

comment:68

Replying to Matthias Köppe:

ok, done

Thank you.

[mkoeppe]

comment:69

Replying to Travis Scrimshaw:

Should we also do comparisons with different SupportView objects, following python?

sage: d = {1:1, 2:2}
sage: dp = {1:-1, 2:-2}
sage: d.keys() == dp.keys()
True

Sorry if this was something you were planning to support and hadn’t gotten to that stage yet.

I'm unsure about this, and I think I would defer it to a follow-up ticket.

It could get full collections.abc.Set semantics actually, including <= as subset test etc. But that's a bit more work

[mkoeppe]

comment:70

In view of #29218, I would also move __iter__ from IndexedFreeModuleElement to the category, next to __len__. Together they merely provide a default implementation of the Sized Iterable protocols. (Dense modules necessarily override both.)

The length method, on the other hand, is full specified and would be changed to not go through __len__.

[mkoeppe]

comment:71

But that will go to #29218.

[mkoeppe]

comment:72

sage -t --random-seed=124699541928353137721504742146487601068 doc/en/thematic_tutorials/lie/weyl_character_ring.rst  # 3 doctests failed
sage -t --random-seed=124699541928353137721504742146487601068 sage/algebras/quantum_groups/fock_space.py  # 80 doctests failed
sage -t --random-seed=124699541928353137721504742146487601068 sage/graphs/generators/random.py  # 1 doctest failed
sage -t --random-seed=124699541928353137721504742146487601068 sage/modules/tutorial_free_modules.py  # 1 doctest failed

[sagetrac-git]

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

57273ea

src/doc/en/thematic_tutorials/lie/weyl_character_ring.rst: Use key=...tuple(....support()) for sorting by lex support

[sagetrac-git]

Changed commit from b80989f to 57273ea

[sagetrac-git]

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

6ce669c	src/sage/modules/tutorial_free_modules.py: Fix doctest output
2fe3b98	src/sage/algebras/quantum_groups/fock_space.py: Use sorted() with support, not sort

[sagetrac-git]

Changed commit from 57273ea to 2fe3b98

[mkoeppe]

comment:75

The failure in sage/graphs/generators/random.py is an unrelated random failure, I've added it to #32544.

[mkoeppe]

comment:77

All morally green, ready for review

(The Build&Test failure is another well-known random failure, in sage/schemes/toric/sheaf/klyachko.py, and Lint failures are known and unrelated.)

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:78

Sorry, lost track of this. LGTM.

[mkoeppe]

comment:79

Thank you!

[vbraun]

Changed branch from u/mkoeppe/make_indexedfreemoduleelement_a_collections_abc_mapping to 2fe3b98