Does this type satisfy the requirements of Sequence and IteratorProtocol?

Using Swift
1

I want to be sure what it means for a type to conform to Sequence and IteratorProtocol, and thus what can be assumed about conforming types when writing extensions on Sequence.

My current interpretation of the related documentation leads me to believe that the following example type satisfies the formal and semantic requirements of Sequence and IteratorProtocol.

/// An example sequence type that is destructively consumed by iteration and
/// has shared mutable state.
final class SharedCountdown: Sequence, IteratorProtocol {
    var current: Int

    init(from: Int) {
        print("-- initializing a new SharedCountdown instance --")
        current = from
    }
    func makeIterator() -> SharedCountdown {
        print("-- calling makeIterator() --")
        return self
    }
    func next() -> Int? {
        if current == 0 {
            return nil
        } else {
            defer { current -= 1 }
            return current
        }
    }
}

// Some examples to demonstrate its behavior:

let a = SharedCountdown(from: 3)
for e in a { print(e) } // Will print 3 2 1
for e in a { print(e) } // Will not print anything (as expected).

let b = SharedCountdown(from: 3)
print(Array(b)) // [3, 2, 1]
print(Array(b)) // []

let c = SharedCountdown(from: 3)
print(Array(c.prefix(1))) // [3]
print(Array(c)) // [2, 1]

let d = SharedCountdown(from: 3)
print(Array(d.dropFirst())) // [2, 1]
print(Array(d)) // []

let e = SharedCountdown(from: 3)
print(e.contains(2)) // true
print(e.contains(2)) // false

let f = SharedCountdown(from: 3)
let g = SharedCountdown(from: 3)
let h = SharedCountdown(from: 3)
print(f.elementsEqual(g)) // true
print(g.elementsEqual(f)) // true (but because they have both been consumed)
print(f.elementsEqual(h)) // false (because f has been consumed but h has not)

let x = SharedCountdown(from: 3)
let y = SharedCountdown(from: 3)
print(x.elementsEqual([3, 2, 1])) // true
print(x.elementsEqual([3, 2, 1])) // false (!)
print(x.elementsEqual(y)) // false (!)
print(x.elementsEqual(y)) // false (!)
print(x.elementsEqual(y)) // false (!)
print(x.elementsEqual(y)) // true (!!!)

So, in short, does this SharedCountdown type satisfy the requirements of IteratorProtocol and Sequence?

3 Likes
Stride Operators, (a..<b)/step and (a...b)/step
2

Not in any official position to judge, but looks fine.

2 Likes
3

I'd say yes.
However two comments on your code:
next() must be marked mutating and AFAIK if the sequence is its own iterator you don't need to implement makeIterator(), it's automagically supplied.

4

Note that it is a class (intentionally), so mutating is not needed.

I know, but I included it in order to know and show exactly what it is doing, and to log calls to it.

1 Like
5

The rules about Sequence and Iterator state that it is not safe to copy them (in the sense of an assignment, not calling a hypothetical copy() method), so if you want to define what happens when you do copy them, that's up to you.

6

This is a pretty solid compilation of the problems with actually having Sequence model single-pass sequences. At the use site, their behavior is incomprehensible and essentially undefined once a single operation has been performed.

cc @soroush @ben-cohen

4 Likes
Add an `adjacentPairs` algorithm to Sequence
7

That’s why Scala’s collections type hierarchy starts with Traversable which has the single requirement of foreach. Then it continues with Iterable on to three traits: Seq, Set, and Map.
image

The Seq trait represents sequences:

A sequence is a kind of iterable that has a length and whose elements have fixed index positions, starting from 0.

So that would roughly correspond to Swift's Collection, I guess? Notice how this hierarchy avoids our weird issues of Set and Dictionary: Collection. The protocols in Swift’s collections are very compressed. I’m guessing they started with implementation of Array and were adopted for Set and Dictionary with reasoning along the lines that even though they are unordered, technically everything in computer is ordered, therefore it all stuck around?

2 Likes
8

