Family: support slices

[mkoeppe]

sage: F = Family([0, 1, 4, 9])
sage: F[2]
4
sage: F[2:]
(4, 9)

This happens to work because it is passed on to list.__item__. But:

sage: F = Family({0:0, 2:4, 3:9})       # note 1 is missing
sage: F[2]
4
sage: F[2:]
TypeError: unhashable type: 'slice'     # currently

In this ticket, we add slice support to Family.

sage: F[2:]
TypeError: unhashable type: 'slice'     # currently
(4, 9)                                  # with this ticket
sage: F[0:1]
(0,)                                    # with this ticket
sage: F[0:3]
IndexError: 1 not in family             # with this ticket

As an extension, we will give elements of CombinatorialFreeModule convenient slice accessors like those available for FreeModule and FiniteRankFreeModule.

sage: F = FreeModule(QQ, 6)
sage: F.basis()[2:4]
[
(0, 0, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 0)
]
sage: v = F.basis()[2] + F.basis()[3]
sage: v
(0, 0, 1, 1, 0, 0)
sage: v[2:4]
(1, 1)
sage: type(_)
<class 'sage.modules.vector_rational_dense.Vector_rational_dense'>

sage: F = FiniteRankFreeModule(QQ, 3)
sage: e = F.basis('e')
sage: F = FiniteRankFreeModule(QQ, 5)
sage: e = F.basis('e')
sage: e[2:4]
(Element e_2 of the 5-dimensional vector space over the Rational Field,
 Element e_3 of the 5-dimensional vector space over the Rational Field)
sage: v = e[2] + e[3]
sage: v
Element e_2+e_3 of the 5-dimensional vector space over the Rational Field
sage: v[e, 2:4]
[1, 1]
sage: type(_)
<class 'list'>

sage: F = CombinatorialFreeModule(QQ, [2, 3, 5])
sage: F.basis()[2:4]
TypeError: unhashable type: 'slice'     # currently
[B[2], B[3]]                            # with this ticket
sage: v = F.basis()[2] + F.basis()[3]
sage: v
B[2] + B[3]
sage: v[2]
1
sage: v[2:4]
TypeError: unhashable type: 'slice'    # currently
(1, 1)                                 # with this ticket

---

Random references:

• https://numpy.org/doc/stable/reference/arrays.indexing.html

Depends on #29991

CC: @tscrim @nthiery @mwageringel

Component: combinatorics

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

[mwageringel]

comment:1

+1

I have been looking for this functionality, too, recently.

[nthiery]

comment:2

It's a natural feature to wish. Yet one difficulty is what semantic do we want for F[i:j], given that F[i] does not return the i-th element, but the element indexed by i?. Should this be the i-th to j-1-th element of the family? Or all elements with index k such that i<=k<j? In the latter case, for which order?

[mkoeppe]

Description changed:

--- 
+++ 
@@ -10,10 +10,18 @@
 But:

-sage: F = Family({0:0, 1:1, 2:4, 3:9}) +sage: F = Family({0:0, 2:4, 3:9}) sage: F[2] 4 sage: F[2:] TypeError: unhashable type: 'slice'

+With added support for slices:

+```
+sage: F[2:]
+(4, 9)
+sage: F[0:3]
+IndexError: 1 not in family
+```
+

[mkoeppe]

comment:3

Thanks. I have clarified the ticket description

[nthiery]

comment:4

Hi Matthias,

Can you clarify the semantic you have in mind? I am not sure why the first should fail when the second one would not?

[mkoeppe]

Description changed:

--- 
+++ 
@@ -10,18 +10,15 @@
 But:

-sage: F = Family({0:0, 2:4, 3:9}) +sage: F = Family({0:0, 2:4, 3:9}) # note 1 is missing sage: F[2] 4 sage: F[2:] -TypeError: unhashable type: 'slice' -``` -With added support for slices:

