[swift-evolution] About the PermutationGenerator
Dave Abrahams
dabrahams at apple.com
Thu Dec 31 23:22:19 CST 2015
> On Dec 31, 2015, at 8:22 PM, 鄭齊峯 via swift-evolution <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 <mailto:dabrahams at apple.com>> 於 2016年1月1日 下午12:00 寫道：
>>
>>>
>>> On Dec 31, 2015, at 7:46 PM, Susan Cheng <susan.doggie at gmail.com <mailto: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 <mailto: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 <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-Dave
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151231/8c157adf/attachment.html>
More information about the swift-evolution
mailing list