[swift-evolution] About the PermutationGenerator

Dave Abrahams dabrahams at apple.com
Fri Jan 1 20:30:02 CST 2016


I see what you’ve done, now, after diffing your code with mine.  That’s a very nice improvement; it generalizes to cover more Sequences and doesn’t require an Equatable generator.  Great job!

> On Dec 31, 2015, at 9:30 PM, Susan Cheng <susan.doggie at gmail.com> wrote:
> 
> I didn't explain correctly.
> 
> let's take this:
> 
> let c = Multipass(Fib(a: 1, b: -1, limit: 10))
> 
> this sequences should have results with [1, -1, 0, -1, -1, ...]

> So is c.startIndex.successor() equal to c.startIndex.successor().successor().successor()??
> 
> Dave Abrahams <dabrahams at apple.com <mailto:dabrahams at apple.com>> 於 2016年1月1日星期五 寫道:
> 
>> On Dec 31, 2015, at 8:22 PM, 鄭齊峯 via swift-evolution <swift-evolution at swift.org <javascript:_e(%7B%7D,'cvml','swift-evolution at swift.org');>> wrote:
>> 
>> if you try my modification, it will crash.
> 
> Only because your Sequence genereates an arithmetic underflow.  I don’t understand what point you’re trying to make
>> 
>> struct Fib : SequenceType {
>>     
>>     var a: Int
>>     var b: Int
>>     
>>     var limit: Int
>>     
>>     func generate() -> FibGenerator {
>>         return Generator(a: a, b: b, limit: limit)
>>     }
>> }
>> 
>> let c = Multipass(Fib(a: 1, b: -1, limit: 10))
>> 
>> A SequenceType becomes a CollectionType only work by adding a Index. that the most significantly different of sequence and collection.
> 
> I think I understand that pretty well, having designed both of those abstractions, but still don’t get your point.  Sorry, I’m trying here, but I can’t figure out what you’re trying to tell me.
> 
>> 
>> /// A `CollectionType` containing the same elements as `Base`, without storing them.
>> ///
>> /// - Requires: `Base` supports multiple passes (traversing it does not
>> ///   consume the sequence), and `Base.Generator` has value semantics
>> public struct Multipass<Base: SequenceType> : CollectionType {
>>     public var startIndex: MultipassIndex<Base> {
>>         var g = _base.enumerate().generate()
>>         if let (idx, val) = g.next() {
>>             return MultipassIndex(index: idx, buffer: val, generator: g)
>>         }
>>         return MultipassIndex(index: nil, buffer: nil, generator: g)
>>     }
>>     
>>     public var endIndex: MultipassIndex<Base> {
>>         return MultipassIndex(index: nil, buffer: nil, generator: _base.enumerate().generate())
>>     }
>>     
>>     public subscript(position: MultipassIndex<Base>) -> Base.Generator.Element {
>>         return position.buffer!
>>     }
>>     
>>     public init(_ base: Base) {
>>         _base = base
>>     }
>>     
>>     var _base: Base
>> }
>> 
>> // Note: Requires T.Generator has value semantics
>> public struct MultipassIndex<T: SequenceType> : ForwardIndexType {
>>     public func successor() -> MultipassIndex {
>>         var r = self
>>         if let (idx, val) = r.generator.next() {
>>             r.index = idx
>>             r.buffer = val
>>         } else {
>>             r.index = nil
>>             r.buffer = nil
>>         }
>>         return r
>>     }
>>     var index: Int?
>>     var buffer: T.Generator.Element?
>>     var generator: EnumerateSequence<T>.Generator
>> }
>> 
>> public func == <T>(x: MultipassIndex<T>, y: MultipassIndex<T>) -> Bool {
>>     return x.index == y.index
>> }
>> 
>> //===--- An example fibonacci sequence ------------------------------------===//
>> struct FibGenerator : GeneratorType {
>>     mutating func next() -> Int? {
>>         let c = a + b
>>         a = b
>>         b = c
>>         return a < limit ? a : nil
>>     }
>>     var a, b, limit: Int
>> }
>> 
>> 
>> struct Fib : SequenceType {
>>     var limit = 100
>>     
>>     func generate() -> FibGenerator {
>>         return Generator(a: 0, b: 1, limit: limit)
>>     }
>> }
>> 
>> It's true that ForwardIndexType is also run-through the base one by one but it also correct that getting specific value with specific index.
>> 
>> c[c.startIndex.successor().successor().successor()] // it's a defined behave
> 
> Again, not sure what you’re trying to say here.
> 
>> 
>> 
>>> Dave Abrahams <dabrahams at apple.com <javascript:_e(%7B%7D,'cvml','dabrahams at apple.com');>> 於 2016年1月1日 下午12:00 寫道:
>>> 
>>>> 
>>>> On Dec 31, 2015, at 7:46 PM, Susan Cheng <susan.doggie at gmail.com <javascript:_e(%7B%7D,'cvml','susan.doggie at gmail.com');>> wrote:
>>>> 
>>>> 
>>>> How GeneratorType confirm to Equatable??
>>> 
>>> I don’t understand the question.  In the code I posted there’s a working example of how a GeneratorType model can conform to Equatable..
>>> 
>>>> 
>>>> struct Fib : SequenceType {
>>>>     
>>>>     var a: Int
>>>>     var b: Int
>>>>     
>>>>     var limit: Int
>>>>     
>>>>     func generate() -> FibGenerator {
>>>>         return Generator(a: a, b: b, limit: limit)
>>>>     }
>>>> }
>>>> 
>>>> let c = Multipass(Fib(a: 1, b: -1, limit: 10))
>>>> 
>>>> -Susan
>>>> 
>>>> 
>>>> 2016-01-01 11:17 GMT+08:00 Dave Abrahams <dabrahams at apple.com <javascript:_e(%7B%7D,'cvml','dabrahams at apple.com');>>:
>>>> FWIW, Indexable is an implementation artifact that will go away when Swift’s generics system is improved.
>>>> 
>>>> But if your real objection is that you have to come up with an Index and a subscripting operator, I can understand that.  Part of the reason for this is our reluctance to create any distinct protocols with identical syntactic requirements <http://news.gmane.org/find-root.php?message_id=2A3E0C76-1C88-4752-8A70-AA64BB14223A@apple.com <http://news.gmane.org/find-root.php?message_id=2A3E0C76-1C88-4752-8A70-AA64BB14223A@apple.com>>.  To justify having a separate multi-pass sequence protocol, there would have to be a significant/important class of multi-pass sequences for which CollectionType was unimplementable without serious costs.
>>>> 
>>>> In principle there’s a way to ease the pain of creating CollectionType conformances for multipass SequenceTypes…if only it didn’t crash the compiler <https://bugs.swift.org/browse/SR-427 <https://bugs.swift.org/browse/SR-427>> ;-).  Here’s a variation that uses a generic adapter instead of a protocol conformance declaration:
>>>> 
>>>> /// A `CollectionType` containing the same elements as `Base`, without storing them.
>>>> ///
>>>> /// - Requires: `Base` supports multiple passes (traversing it does not
>>>> ///   consume the sequence), and `Base.Generator` has value semantics
>>>> public struct Multipass<Base: SequenceType where Base.Generator: Equatable> : CollectionType {
>>>>   public var startIndex: MultipassIndex<Base> {
>>>>     var g = _base.generate()
>>>>     return MultipassIndex(buffer: g.next(), generator: g)
>>>>   }
>>>> 
>>>>   public var endIndex: MultipassIndex<Base> {
>>>>     return MultipassIndex(buffer: nil, generator: _base.generate())
>>>>   }
>>>> 
>>>>   public subscript(position: MultipassIndex<Base>) -> Base.Generator.Element {
>>>>     return position.buffer!
>>>>   }
>>>> 
>>>>   public init(_ base: Base) {
>>>>     _base = base
>>>>   }
>>>> 
>>>>   var _base: Base
>>>> }
>>>> 
>>>> // Note: Requires T.Generator has value semantics
>>>> public struct MultipassIndex<T: SequenceType where T.Generator: Equatable> : ForwardIndexType {
>>>>   public func successor() -> MultipassIndex {
>>>>     var r = self
>>>>     r.buffer = r.generator.next()
>>>>     return r
>>>>   }
>>>>   var buffer: T.Generator.Element?
>>>>   var generator: T.Generator
>>>> }
>>>> 
>>>> public func == <T>(x: MultipassIndex<T>, y: MultipassIndex<T>) -> Bool {
>>>>   return x.buffer == nil && y.buffer == nil || x.generator == y.generator
>>>> }
>>>> 
>>>> //===--- An example fibonacci sequence ------------------------------------===//
>>>> struct FibGenerator : GeneratorType {
>>>>   mutating func next() -> Int? {
>>>>     let c = a + b
>>>>     a = b
>>>>     b = c
>>>>     return a < limit ? a : nil
>>>>   }
>>>>   var a, b, limit: Int
>>>> }
>>>> 
>>>> 
>>>> struct Fib : SequenceType {
>>>>   var limit = 1000
>>>> 
>>>>   func generate() -> FibGenerator {
>>>>     return Generator(a: 0, b: 1, limit: limit)
>>>>   }
>>>> }
>>>> 
>>>> //===--- Adapt Fib for use with Multipass ---------------------------------===//
>>>> extension FibGenerator : Equatable {}
>>>> func == (x: Fib.Generator, y: Fib.Generator) -> Bool {
>>>>   return x.a == y.a
>>>> }
>>>> 
>>>> //===--- Demonstration ----------------------------------------------------===//
>>>> let c = Multipass(Fib())
>>>> print(c.first)
>>>> print(c.count)
>>>> print(c.lazy.map { $0 + 1 })
>>>> 
>>> 
>>> -Dave
>> 
>>  _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <javascript:_e(%7B%7D,'cvml','swift-evolution at swift.org');>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
> -Dave
> 

-Dave

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


More information about the swift-evolution mailing list