[swift-evolution] About the PermutationGenerator

[plx]

> On Jan 12, 2016, at 11:55 AM, Jordan Rose <jordan_rose at apple.com> wrote:
> 
> 
>> On Jan 11, 2016, at 18:35 , plx via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>>> 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?
> 
> Oops, yes. "Knowing the concrete type is the only way to guarantee that multiple iteration is safe." And then:
> 
>>> 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++.)
> 
> 
> 
> Also:
> 
>> 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).
> 
> I guess this is true, in that both produce a single successor, but (a) ForwardIndexType is non-destructive whereas GeneratorType may be, and (b) in that new model, ForwardIndexType does not know its successor whereas GeneratorType does.

It’s not so much that they both produce a single successor; it’s that both of them can wind up with most of their “interesting" logic essentially-shared.

Consider the following thought experiment:

protocol AlternativeCollectionType {
  typealias InternalPosition: Equatable
  typealias Item // so-named so as to avoid some later circularity
  
  var startPosition: InternalPosition { get }
  var endPosition: InternalPosition { get }
  subscript(position: InternalPosition) -> Item { get }

  // - requires: `position != endPosition`
  func successorFor(position: InternalPosition) -> InternalPosition
  
}

// assume `==` just examines position (which seems fair here):
struct ConcretePosition<C:AlternativeCollectionType> : Equatable {
  typealias Element = C.Item

  private let collection: C
  private var position: C.InternalPosition

  func isEndPosition() -> Bool {
    return position == collection.endPosition
  }

  func dereference() -> Element? {
    if isEndPosition() { return nil }
    return collection[position]
  }

  private func nextPosition() -> C.InternalPosition {
    precondition(!isEndPosition())
    return collection.successorFor(position)
  }

}

extension ConcretePosition : ForwardIndexType {
  func successor() -> ConcretePosition<C> { 
    return ConcretePosition<C>(
      collection: collection,
      position: nextPosition()
    )
  }
}

extension ConcretePosition: GeneratorType {
  mutating func next() -> Element? {
    guard let element = dereference() else { return nil }
    position = nextPosition()
    return element
  }
}

I think the *similarity* under this organization is pretty straightforward; although `successor()` and `next()` are definitely *not* identical, they can both be implemented as operations on the same base type, with a lot the logic being essentially common to both (that’s the part written here as `nextPosition`, which simply calls the collection's `successorFor`).

Note that under Swift’s current organization, that common logic winds up manually-inlined into both `next` and `successor`, often in ways that make the commonality harder to spot.

The above experiment’s connection-with “collections move indices” is also I hope pretty easy to spot; if you accept the premise that most concrete `ForwardIndexType` implementations will in fact need a back-reference — or the moral equivalent thereof — to be able to implement the ostensibly stand-alone `successor()`, then it seems reasonable to consider the possibility that the stand-alone `successor` is actually the special-case (a very handy case, but still a special case); if you don’t accept that premise, we’ll have to agree to disagree.

Thanks again for the consideration and the considered replies. I will be finishing up a proposal relating to this topic and it’ll be much the better for having received your responses (and Dmitri’s, also).

> 
> Jordan

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