[swift-evolution] About the PermutationGenerator

Mon Feb 22 09:06:22 CST 2016

on Wed Jan 06 2016, Erica Sadun <erica-AT-ericasadun.com> wrote:

> Thank you for this. Also, the book states: "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."
>
> Your magic DWIM Swift has generators (you call it a destructive
> iteration type) and collections (indexable, re-addressable types). I'm
> trying to wrap my head these. I interpret the former as f() -> U, with
> a progression of accesses with no memory that maps to a known type,
> and the latter being f(index) -> V, where index belongs to a fixed
> index set and maps to the collection's contents.

Yes.

> What confuses me is that both of these seem to my inexperienced mind
> to be operations not types. You point out that a SequenceType doesn't
> actually concretely exist ("Again, no concrete type would ever conform
> to SequenceType; it's just something you can use as a generic
> constraint.") If I were describing these, I'd call them sequence
> generating functions and collection walk functions. The former would
> allow potentially non-terminating streams including random number
> generation, signal generation (for example sin or square waves), or
> soliciting user input. 

The distinction we're interested in is not whether the stream is allowed
to be non-terminating, but whether it can be traversed
non-destructively.  That's at least important for optimizations like
measuring the stream before allocating an array buffer to hold its
contents.

> The latter would offer any kind of iteration or permutation.
>
> I'm not a language person (well not *that* kind of languages person)
> and I'm not up to date on the particular terms of art that apply here,
> as I learned when it came to suggesting alternatives to associated
> type, but it seems like these words don't really describe the things
> you guys are giving us.
>
> Does this better explain my confusion?
>
> -- Erica
>
>> On Jan 6, 2016, at 10:37 AM, Jordan Rose <jordan_rose at apple.com> wrote:
>> 
>> I've bounced this idea off of Dave and Dmitri internally, so might as well put it out publicly:
>> 
>> In Magic DWIM Swift, there would only be two types that you'd ever
>> conform to: a destructive iteration type (today's "Generator"), and
>> a multi-pass indexed type (today's "Collection"). Some operations
>> can meaningfully use either one (like forEach or maxElement); these
>> operations go on a general "traversable" type (today's "Sequence").
>> 
>> In this world, both GeneratorType and CollectionType are refinements
>> of SequenceType (i.e. any GeneratorType "is-a" SequenceType),
>> including the necessary default implementations. Maybe we rename
>> some of the protocols in the process. Again, no concrete type would
>> ever conform to SequenceType; it's just something you can use as a
>> generic constraint.
>> 
>> We can't actually do this today because it creates a circularity
>> between SequenceType and GeneratorType that the compiler can't
>> handle. I'm pretty sure it's possible to change the compiler's
>> protocol checking logic to allow this, though.
>> 
>> Anyway, that's that idea. At the very least it helped me clear up my
>> thoughts about Sequence, Collection, and Generator back when I was
>> first learning them.
>> 
>> Jordan
>> 
>> P.S. This idea falls apart if someone comes up with a model
>> (concrete type) for SequenceType that isn't a Collection or
>> Generator. I wasn't able to think of one back when I was originally
>> thinking about this, but of course that doesn't mean there isn't
>> one. (Infinite collections are interesting as discussed on the
>> "cycle" thread, but it's not the sequence/generator distinction
>> that's really meaningful there.)
>> 
>> 
>>> On Dec 31, 2015, at 9:52, Erica Sadun via swift-evolution
>>> <swift-evolution at swift.org <mailto:swift-evolution at swift.org>>
>>> wrote:
>>> 
>>> I'm trying to work them out, so it's still muddled.
>>> 
>>> Right now, I think SequenceType is better described as
>>> CollectionWalkType but that's kind of (1) a mouthful and (2) not
>>> entirely accurate.
>>> 
>>> Moving back a step: SequenceType is defined as: "A type that can be
>>> iterated with a `for`...`in` loop." But it says nothing about
>>> whether that loop ever terminates and many stdlib sequence
>>> functions currently don't make sense (at least if they're not lazy)
>>> with respect to infinite sequences, which should probably be
>>> "StreamType" not sequences. A couple of examples:
>>> Here's my fib: http://swiftstub.com/189513594/ <http://swiftstub.com/189513594/>
>>> And here's Oisin's user-input sequence:
>>> https://gist.github.com/oisdk/2c7ac33bf2188528842a
>>> <https://gist.github.com/oisdk/2c7ac33bf2188528842a>
>>> Both of these are theoretically filterable, but they aren't dropLast-able, suffix-able, properly split-able, etc.
>>> 
>>> Hopefully that's enough of a starting point to indicate where my
>>> thinking is at and what I'm trying to think through when it comes
>>> to this. -- E
>>> 
>>> 
>>>> On Dec 31, 2015, at 10:09 AM, Dave Abrahams <dabrahams at apple.com <mailto:dabrahams at apple.com>> wrote:
>>>> 
>>>> 
>>>>> On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution
>>>>> <swift-evolution at swift.org <mailto:swift-evolution at swift.org>>
>>>>> wrote:
>>>>> 
>>>>> It does seem that in Swift the concepts of collection, sequence, permutation, stream, etc are a bit muddled.
>>>> 
>>>> This is a pretty vague critique.  Do you have specifics, and suggestions that address them?
>>>> 
>>>>> 
>>>>> -- E
>>>>> 
>>>>> 
>>>>>> On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution
>>>>>> <swift-evolution at swift.org <mailto:swift-evolution at swift.org>>
>>>>>> wrote:
>>>>>> 
>>>>>>> Those are collections.  Collections can be iterated over multiple times.
>>>>>> Speaking of the Fibonacci-numbers:
>>>>>> Sure we can write an algorithm that iterates over them several
>>>>>> times — it just won't ever finish the first iteration ;-)
>>>>>> (only nitpicking — I just couldn't resist)
>>>>>> 
>>>>>> Happy new year!
>>>>>> _______________________________________________
>>>>>> swift-evolution mailing list
>>>>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>>> <https://lists.swift.org/mailman/listinfo/swift-evolution>
>>>>> 
>>>>> _______________________________________________
>>>>> swift-evolution mailing list
>>>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>> <https://lists.swift.org/mailman/listinfo/swift-evolution>
>>>> 
>>>> -Dave
>>>> 
>>> 
>>> <open.gif> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>

-- 
-Dave