[Proposal] RangeReplaceableCollection should inherits from MutableCollection

Hi everyone,

I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection

MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))

RangeReplaceableCollection requires a function replaceRange(_:with:)

If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.

Thanks!
Jiannan

I thought this too a couple years ago, but it's not really true. `MutableCollection` requires not only that you be able to set elements, but also that when you do so, it doesn't change any of the indices in the collection. Some collections can't guarantee that. For example, `String` can't conform to `MutableCollection` because if you set some character in the middle of the string to a character that's a different size, it might move characters later in the string to different indices. So Swift lets you say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't let you say `myString[myRange] = newCharacters`.

`MutableCollection` and `RangeReplaceableCollection` are very similar in that they both involve changing a collection. But they are different *kinds* of changes to a collection, so it makes sense for a collection to support either one of them without supporting the other.

···

On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection

MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))

RangeReplaceableCollection requires a function replaceRange(_:with:)

If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.

--
Brent Royal-Gordon
Architechies

MutableCollection's subscript setter is also expected to take constant time (well, proportional to the size of a single element). That may not be the case for a range replacement implementation, even if it turns out the other elements in the collection don't have to move.

Jordan

···

On Dec 4, 2017, at 18:48, Brent Royal-Gordon via swift-dev <swift-dev@swift.org> wrote:

On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection

MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))

RangeReplaceableCollection requires a function replaceRange(_:with:)

If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.

I thought this too a couple years ago, but it's not really true. `MutableCollection` requires not only that you be able to set elements, but also that when you do so, it doesn't change any of the indices in the collection. Some collections can't guarantee that. For example, `String` can't conform to `MutableCollection` because if you set some character in the middle of the string to a character that's a different size, it might move characters later in the string to different indices. So Swift lets you say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't let you say `myString[myRange] = newCharacters`.

`MutableCollection` and `RangeReplaceableCollection` are very similar in that they both involve changing a collection. But they are different *kinds* of changes to a collection, so it makes sense for a collection to support either one of them without supporting the other.

Yes. ‘replaceSubrange(myRange, with: newCharacters)’ is different than subscript, because it may change the length.

But any subscript could do that replaceSubrange could do, right?

在 2017年12月5日,10:48,Brent Royal-Gordon <brent@architechies.com> 写道:

···

On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection

MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))

RangeReplaceableCollection requires a function replaceRange(_:with:)

If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.

I thought this too a couple years ago, but it's not really true. `MutableCollection` requires not only that you be able to set elements, but also that when you do so, it doesn't change any of the indices in the collection. Some collections can't guarantee that. For example, `String` can't conform to `MutableCollection` because if you set some character in the middle of the string to a character that's a different size, it might move characters later in the string to different indices. So Swift lets you say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't let you say `myString[myRange] = newCharacters`.

`MutableCollection` and `RangeReplaceableCollection` are very similar in that they both involve changing a collection. But they are different *kinds* of changes to a collection, so it makes sense for a collection to support either one of them without supporting the other.

--
Brent Royal-Gordon
Architechies

Yes. ‘replaceSubrange(myRange, with: newCharacters)’ is different than subscript, because it may change the length.

But, I mean, what subscript (restrict to the length) could do is subset of p replaceSubrange could do, right?

在 2017年12月5日,10:48,Brent Royal-Gordon <brent@architechies.com> 写道:

···

On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection

MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))

RangeReplaceableCollection requires a function replaceRange(_:with:)

If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.

I thought this too a couple years ago, but it's not really true. `MutableCollection` requires not only that you be able to set elements, but also that when you do so, it doesn't change any of the indices in the collection. Some collections can't guarantee that. For example, `String` can't conform to `MutableCollection` because if you set some character in the middle of the string to a character that's a different size, it might move characters later in the string to different indices. So Swift lets you say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't let you say `myString[myRange] = newCharacters`.

`MutableCollection` and `RangeReplaceableCollection` are very similar in that they both involve changing a collection. But they are different *kinds* of changes to a collection, so it makes sense for a collection to support either one of them without supporting the other.

--
Brent Royal-Gordon
Architechies

But, I mean, what subscript (restrict to the length) could do is subset of p replaceSubrange could do, right?

True but that would imply the opposite of the refinement relationship you’re suggesting. A derived protocol has to have a subset of the behavior of the protocol it refines.

···

Sent from my iPhone

On Dec 5, 2017, at 12:19 AM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection

MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))

RangeReplaceableCollection requires a function replaceRange(_:with:)

If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.

I thought this too a couple years ago, but it's not really true. `MutableCollection` requires not only that you be able to set elements, but also that when you do so, it doesn't change any of the indices in the collection. Some collections can't guarantee that. For example, `String` can't conform to `MutableCollection` because if you set some character in the middle of the string to a character that's a different size, it might move characters later in the string to different indices. So Swift lets you say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't let you say `myString[myRange] = newCharacters`.

`MutableCollection` and `RangeReplaceableCollection` are very similar in that they both involve changing a collection. But they are different *kinds* of changes to a collection, so it makes sense for a collection to support either one of them without supporting the other.

MutableCollection's subscript setter is also expected to take constant time (well, proportional to the size of a single element). That may not be the case for a range replacement implementation, even if it turns out the other elements in the collection don't have to move.

The most common example a not-constant-time-element-updatable-but-still-range-replaceable-collection being String, since graphemes can vary in width in the underlying buffer.

For an example of why this is important, see this optimization for removing elements from a RangeReplaceableCollection:

When the collection is both range-replaceable and mutable, it can save time by not re-allocating the whole buffer, and just shuffling elements down in-place. But it needs to know that swapping two elements takes constant time for this to be an improvement and not an accidentally-quadratic disaster.

···

On Dec 5, 2017, at 2:48 PM, Jordan Rose via swift-dev <swift-dev@swift.org> wrote:

On Dec 4, 2017, at 18:48, Brent Royal-Gordon via swift-dev <swift-dev@swift.org> wrote:

On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

Jordan
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

String should be some kind of MutableCollection. if we really want to restrict subscript of String should be { get } only, then we should consider make some extension methods of MutableCollection should available on SubrangeReplaceablecollection too.

For example:

var c = [1, 2, 3, 4]
print(c.reversed()) // OK

var d = "1234"
print(d.reversed()) // OK

They are both fine.

var a = [1, 2, 3, 4]
a.reverse()
print(a) // OK

var b = "1234"
b.reverse() // no function
print(b)

But this is weird.

String has String.reversed() function,
but it does not have String.reverse() function which is MutableCollection only.

I think, MutableCollection.reverse(), swapAt(_:_:), .partition(by:), sort(by:), should also be available with RangeReplaceableCollection.

···

在 2017年12月6日,06:55,Dave Abrahams <dabrahams@apple.com> 写道:

Sent from my iPhone

On Dec 5, 2017, at 12:19 AM, Cao, Jiannan via swift-dev <swift-dev@swift.org> wrote:

But, I mean, what subscript (restrict to the length) could do is subset of p replaceSubrange could do, right?

True but that would imply the opposite of the refinement relationship you’re suggesting. A derived protocol has to have a subset of the behavior of the protocol it refines.