-``` -sage: F[2:] -(4, 9) +TypeError: unhashable type: 'slice' # currently +(4, 9) # with this ticket +sage: F[0:1] +(0,) # with this ticket sage: F[0:3] -IndexError: 1 not in family +IndexError: 1 not in family # with this ticket

[mkoeppe]

comment:5

Edited the description to clarify

[mkoeppe]

comment:6

Replying to @nthiery:

what semantic do we want for F[i:j], ... Should this be ... all elements with index k such that i<=k<j? In the latter case, for which order?

Yes, raising an IndexError if an element indexed by k is not present. In the order of increasing indices.

[nthiery]

comment:7

Ok. That's consistent indeed.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -22,3 +22,42 @@
 IndexError: 1 not in family             # with this ticket

+ +This will give elements of CombinatorialFreeModule convenient slice accessors like those available for FreeModule and FiniteRankFreeModule. + + +sage: F = FreeModule(QQ, 6) +sage: v = F.basis()[2] + F.basis()[3] +sage: v +(0, 0, 1, 1, 0, 0) +sage: v[2:4] +(1, 1) +sage: type(_) +<class 'sage.modules.vector_rational_dense.Vector_rational_dense'> + +sage: F = FiniteRankFreeModule(QQ, 3) +sage: e = F.basis('e') +sage: F = FiniteRankFreeModule(QQ, 5) +sage: e = F.basis('e') +sage: v = e[2] + e[3] +sage: v +Element e_2+e_3 of the 5-dimensional vector space over the Rational Field +sage: v[e, 2:4] +[1, 1] +sage: type(_) +<class 'list'> + +sage: F = CombinatorialFreeModule(QQ, [2, 3, 5]) +sage: v = F.basis()[2] + F.basis()[3] +sage: v +B[2] + B[3] +sage: v[2] +1 +sage: v[2:4] +TypeError: unhashable type: 'slice' # currently +(1, 1) # with this ticket + + + + +

[mkoeppe]

Description changed:

--- 
+++ 
@@ -13,6 +13,13 @@
 sage: F = Family({0:0, 2:4, 3:9})       # note 1 is missing
 sage: F[2]
 4
+sage: F[2:]
+TypeError: unhashable type: 'slice'     # currently
+```
+
+In this ticket, we add slice support to `Family`.
+
+```
 sage: F[2:]
 TypeError: unhashable type: 'slice'     # currently
 (4, 9)                                  # with this ticket

[mwageringel]

comment:10

I am not sure about half-open slices. For example, what is the expected result of this?

sage: F = Family({0:0, 2:4, 3:9, 10:10})
sage: F[2:]

I would probably expect an error, as the keys 4..9 are missing, but it is not possible to obtain this information efficiently from the dictionary.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -30,10 +30,15 @@

-This will give elements of CombinatorialFreeModule convenient slice accessors like those available for FreeModule and FiniteRankFreeModule. +As an extension, we will give elements of CombinatorialFreeModule convenient slice accessors like those available for FreeModule and FiniteRankFreeModule.

 sage: F = FreeModule(QQ, 6)
+sage: F.basis()[2:4]
+[
+(0, 0, 1, 0, 0, 0),
+(0, 0, 0, 1, 0, 0)
+]
 sage: v = F.basis()[2] + F.basis()[3]
 sage: v
 (0, 0, 1, 1, 0, 0)
@@ -46,6 +51,9 @@
 sage: e = F.basis('e')
 sage: F = FiniteRankFreeModule(QQ, 5)
 sage: e = F.basis('e')
+sage: e[2:4]
+(Element e_2 of the 5-dimensional vector space over the Rational Field,
+ Element e_3 of the 5-dimensional vector space over the Rational Field)
 sage: v = e[2] + e[3]
 sage: v
 Element e_2+e_3 of the 5-dimensional vector space over the Rational Field
@@ -55,6 +63,9 @@
 <class 'list'>

 sage: F = CombinatorialFreeModule(QQ, [2, 3, 5])
+sage: F.basis()[2:4]
+TypeError: unhashable type: 'slice'     # currently
+[B[2], B[3]]                            # with this ticket
 sage: v = F.basis()[2] + F.basis()[3]
 sage: v
 B[2] + B[3]

[mkoeppe]

comment:12

Replying to @mwageringel:

I am not sure about half-open slices. For example, what is the expected result of this?

sage: F = Family({0:0, 2:4, 3:9, 10:10})
sage: F[2:]

I would probably expect an error, as the keys 4..9 are missing, but it is not possible to obtain this information efficiently from the dictionary.

This is certainly a point that needs clarification.

[tscrim]

comment:13

I don't expect that to be an error, but instead return [4, 9, 10] or maybe Family({2:4, 3:9, 10:10}).

What you are essentially asking for is a slice of a dict. However, I don't think this makes a lot of sense.

Also, what do you do when the keys are not (and cannot be) ordered?

I think this is fine when the Family object is list-like, but in general, I doubt it is possible to get something consistent.

[mkoeppe]

comment:14

My take is that Family is trying to abstract the difference between lists and hashes etc. away. But currently the slicing behavior of lists leaks through to __item__. It would be fine to just make the first example in the ticket description an error too.

But I think slicing is very useful, and the specification that we have worked out so far on the ticket seems consistent. We could just make unbounded ranges an error - bounded ranges would still be good enough.

[tscrim]

comment:15

I agree that slicing is useful.

Even with bounded ranges, there still is a problem when the keys are not comparable (say, indexed by complex numbers). If they form a poset, then the natural thing would be the interval between them, but the next question is how do you check you got everything? For finite posets, this isn't a problem, but a Family can be indexed by an infinite set. Do you want to just disallow slices when the set is infinite? Or perhaps just non-enumerated sets, where you don't have a rank function?

[mkoeppe]

comment:16

I am not sure about the interpretation of slice(a, b) as intervals. That is not really compatible with the idea that it is an error if an element is missing.

Rather I'd make the assumption that the index set is totally ordered and define slice(a,b) == slice(a, b, 1) and slice(a, b, step) == [ a, a+step, ... ]

[tscrim]

comment:17

Then what does "totally ordered" and "missing" mean here? The set [0, 2, 3, 10] is totally ordered, and there are 4! number of orderings possible to. What about if I do [0, 2/3, 3/10, 5] as my keys?

[mkoeppe]

Dependencies: #29991

[mkoeppe]

Description changed:

--- 
+++ 
@@ -77,5 +77,10 @@

+--- + +Random references: +- https://numpy.org/doc/stable/reference/arrays.indexing.html

+

[mwageringel]

comment:20

Replying to @tscrim:

I don't expect that to be an error, but instead return [4, 9, 10] or maybe Family({2:4, 3:9, 10:10}).

Indeed, it might be better if it does not raise an error, especially if the example from the description is an intended use case in which a slice is used to restrict the support of an element in CombinatorialFreeModule.

This is also consistent with ordinary use of slices, as the following does not throw an error either:

sage: [0,1,2][0:10]
[0, 1, 2]

Also, what do you do when the keys are not (and cannot be) ordered?

I think it is fine to focus on the case in which the keys are integers for now.

[mkoeppe]

comment:21

Replying to @mwageringel:

Replying to @tscrim:

I don't expect that to be an error, but instead return [4, 9, 10] or maybe Family({2:4, 3:9, 10:10}).

Indeed, it might be better if it does not raise an error, especially if the example from the description is an intended use case in which a slice is used to restrict the support of an element in CombinatorialFreeModule.

This is also consistent with ordinary use of slices, as the following does not throw an error either

Good point. This variant is fine with me. Let's change the ticket description

[mkoeppe]

comment:23

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