[swift-evolution] About the PermutationGenerator

[plx]

> On Jan 11, 2016, at 5:21 PM, Jordan Rose <jordan_rose at apple.com> wrote:
> 
>> 
>> On Jan 6, 2016, at 10:42, plx via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>>> 
>>> On Jan 6, 2016, at 11:37 AM, Jordan Rose via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> 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.)
>> 
>> It’s not clear what you mean by a `SequenceType` that isn’t either a `Collection` or a `Generator`, but if you mean a *concrete* sequence that:
>> 
>> - can be re-iterated (thus not a `Generator`)
>> - has no meaningful index (!) (thus not a `Collection`)
>> 
>> …then I can provide you with examples of such. The (!) is b/c you can of course always use `Int` as an index, in the sense that “the value at index `n` is obtained by iterating `n` steps from the start of the sequence”; I’ll assume this doesn’t “count” as an index for purposes of this discussion.
>> 
>> Given the above, I will provide two examples.
>> 
>> Here is one that is stable, re-iterable, infinite, and has no “non-trivial" index:
>> 
>>     // Modest generalization of a seedable PRNG.
>>     // We assume that identically-seeded sources generate
>>     // identical elements (via `randomElement`), in identical order.
>>     protocol RandomElementSourceType {
>> 
>>       typealias Element
>>       typealias Seed: Equatable
>>       // ^ `:Equatable` isn't actually necessary, but it's nice
>>   
>>       init(seed: Seed)
>>   
>>       mutating func randomElement() -> Element
>> 
>>     }
>> 
>>     struct RandomElementGenerator<R:RandomElementSourceType> : GeneratorType {
>> 
>>       typealias Element = R.Element
>>   
>>       private var source: R
>>   
>>       mutating func next() -> Element? {
>>         return source.randomElement() // <- never stops!
>>       }
>>   
>>     }
>> 
>>     struct RandomElementSequence<R:RandomElementSourceType> : SequenceType {
>> 
>>       typealias Generator = RandomElementGenerator<R>
>>   
>>       private let seed: R.Seed
>>   
>>       func generate() -> Generator {
>>         return Generator(source: R(seed: seed))
>>         // ^ as per assumptions, each iteration will be identical b/c
>>         //   because each iteration uses the same seed 
>>       }
>> 
>>     }
>> 
>> …and here is one that is not-necessarily-stable, reiteration-capable, finite (one hopes!), and with no “non-trivial” index:
>> 
>>     struct SuperviewGenerator : GeneratorType {
>>     
>>       typealias Element = UIView
>>     
>>       private var currentView: UIView? // or NSView on OS X, etc.
>>       
>>       private init(initialView: UIView?) {
>>         currentView = initialView
>>       }
>>       
>>       mutating func next() -> Element? {
>>         guard let here = currentView else {
>>           return nil
>>         }
>>         currentView = here.superview
>>         return here
>>       }
>>     
>>     }
>> 
>>     // also e.g. analogous constructs for `CALayer`,
>>     // `UIViewController`, `UIResponder`, “folders/directories”, and so on...
>>     struct SuperviewSequence : SequenceType {
>> 
>>       typealias Generator = SuperviewGenerator
>>       
>>       private let initialView: UIView?
>>       
>>       init(initialView: UIView?) {
>>         self.initialView = initialView
>>       }
>>       
>>       func generate() -> Generator {
>>         return Generator(initialView: initialView)
>>       }
>>       
>>       func underestimateCount() -> Int {
>>         return initialView != nil ? 1 : 0
>>       }
>>       
>>     }
>>     
>>     // Useful extensions:
>>     extension UIView {
>>     
>>       // Enumerates the view hierarchy upward from `self`, including `self`.
>>       func inclusiveSuperviewSequence() -> SuperviewSequence {
>>         return SuperviewSequence(initialView: self)
>>       }
>>       
>>       // Enumerates the view hierarchy upward from `self`, omitting `self`.
>>       func exclusiveSuperviewSequence() -> SuperviewSequence { 
>>         return SuperviewSequence(initialView: self.superview)
>>       }
>>     
>>     }
> 
> I've been musing over these for a few days, and I think the answers are that RandomElementSequence would be a Generator and SuperviewSequence would be a Collection.
> 
> RandomElementSequence: As you say, this type is copyable, but its iteration is destructive: you can't get back to a previous state via any sort of Index. But that's not a distinction between Sequence and Generator today; there are some Generators that are perfectly copyable and others that are not. (Ideally, the ones that aren't would be made into classes.) If all you have is a generic Generator, you can only iterate it once…but the same is true of Sequence. Knowing the concrete type 

^ did something get edited out here?

> 
> Sure, you could come up with a new protocol, MultipassSequence, but you could just as easily have a MultipassGenerator that just means "this generator is safe to copy". (That's basically InputIterator vs. ForwardIterator <http://en.cppreference.com/w/cpp/iterator> in C++.)

I’m almost ready to make a proposal for something along those lines, actually, although these responses mean I’ll be revising it a bit first.

> 
> (Another direction to take this: a degenerate case of an index would be "the entire state of the underlying RNG", but that's not always possible with, say, access control.)

Dmitri suggested this also; I don’t see what the natural `endIndex` would be here (that isn’t just, say, created by artificially truncating the underlying sequence).

> SuperviewSequence: Right, so, I claim this is a Collection. Here's my index:
> 
> public struct SuperviewIndex: ForwardIndexType {
>   var currentNode: AnyClass?
> 
>   func successor() -> SuperviewIndex {
>     guard let currentNode = self.currentNode else {
>       fatalError("advanced past the end SuperviewIndex")
>     }
>     return SuperviewIndex(currentNode.superclass)
>   }
> }
> 
> and the CollectionType implementation:
> 
> public var startIndex: SuperviewIndex { return .init(startNode) }
> public var endIndex: SuperviewIndex { return .init(nil) }
> 
> public subscript(index: SuperviewIndex) {
>     guard let currentNode = index.currentNode else {
>       fatalError("accessed endIndex")
>     }
>     // Debug-only assertion
>     assert(self.indices.contains(index), "not part of this superclass hierarchy")
>     return currentNode
> }

I have to hand it to you here, it really does meet the requirements; this is a good trick to be aware of. 

Interestingly-enough, I hadn’t actually actually considered writing a superclass sequence, but it’d certainly have its own uses.

It also highlights that `ForwardIndexType` and `GeneratorType` are suspiciously similar, and would be even more so in a “collections move indices” world (e.g. SR-122, which I hope is adopted in some form).

> 
> It is a little weird that the subscript doesn't depend on 'self' at all, but that's just the nature of the collection: if you want an O(1) access, you're not going through the collection at all. (Try to implement a linked list that conforms to CollectionType using a class and you'll see the same thing. Implement one using an enum and it's even weirder.)
> 
> 
> I'm still trying to come up with a good response to Erica's idea that GeneratorType and CollectionType don't inherently have anything in common, but the gist of it is that there are useful operations common to both kinds of values, which suggests the existence of a more general abstraction. That is, there are things that are obviously Collections and things that are obviously not Collections but could still be Generators, and there are operations (currently on SequenceType) that apply to both.

FWIW, I’d say that it’s less that theres an actual common abstraction here as that you have a bunch of operations that *could* be defined on `GeneratorType` (though currently are-defined on `SequenceType`), but because you can always get a “canonical” generator from a `CollectionType` it becomes easy to start eliding this distinction…and after awhile you might start referring to these generator-operations as applying to both.

That’s just one interpretation, though.

Thanks for the considered response; I’ve picked up a couple tricks and now have some food for thought.

> 
> Jordan

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160111/ea52d0de/attachment.html>