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

[Dave Abrahams]

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.

on Sun Jun 26 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

> Can’t a Sequence be potentially infinite, whereas a collection has a
> defined count/endIndex?  Other than that, I agree with your statement.

I agree that that is currently what the documentation allows and requires.
Maybe we do need to separate finiteness from multipass-ness.  There's
certainly no reason one can't make multiple passes over a portion of an
infinite sequence.  

[Just to complicate things... I wonder if finiteness is really
meaningful.  It's easy to create a finite sequence that's so long that
it's “effectively infinite.”]

> Here is what I see as the appropriate structure:
>
> Iterator: Single destructive pass, potentially infinite, (should be
> for-in able)

[Note: the best way to represent “single destructive pass” today is to
constrain Iterator to be a reference type.  Otherwise, it's both easy to
create an Iterator that can be used to make multiple passes (by
copying), and to create a truly single-pass Iterator that suggests it
has value semantics.  These are both potentially misleading situations]

> Sequence: Guaranteed non-destructive multi-pass (vends Iterators),
> potentially infinite, (should be subscript-able, gain most of
> collection, but lose anything that relies on it ending)
>
> Collection: Multi-pass, guaranteed finite, (no changes from current
> form, except extra inits from Iterator/Sequence with end conditions)

This is a reasonable structure, but there are important details missing.

1. Presumably these are all for-in-able.  What makes something
   for-in-able?

2. Presumably Collection refines Sequence.  Does Sequence refine
   Iterator?  IMO that would create the same problematic programming
   model we have today.

Perhaps the language should accept types conforming to either of two
unrelated protocols (your Sequence and Iterator, as you've described
them, with no refinement relationship) for for-in.

> Right now we are allowed to have an infinite sequence, but calling
> dropLast or non-lazy map will cause an infinite loop.  These cases
> could be made much safer by considering the potentially infinite and
> finite cases separately...

The other thing I am concerned about here is that we're addressing real
use-cases with these distinctions.  For example, do people commonly get
in trouble with infinite sequences today?

> Thanks,
> Jon
>
>> on Wed Jun 22 2016, David Waite <david-AT-alkaline-solutions.com> wrote:
>> 
>> >> On Jun 22, 2016, at 2:57 PM, Dave Abrahams via swift-evolution
>> >> <swift-evolution at swift.org
>> >> <https://lists.swift.org/mailman/listinfo/swift-evolution>>
>> >> wrote:
>> >> 
>> >> <Ahem> “Iterators,” please.
>> >
>> > That makes me happy - for some reason I thought it was still GeneratorProtocol
>> >
>> >>> destructively, but such Generators would not conform to the needs of
>> >>> Sequence. As such, the most significant impact would be the inability
>> >>> to use such Generators in a for..in loop, 
>> >> 
>> >> Trying to evaluate this statement, it's clear we're missing lots of
>> >> detail here:
>> >> 
>> >> * Would you remove Sequence?
>> >> * If so, what Protocol would embody “for...in-able?”
>> > No, I would just remove the allowance in the documentation and API
>> > design for a destructive/consuming iteration. Sequence would be the
>> > interface to getting access to repeatable iteration, without the need
>> > for meeting the other requirements for Collection.
>> 
>> That would be wrong unless there exist substantial examples of a
>> multipass Sequence that *can't* meet the other requirements of
>> Collection without loss of efficiency.  And since I can write an adaptor
>> that turns any multipass sequence into a Collection, I think it's
>> trivial to prove that no such examples exist.
>> 
>> -- 
>> -Dave
>

-- 
-Dave