[swift-evolution] [Pitch] Remove destructive consumption from Sequence

[Brent Royal-Gordon]

I think you're tremendously overcomplicating the design.

> If we’re going to consider alternative designs it is worth considering the semantic space available.  For the sake of discussion, here is a model that captures the various semantics that exist (the names are just strawmen):
> 
>                           Iterable 
>                           /          \
>                          /             \
>                         /               \
>    FiniteIterable                 MultipassIterable
>                        \                 /
>                          \              / 
>                           \            /
>                          Sequence
>                                 |
>                                 |
>                          Collection
> 
> `Iterable` corresponds to the current `Sequence` - no semantics beyond iteration are required.  Infinite, single-pass “sequences” may conform.  

Okay, so let's start by undoing that renaming to make clear which semantics in this hierarchy are actually new and which ones are already part of the standard library.

                        Sequence 
                          /          \
                         /             \
                        /               \
   FiniteSequence         MultipassSequence
                       \                 /
                         \              / 
                          \            /
               FiniteMultipassSequence
                                |
                                |
                         Collection

> `for..in` naturally requires `FiniteIterable`,

Why? There's nothing conceptually incoherent about looping over an infinite sequence. Even ignoring errors, you can `break` out, you can `exit()` from an interior method, you can abort or fail a precondition, or you can just let it loop forever. Forbidding potentially-infinite for loops `for` loops is an arbitrary limitation.

> but does not require the `MultipassIterable`.
> 
> There are many interesting infinite `MultipassIterable` types.  These include any dynamically generated sequence, such as a mathematical sequence (even numbers, odd numbers, etc).  This is also what the existing `Sequence` would become if we drop support for destructive sequences and do nothing else (note: it would still be possible to accidentally write a `for..in` loop over an infinite sequence).

Okay, but all of these can be represented as infinite Collections.

Let me explain. If a Sequence is truly multipass—that is, you can iterate over it many times and it will always return the same elements—then it must look something like this:

	struct MyElement { … }	
	
	struct MyState {
		…
		init() { … }
		mutating func formNextElement(in: MySequence) { … }
		var currentElement(in: MySequence) -> MyElement? { … }
	}

	struct MySequence: MultipassSequence {
		struct Iterator: IteratorProtocol {
			var sequence: MySequence
			var state: MyState
			
			init(sequence: MySequence, initialState: MyState) {
				self.sequence = sequence
				self.state = initialState
			}
			
			mutating func next() -> MyElement? {
				defer { someState.formNextElement(in: sequence) }
				return someState.currentElement(in: sequence)
			}
		}
		
		func formIterator() -> MyIterator {
			return MyIterator(sequence: self, initialState: MyState())
		}
	}

Now, the pieces may *appear* to be different—the Iterator may not actually need a reference to the Sequence, the state may be stored in many properties instead of just one, the code to iterate and get the current element may be directly in `next()` instead of in methods `next()` calls—but any multipass Sequence and Iterator could be refactored to match this pattern, so all multipass Sequences and Iterators are equivalent to it.

But you can convert MySequence into a possibly infinite MyCollection like so:

	struct MyCollection: PossiblyInfiniteCollection {
		enum Index: Comparable {
			var offset: Int
			var state: MyState?
		}
				
		var startIndex: Index {
			return Index(offset: 0, state: MyState())
		}
		var endIndex: Index {
			return Index(offset: Int.max, state: nil)
		}
		
		func formIndex(after index: inout Index) {
			index.state!.formNextElement(in: self)
			if index.state!.currentElement(in: self) == nil {
				index.offset = Int.max
			}
			else {
				index.offset! += 1
			}
		}
		
		subscript(index: Index) -> MyElement {
			return index.state!.currentElement(in: self)
		}
	}
	
	func == (lhs: MyCollection.Index, rhs: MyCollection.Index) -> Bool {
		return lhs.offset == rhs.offset
	}
	
	func < (lhs: MyCollection.Index, rhs: MyCollection.Index) -> Bool {
		return lhs.offset < rhs.offset
	}

In other words, whatever state (other than the sequence itself) the Iterator needs to keep in its stored properties can instead be stored inside an index, and whatever logic the Iterator needs to implement its `next()` method can instead be split between `formIndex(after:)` and `subscript(_:)`. Any MultipassSequence can be written as a PossiblyInfiniteCollection if you're willing to put in the effort. And this is a boon to its multipass-ness, because you can not only start over again from the beginning, but start over from *any* step in the iteration.

If any MultipassSequence can be written as a PossiblyInfiniteCollection, then we can eliminate another protocol:

                        Sequence 
                          /          \
                         /             \
                        /               \
   FiniteSequence         PossiblyInfiniteCollection
                       \                 /
                         \              / 
                          \            /
                         Collection

Now we can move any members which may not terminate early (like `map` or `last`) or are ill-defined when infinite (`count`) into `FiniteSequence` and `Collection`, while leaving any which often do terminate early (like `first` or `index(of:)`) in `Sequence` and `PossiblyInfiniteCollection`.

Is this necessary? I don't really know. Arguably, we could simply provide this hierarchy:

                        Sequence 
                          /          \
                         /             \
                        /               \
      IteratorProtocol      Collection

Where Iterators must be treated as potentially infinite, Collections are always finite, and you are asked (or, with a "closed protocol" feature, forced) to conform to one or the other, rather than to Sequence directly. Then the non-infinite-safe APIs like `map` can move onto `Collection` and we'll have covered most of the use cases which matter.

-- 
Brent Royal-Gordon
Architechies