Does this type satisfy the requirements of Sequence and IteratorProtocol?

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

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

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))

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.

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?

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.

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").

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.

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

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

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.

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

Given a sequence of random elements, I think that you are pushing a little far the "reasonableness" (is is English?) of your statements.

Note that it is a prefix of a sequence of random elements.

The prefix is also a sequence, and its documentation says that it:

Returns a subsequence, up to the specified maximum length, containing the initial elements of the sequence.

And note that a.elementsEqual(a) not always being true also applies to eg a Set.

EDIT: No it doesn’t, i’m obviously confused :-), but at least a == b doesn’t imply a.elementsEqual(b) for Set.

You use the prefix of a lazy sequence of random elements. We've left the trivial zone a long time ago, don't you think? Are the "average users" still the people we need to talk about/with?

Can you show an example here? Or cite the documentation? From what I thought I knew about the semantics of Collection, this isn't possible for any conforming type.

No lazy there, I think it’s a trivial example.

1 Like

I realized this and edited at the same time as you wrote this, please see the edit.

Ah, okay. Well, elementsEqual never implies ==, because even a type that conforms completely “normally” to Sequence/Collection conformance (has a controllable/meaningful order, finite, multipass, whatever) can have additional properties that an Equatable conformance may need to consider.

The prefix does not satisfy the semantic requirements of Sequence. In particular, the prefix’s *iterator* fails to obey the rule that, after it has returned nil once, it must continue to return nil forever.

3 Likes