SequenceType vs. CollectionType


(Aaron Bohannon) #1

Hi,

I find the SequenceType protocol a bit confusing. My confusion is best
explained in the context of a specific, real-world example. Let's say that
I wanted to extend a protocol with a method "repeated(Int)" that would
allow me to iterate over a collection of items multiple times, like this:

for x in ["a", "b", "c"].repeated(3) {
  print(x, terminator: "")
}

That would be expected to print the string "abcabcabc".

Implementing the extension is simple enough. Here's my main question: is
it more appropriate to implement it by extending SequenceType or extending
CollectionType? I'm not imagining an implementation that does any
buffering, so one could argue that the operation would not have predictable
behavior in the context of an arbitrary SequenceType -- however, a likely
implementation would rely upon nothing more than the the generate() method,
which is available in the SequenceType protocol.

- Aaron


(Brent Royal-Gordon) #2

I find the SequenceType protocol a bit confusing. My confusion is best explained in the context of a specific, real-world example. Let's say that I wanted to extend a protocol with a method "repeated(Int)" that would allow me to iterate over a collection of items multiple times, like this:

for x in ["a", "b", "c"].repeated(3) {
  print(x, terminator: "")
}

That would be expected to print the string "abcabcabc".

Implementing the extension is simple enough. Here's my main question: is it more appropriate to implement it by extending SequenceType or extending CollectionType? I'm not imagining an implementation that does any buffering, so one could argue that the operation would not have predictable behavior in the context of an arbitrary SequenceType -- however, a likely implementation would rely upon nothing more than the the generate() method, which is available in the SequenceType protocol.

A protocol is not merely a collection of required members; it is a set of promises about a conforming type's behavior. Some of them can be expressed in code, like that a `SequenceType` provides a `generate()` method returning an instance conforming to `GeneratorType`. Others can only be described in documentation, like that the generator returned by `generate()` returns all of the elements in the sequence, rather than skipping some of them.

In the case of `SequenceType`, the documentation says:

SequenceType makes no requirement on conforming types regarding whether they will be destructively "consumed" by iteration. To ensure non-destructive iteration, constrain your sequence to CollectionType.

It is not correct to assume that a sequence will either be "consumable" and will resume iteration, or that a sequence is a collection and will restart iteration from the first element. A conforming sequence that is not a collection is allowed to produce an arbitrary sequence of elements from the second generator.

So even though the `SequenceType` protocol provides all of the calls your `repeated(_:)` method will use, it explicitly does *not* promise that those calls will behave in the way needed for `repeated(_:)` to work correctly. Your code will be making exactly the sort of assumption the documentation warns you not to make. The fact that the compiler cannot detect this mistake doesn't make it any less of a mistake.

Therefore, I would say you should put `repeated(_:)` on `CollectionType`. If you put it on `SequenceType`, it will malfunction on some of the sequences which claim to support it.

···

--
Brent Royal-Gordon
Architechies


(Karl) #3

Well you could do it, but you’d need to build up a non-consuming sequence as you go so it wouldn’t be a transparent wrapper.
You could specialise for sequences which also implement CollectionType and handle that case more efficiently.

···

On 15 Jun 2016, at 01:59, Brent Royal-Gordon via swift-users <swift-users@swift.org> wrote:

I find the SequenceType protocol a bit confusing. My confusion is best explained in the context of a specific, real-world example. Let's say that I wanted to extend a protocol with a method "repeated(Int)" that would allow me to iterate over a collection of items multiple times, like this:

for x in ["a", "b", "c"].repeated(3) {
print(x, terminator: "")
}

That would be expected to print the string "abcabcabc".

Implementing the extension is simple enough. Here's my main question: is it more appropriate to implement it by extending SequenceType or extending CollectionType? I'm not imagining an implementation that does any buffering, so one could argue that the operation would not have predictable behavior in the context of an arbitrary SequenceType -- however, a likely implementation would rely upon nothing more than the the generate() method, which is available in the SequenceType protocol.

A protocol is not merely a collection of required members; it is a set of promises about a conforming type's behavior. Some of them can be expressed in code, like that a `SequenceType` provides a `generate()` method returning an instance conforming to `GeneratorType`. Others can only be described in documentation, like that the generator returned by `generate()` returns all of the elements in the sequence, rather than skipping some of them.

In the case of `SequenceType`, the documentation says:

SequenceType makes no requirement on conforming types regarding whether they will be destructively "consumed" by iteration. To ensure non-destructive iteration, constrain your sequence to CollectionType.

It is not correct to assume that a sequence will either be "consumable" and will resume iteration, or that a sequence is a collection and will restart iteration from the first element. A conforming sequence that is not a collection is allowed to produce an arbitrary sequence of elements from the second generator.

So even though the `SequenceType` protocol provides all of the calls your `repeated(_:)` method will use, it explicitly does *not* promise that those calls will behave in the way needed for `repeated(_:)` to work correctly. Your code will be making exactly the sort of assumption the documentation warns you not to make. The fact that the compiler cannot detect this mistake doesn't make it any less of a mistake.

Therefore, I would say you should put `repeated(_:)` on `CollectionType`. If you put it on `SequenceType`, it will malfunction on some of the sequences which claim to support it.

--
Brent Royal-Gordon
Architechies

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


(Brent Royal-Gordon) #4

Well you could do it, but you’d need to build up a non-consuming sequence as you go so it wouldn’t be a transparent wrapper.

You could, but the original post said:

···

I'm not imagining an implementation that does any buffering

--
Brent Royal-Gordon
Architechies