Sorry if I miss understand, but is Scalas Iterable not Swift’s Sequence? Which means scalas Set has all the same ‘problems’ as Swift’s?

9

Yep. The documents for head, Swift first, say:

def head: A

Selects the first element of this iterable collection.

Note: might return different results for different runs, unless the underlying collection type is ordered.

Same goes for Kotlin.

But not Java, it’s Set is much closer to a math set.

1 Like
10

I just found an old thread with a very long and interesting previous discussion on this topic:
[Pitch] Remove destructive consumption from Sequence
cc @dwaite @anandabits @dabrahams

11

I think you could add one special case to the list:

x.elementsEqual(x) // it's probably not hard to guess... but how about

class Stutter: Sequence, IteratorProtocol {
	var current: Int

	init(from: Int) {
		print("-- initializing a new SharedCountdown instance --")
		current = from
	}
	func makeIterator() -> Stutter {
		print("-- calling makeIterator() --")
		return self
	}
	func next() -> Int? {
		if current < 0 {
			return nil
		} else {
			defer { current -= 1 }
			return current / 2
		}
	}
}

let s = Stutter(from: 7)
print(s.elementsEqual(s))
12

For what it's worth, the SQLite wrapper GRDB needed a way to iterate database results. Since SQLite can throw an error at any point during iteration (I/O, etc.), Sequence and Iterator did not fit the bill. They can't throw during iteration. I thus had to define Cursor, a protocol for "types that supply the values of some external resource, one at a time."

Relevant excerpt from its documentation:

/// Cursors share traits with lazy sequences and iterators from the Swift
/// standard library. Differences are:
///
/// - Cursor types are classes, and have a lifetime.
/// - Cursor iteration may throw errors.
/// - A cursor can not be repeated.
///
/// The protocol comes with default implementations for many operations similar
/// to those defined by Swift's Sequence protocol: `contains`, `dropFirst`,
/// `dropLast`, `drop(while:)`, `enumerated`, `filter`, `first`, `flatMap`,
/// `forEach`, `joined`, `joined(separator:)`, `max`, `max(by:)`, `min`,
/// `min(by:)`, `map`, `prefix`, `prefix(while:)`, `reduce`, `reduce(into:)`,
/// `suffix`.
public protocol Cursor: class {
    /// The type of element traversed by the cursor.
    associatedtype Element
    
    /// Advances to the next element and returns it, or nil if no next element
    /// exists. Once nil has been returned, all subsequent calls return nil.
    func next() throws -> Element?
}

I had to fully rewrite lazy throwing versions of map, filter, etc: 773 lines (!) of support code without any help from the standard library. Not a funny job. But it was necessary for a library that claims to be "a toolkit for SQLite databases, with a focus on application development", and thus needs to come with many batteries included. Expressive, fluent, efficient (and above all robust) consumption of lazy database results was part of the design goals.

13

I told the Cursor story above for two reasons:

  1. When Sequence does not fit the bill, because it lacks feature (as in my example), or because it creates weird situations (as in Stutter and SharedCountdown), then one has to wonder if adopting Sequence was correct in the first place. So far, people write as if the bad consequences of an ill-advised adoption of Sequence are to be charged on Sequence. I claim that charging the developer for not choosing the best tool for the job in another valid option on the table.
  2. Stutter and SharedCountdown are two examples of single-pass sequences and their weird behaviors. I guess they are supposed to support the request for 1st-class single-pass-sequences in stdlib. My Cursor example comes to add "and what about throwing sequences"? The Set vs. Sequence thread came to add "and what about unordered sequences?". Some other thread did and will come about "and what about infinite sequences?", etc, etc. There are so many combinations that @ben-cohen had to write:

This is not to say that the protocols are perfect, or not in need of further debate. The single/multi-pass nature of Sequence, and the way that SubSequence works, is still a topic worthy of exploration and potential change (so long as that change can be made in a source-(and soon ABI)-stable way). But revisiting naming based on theoretical concerns, or totally overhauling the hierarchy in a way that would increase complexity with little upside, is not useful and at this point should be considered a settled discussion.

