Opened 4 months ago

Last modified 4 months ago

#30182 new enhancement

Family: support slices

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.3
Component: combinatorics Keywords:
Cc: tscrim, nthiery, gh-mwageringel Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #29991 Stopgaps:

Description (last modified by 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:

Change History (22)

comment:1 Changed 4 months ago by gh-mwageringel

+1

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

comment:2 follow-up: Changed 4 months ago by nthiery

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?

comment:3 Changed 4 months ago by mkoeppe

  • Description modified (diff)

Thanks. I have clarified the ticket description

comment:4 Changed 4 months ago by nthiery

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?

Last edited 4 months ago by nthiery (previous) (diff)

comment:5 Changed 4 months ago by mkoeppe

  • Description modified (diff)

Edited the description to clarify

comment:6 in reply to: ↑ 2 Changed 4 months ago by mkoeppe

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.

comment:7 Changed 4 months ago by nthiery

Ok. That's consistent indeed.

comment:8 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:9 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:10 follow-up: Changed 4 months ago by gh-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.

comment:11 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:12 in reply to: ↑ 10 Changed 4 months ago by mkoeppe

Replying to gh-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.

comment:13 follow-up: Changed 4 months ago by 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}).

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.

comment:14 Changed 4 months ago by mkoeppe

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.

comment:15 Changed 4 months ago by tscrim

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?

comment:16 Changed 4 months ago by mkoeppe

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, ... ]

comment:17 Changed 4 months ago by tscrim

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?

comment:18 Changed 4 months ago by mkoeppe

  • Dependencies set to #29991

comment:19 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:20 in reply to: ↑ 13 ; follow-up: Changed 4 months ago by gh-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:

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.

comment:21 in reply to: ↑ 20 Changed 4 months ago by mkoeppe

Replying to gh-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

comment:22 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3
Note: See TracTickets for help on using tickets.