[swift-evolution] About the PermutationGenerator

[Dave Abrahams]

> On Dec 31, 2015, at 10:52 AM, Donnacha Oisín Kidney <oisin.kidney at gmail.com> wrote:
> 
> Just to add to that, it’s always seemed strange to me that to signify your sequence is multi-pass (i.e., to make it conform to CollectionType) you have to have it conform to Indexable. 

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>.  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> ;-).  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 })


> 
>> On 31 Dec 2015, at 17: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
>>> 
>> 
>>  _______________________________________________
>> 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/e6b9ca5a/attachment.html>