And this is why I'd like to see more people consider my 1st point right above: was adopting Sequence a good idea in the first place?

14

I agree to some extent, but AFAICS, the goal of a protocol's semantic requirements is to prevent weird situations. And Sequence is a a protocol that makes it exceptionally easy to introduce weird situations accidentally, without breaking any of its semantic requirements.

As @dabrahams writes in the old thread:

I should be clear up-front about the main problem I'm trying to solve:

Today, people see a beautiful, simple protocol (Sequence) to which many things conform. They don't recognize that there's a semantic restriction (assume you can make only a single-pass!) on it, so they write libraries of functions that may make multiple passes over Sequences. They test their libraries with the most commonly-available Sequences, e.g. Arrays and Ranges, which happen to be multi-pass. Their tests pass! But their constraints are wrong, their whole model of how to write generic code over sequences is wrong, and some of their code is wrong.

IMO this is a problematic programming model.

15

I agree, too. I'd write "MOST" weird situations, though. I don't know if deliberately sick examples hold much weight (I wrote "I don't know", not "I don't think").

16

I wouldn't call the examples in this thread "sick". A conceptually very similar example would be if the proposed and soon to be accepted default (true) random number generator should conform to Sequence.

17

Now we're talking. What about analyzing random generators instead of made-up sequences, then?

18

Could you please clarify what you mean by that?

EDIT: Oh, I guess you simply mean I should provide some examples using such a random Sequence type instead of the above? (If so, I'm sorry but my english skills made me not realize that immediately, and sure, I can provide such examples.)

EDIT2: Here's such an example:

There are of course many possible ways to design an infinte random number Sequence type, and surely many of them would be much better than this (I'm just focusing on keeping this example simple) but I suspect they will all show some kind of similar behavior, ie one that is probably confusing or at least initially surprising to a large proportion of users.

import Foundation

struct Random: Sequence, IteratorProtocol {
    static var `default` = Random()
    private init() {} // Prevents initialization of this struct
    mutating func next() -> UInt64? {
        return UInt64(truncatingIfNeeded: arc4random()) &<< 32 |
            UInt64(truncatingIfNeeded: arc4random())
    }
}

let a = Random.default.prefix(3)
print(a.elementsEqual(a)) // false (or veeeery unlikely true)

let b = Random.default.lazy.map { $0 & 7 }
let c = b.prefix(3)
c.forEach { print($0) } // 1 7 0

print(c.contains(7)) // false
print(c.contains(7)) // false
print(c.contains(7)) // true
print(c.contains(7)) // false

print(Array(c)) // [3, 5, 2]
print(Array(c)) // [2, 7, 3]

While it feels natural and easy to conform an infinite single pass random sequence to Sequence, it's not as easy to predict or reason about the resulting actual behavior of such a type. And it is also not straight forward to say whether such a type should or should not conform to Sequence.

I'm tempted to draw the following conclusion: Assuming that the above type satisfies the semantic requirements of Protocol (it does, afaics), it should not be ignored, or looked upon as something strange, it should rather be seen as an important test case when writing extension on Sequence and it should be in our minds when we ask ourselves what can be assumed about a Sequence type.

3 Likes
19

Thank you @Jens!

You didn't add any // (!) or // (!!!) comments in your sample code above, as you did for SharedCountdown.

May I interpret this fact (please excuse me if I go wild)? Does it mean that you are less surprised by the behavior of Random.default than you are by SharedCountdown? I think that you actually are. This sample code has the expected behavior, given a sequence of random values.

This is very different from SharedCountdown, which was deliberately built in order to confuse its user.

20

I could of course have added (!) at almost every result-printing line. The content of the two paragraphs following the sample code makes it clear that I'm not any less (or more) surprised by the behavior of Random.default than I am by the behavior of SharedCountdown. And the point is not (anymore) whether I am surprised, it is whether the average user would be surprised.

I still think it is reasonable to believe that most people are surprised by the fact that:

  • a.elementsEqual(a) is not always true

  • a.contains(7) == a.contains(7) is not always true

3 Likes