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]

Description changed:

--- 
+++ 
@@ -1,8 +1,10 @@
+This is the element class of a `CombinatorialFreeModule`.
+
 Its implementation of `__iter__`, `__contains__`, `__len__` are not compatible with anything in the [collections.abc](https://docs.python.org/3/library/collections.abc.html) protocols.

 To improve interoperability, we propose to make changes to make it a [collections.abc.Mapping](https://docs.python.org/3/library/collections.abc.html#collections.abc.Mapping) (= supporting the operations of a `dict` but without mutability):
 - Because a `Mapping` is a `Collection`, we change the `__iter__` method from yielding (key, value) items to yielding keys only. (Thus it will be compatible with the existing `__contains__` method which check for the presence of a key)
 - Add methods `keys`, `items`, `values` with the semantics familiar from `dict`.

-(In #24815, it was proposed to make it a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)
+(Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

[mkoeppe]

Dependencies: #34505

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@

 To improve interoperability, we propose to make changes to make it a [collections.abc.Mapping](https://docs.python.org/3/library/collections.abc.html#collections.abc.Mapping) (= supporting the operations of a `dict` but without mutability):
 - Because a `Mapping` is a `Collection`, we change the `__iter__` method from yielding (key, value) items to yielding keys only. (Thus it will be compatible with the existing `__contains__` method which check for the presence of a key)
-- Add methods `keys`, `items`, `values` with the semantics familiar from `dict`.
+- Add methods `keys`, `items`, `values` with the semantics familiar from `dict`. If ``self`` is a submodule, they refer to the ambient module.

 (Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@

 To improve interoperability, we propose to make changes to make it a [collections.abc.Mapping](https://docs.python.org/3/library/collections.abc.html#collections.abc.Mapping) (= supporting the operations of a `dict` but without mutability):
 - Because a `Mapping` is a `Collection`, we change the `__iter__` method from yielding (key, value) items to yielding keys only. (Thus it will be compatible with the existing `__contains__` method which check for the presence of a key)
-- Add methods `keys`, `items`, `values` with the semantics familiar from `dict`. If ``self`` is a submodule, they refer to the ambient module.
+- Add methods `keys`, `items`, `values` with the semantics familiar from `dict`. If `self` is a submodule, they refer to the ambient module (see #34455).

 (Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

[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.)

[mkoeppe]

Description changed:

--- 
+++ 
@@ -8,3 +8,4 @@

 (Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

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

[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.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,6 +1,16 @@
 This is the element class of a `CombinatorialFreeModule`.

-Its implementation of `__iter__`, `__contains__`, `__len__` are not compatible with anything in the [collections.abc](https://docs.python.org/3/library/collections.abc.html) protocols.
+Its implementation of `__iter__`, `__contains__`, `__len__` are not compatible with anything in the [collections.abc](https://docs.python.org/3/library/collections.abc.html) 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 changes to make it a [collections.abc.Mapping](https://docs.python.org/3/library/collections.abc.html#collections.abc.Mapping) (= supporting the operations of a `dict` but without mutability):
 - Because a `Mapping` is a `Collection`, we change the `__iter__` method from yielding (key, value) items to yielding keys only. (Thus it will be compatible with the existing `__contains__` method which check for the presence of a key)

[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.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -12,9 +12,9 @@

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

-To improve interoperability, we propose to make changes to make it a collections.abc.Mapping (= supporting the operations of a dict but without mutability): -- Because a Mapping is a Collection, we change the __iter__ method from yielding (key, value) items to yielding keys only. (Thus it will be compatible with the existing __contains__ method which check for the presence of a key) -- Add methods keys, items, values with the semantics familiar from dict. If self is a submodule, they refer to the ambient module (see #34455). +To improve interoperability, we propose to make the following changes: +- Deprecate the __contains__ method (currently testing whether a given index is in the suppport). 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. +- Add a method items, with the same semantics as for sparse vectors from sage.modules, and matrices and tensor components after #29619. If self is a submodule, they refer to the ambient module (see #34455).

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -14,6 +14,7 @@

 To improve interoperability, we propose to make the following changes: 
 - Deprecate the `__contains__` method (currently testing whether a given index is in the suppport). 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 object with a fast `__contains__` method instead of a list.
 - Add a method `items`, with the same semantics as for sparse vectors from `sage.modules`, and matrices and tensor components after #29619. If `self` is a submodule, they refer to the ambient module (see #34455).

 (Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

[mkoeppe]

comment:28

I've updated the ticket description to reflect this revised plan

[mkoeppe]

Branch: u/mkoeppe/make_indexedfreemoduleelement_a_collections_abc_mapping

[mkoeppe]

New commits:

35b8b6e	ModulesWithBasis.ElementMethod.support: Return a SupportView
8ae8f09	src/sage/combinat/crystals, src/sage/categories/*crystals*: Use collections.abc for isinstance
c5857f8	Convert result of support() to list or tuple in two places

[mkoeppe]

Description changed:

--- 
+++ 
@@ -13,8 +13,8 @@
 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 suppport). 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 object with a fast `__contains__` method instead of a list.
+- 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.
 - Add a method `items`, with the same semantics as for sparse vectors from `sage.modules`, and matrices and tensor components after #29619. If `self` is a submodule, they refer to the ambient module (see #34455).

 (Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

[mkoeppe]

Commit: c5857f8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

12da4ed

ModulesWithBasis.ElementMethod.len: Use support

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c5857f8 to 12da4ed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 12da4ed to 31559b2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ddb29b	src/sage/structure/support_view.py: Fix up
31559b2	IndexedFreeModuleElement.__contains__: Deprecate

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

eb2c92d	ModulesWithBasis.support: Try to cache the SupportView object
bf91ea4	src/sage/combinat/ncsf_qsym/generic_basis_code.py: Replace deprecated 'index in vector'
b3abc6c	src/sage/combinat/sf/sfa.py: Replace deprecated 'index in vector'

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 31559b2 to b3abc6c

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

Description changed:

--- 
+++ 
@@ -15,7 +15,7 @@
 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.
-- Add a method `items`, with the same semantics as for sparse vectors from `sage.modules`, and matrices and tensor components after #29619. If `self` is a submodule, they refer to the ambient module (see #34455).
+

 (Similarly, in #24815, it was proposed to make the elements of free modules from `sage.modules` a [collections.abc.Sequence](https://docs.python.org/3/library/collections.abc.html#collections.abc.Sequence).)

[mkoeppe]

comment:36

The proposed method items will be added in #34511

[tscrim]

comment:37

Replying to Matthias Köppe:

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

We have somewhat allowed for the possibility that it can hold zero coefficients, but we almost always in practice just remove them. We probably should just enforce this. This would make the support() call much cheaper, although checking containment could still be slow as it might be list-like checking rather than set-like. Anyways, I doubt it is used in much time critical code, but it is still good to keep similar performance in mind.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b3abc6c to 82d8b62

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

82d8b62

src/sage/structure/support_view.py: Add tests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 82d8b62 to 1f48aa0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1f48aa0

src/sage/structure/support_view.py: Add more tests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1f48aa0 to 2583a37

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2583a37

IndexedFreeModuleElement: Add doc

[mkoeppe]

comment:41

Replying to Travis Scrimshaw:

Replying to Matthias Köppe:

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

We have somewhat allowed for the possibility that it can hold zero coefficients, but we almost always in practice just remove them. We probably should just enforce this. This would make the support() call much cheaper

On the level of CombinatorialFreeModule, not the category, right? We can do that in a follow-up ticket. (The tensor modules don't enforce the sparsity, I think.)

[mkoeppe]

comment:43

This could of course be rewritten to avoid forming all these lists, but I don't know if it's worth it. Question for the author

index aa96f2b..e065b7e 100644
--- a/src/sage/categories/loop_crystals.py
+++ b/src/sage/categories/loop_crystals.py
@@ -456,7 +456,7 @@ class KirillovReshetikhinCrystals(Category_singleton):
             bsharp = None
             for b in self:
                 phi = b.Phi()
-                if phi.support() == [0] and phi[0] < ell:
+                if list(phi.support()) == [0] and phi[0] < ell:
                     bsharp = b