[swift-evolution] About the PermutationGenerator

[Dmitri Gribenko]

On Wed, Jan 6, 2016 at 10:42 AM, plx via swift-evolution <
swift-evolution at swift.org> wrote:

>
> On Jan 6, 2016, at 11:37 AM, Jordan Rose via swift-evolution <
> 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.
>

You can use an opaque data type designed just for that collection, it is a
valid design.


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

RandomElementSequence is a forward collection.  You can create an index for
it that contains the generator state, and computes the next element when
the index is advanced.  Subscripting the collection with the index would
return the value contained in the index.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160111/9a8d516d/attachment.html>