About the PermutationGenerator


#1

PermutationGenerator confuses me that it's confirm to both of SequenceType
and GeneratorType. Should it replace by PermutationSequence and
PermutationGenerator?

Also, we should have a PermutationCollection because we can:

public struct PermutationCollection<C : CollectionType, I : CollectionType
where C.Index == I.Generator.Element> : CollectionType {

    public typealias Generator = PermutationGenerator<C, I>

    public typealias Index = I.Index

    public typealias Element = C.Generator.Element

    private let _base: C

    private let _indices: I

    public subscript(idx: Index) -> Element {

        return _base[_indices[idx]]

    }

    public var startIndex : Index {

        return _indices.startIndex

    }

    public var endIndex : Index {

        return _indices.endIndex

    }

    public var count : Index.Distance {

        return _indices.count

    }

    public func generate() -> Generator {

        return PermutationGenerator(elements: _base, indices: _indices)

    }

}

and some methods provide:

public extension CollectionType {

    @warn_unused_result

    func collect<I : SequenceType where Index == I.Generator.Element>(indices:
I) -> PermutationGenerator<Self, I> {

        return PermutationGenerator(elements: self, indices: indices)

    }

    @warn_unused_result

    func collect<I : CollectionType where Index ==
I.Generator.Element>(indices:
I) -> PermutationCollection<Self, I> {

        return PermutationCollection(_base: self, _indices: indices)

    }

}

public extension LazyCollectionType {

    @warn_unused_result

    func collect<I : SequenceType where Elements.Index == I.Generator.

(indices: I) -> LazySequence<PermutationGenerator<Elements, I>> {

        return self.elements.collect(indices).lazy

    }

    @warn_unused_result

    func collect<I : CollectionType where Elements.Index == I.Generator.

(indices: I) -> LazyCollection<PermutationCollection<Elements, I>> {

        return self.elements.collect(indices).lazy

    }

}


(Lily Ballard) #2

We have plenty of examples of GeneratorTypes that also conform to
SequenceType. There's no harm in it, and it saves having to declare a
separate type that consists solely of a generate() method that returns
the generator. In fact, the stdlib automatically derives the generate()
method for any GeneratorType that conforms to SequenceType already,
specifically to make this pattern as easy as possible. The only thing at
all odd about this is the name PermutationGenerator doesn't tell you
it's a sequence, but that's no different than AnyGenerator,
EmptyGenerator, EnumerateGenerator, FlattenGenerator, IndexingGenerator,
JoinGenerator, LazyFilterGenerator, LazyMapGenerator, RangeGenerator,
and UnsafeBufferPointerGenerator (though to be fair all of those have a
matching distinct Sequence type).

As for PermutationCollection, that's not a bad idea. I guess the biggest
objection is that I'm not sure if PermutationGenerator is even pulling
its own weight, and adding more permutation types won't help. I don't
see any uses of PermutationGenerator in the stdlib, and I've never found
a use for it in my own code, though I imagine that someone somewhere is
actually using it. In any case, the argument "because we can" isn't
sufficient to add something to the stdlib; it has to actually be of
enough use to be worth both the added maintenance burden and the added
code size.

That said, even if we do add a PermutationGenerator, I definitely don't
think extending CollectionType with a collect() method set like that is
worth doing. If we did have a method it should probably be called
"permute", but I doubt enough people would use it to be worth the added
semantic overhead of yet another collection method.

-Kevin Ballard

···

On Wed, Dec 30, 2015, at 06:22 PM, Susan Cheng via swift-evolution wrote:

PermutationGenerator confuses me that it's confirm to both of
SequenceType and GeneratorType. Should it replace by
PermutationSequence and PermutationGenerator?

Also, we should have a PermutationCollection because we can:

public struct PermutationCollection<C : CollectionType, I :
CollectionType where C.Index == I.Generator.Element> :
CollectionType {

public typealias Generator = PermutationGenerator<C, I>

public typealias Index = I.Index

public typealias Element = C.Generator.Element

private let _base: C

private let _indices: I

public subscript(idx: Index) -> Element {

return _base[_indices[idx]]

}

public var startIndex : Index {

return _indices.startIndex

}

public var endIndex : Index {

return _indices.endIndex

}

public var count : Index.Distance {

return _indices.count

}

public func generate() -> Generator {

return PermutationGenerator(elements: _base, indices: _indices)

}

}

and some methods provide:

publicextensionCollectionType {

@warn_unused_result

func collect<I : SequenceTypewhereIndex ==
I.Generator.Element>(indices: I) -> PermutationGenerator<Self, I> {

return PermutationGenerator(elements: self, indices: indices)

}

@warn_unused_result

func collect<I : CollectionType where Index ==
I.Generator.Element>(indices: I) -> PermutationCollection<Self, I> {

return PermutationCollection(_base: self, _indices: indices)

}

}

publicextensionLazyCollectionType {

@warn_unused_result

func collect<I : SequenceTypewhereElements.Index ==
I.Generator.Element>(indices: I) ->
LazySequence<PermutationGenerator<Elements, I>> {

return self.elements.collect(indices).lazy

}

@warn_unused_result

func collect<I : CollectionTypewhereElements.Index ==
I.Generator.Element>(indices: I) ->
LazyCollection<PermutationCollection<Elements, I>> {

return self.elements.collect(indices).lazy

}

}

_________________________________________________
swift-evolution mailing list swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


#3

As I know SequenceType should have behaved as immutable structure and it
provides method to get a mutable GeneratorType which generates value from
start of sequence.
But the PermutationGenerator break this rule, every time it changes it's
state, it cannot get the generator with the start of sequence.


(Dmitri Gribenko) #4

Sequences are not immutable. A sequence is allowed to be consumed by
iterating over its generator. If the type you have is a sequence, you can
only assume that you can access the elements only once. For example, a
socket can be modeled as a sequence of bytes. Once the bytes are consumed
from the corresponding generator, they are gone from the sequence.

Dmitri

···

On Thu, Dec 31, 2015 at 2:01 PM, Susan Cheng via swift-evolution < swift-evolution@swift.org> wrote:

As I know SequenceType should have behaved as immutable structure and it
provides method to get a mutable GeneratorType which generates value from
start of sequence.

--
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@gmail.com>*/


#5

yes for sequences are not immutable. I get confused.

no for sequences should be definition of lists of values. Just
like Fibonacci sequence, we can calculate the values form the start of
the Fibonacci sequence one by one. But we are not accessing the values
of Fibonacci sequence.

A socket can be modeled as a sequence of bytes but socket(itself) is not
the sequence. It's just provide method to access the bytes sequences.

Dmitri Gribenko <gribozavr@gmail.com> 於 2015年12月31日星期四 寫道:

···

On Thu, Dec 31, 2015 at 2:01 PM, Susan Cheng via swift-evolution < > swift-evolution@swift.org > <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>> wrote:

As I know SequenceType should have behaved as immutable structure and it
provides method to get a mutable GeneratorType which generates value from
start of sequence.

Sequences are not immutable. A sequence is allowed to be consumed by
iterating over its generator. If the type you have is a sequence, you can
only assume that you can access the elements only once. For example, a
socket can be modeled as a sequence of bytes. Once the bytes are consumed
from the corresponding generator, they are gone from the sequence.

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@gmail.com
<javascript:_e(%7B%7D,'cvml','gribozavr@gmail.com');>>*/


(Dave Abrahams) #6

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

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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

···

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution <swift-evolution@swift.org> wrote:


(Erica Sadun) #7

It does seem that in Swift the concepts of collection, sequence, permutation, stream, etc are a bit muddled.

-- E

···

On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution <swift-evolution@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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Erica Sadun) #8

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/
And here's Oisin's user-input sequence: 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@apple.com> wrote:

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@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@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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave


(Dave Abrahams) #9

I'm trying to work them out, so it's still muddled.

Right now, I think SequenceType is better described as CollectionWalkType

Why do you say so?

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/
And here's Oisin's user-input sequence: 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

All you’ve descrived here is the lack of a distinct protocol for finite sequences, which doesn't indicate “muddled concepts” at all. It's a conscious choice of protocol granularity per this posting <http://news.gmane.org/find-root.php?message_id=2A3E0C76-1C88-4752-8A70-AA64BB14223A@apple.com> In the development of the standard library we’ve tried to keep the API surface area small and given all the factors described in that posting, the conservative choice was to not separate them.

That’s not to say I’m opposed to carving out a place for finite sequences (and as we approach ABI stability now would be the time to do it) but I’d like to clearly understand why we’re doing it, and ideally I’d like to address all of the concerns noted in the post.

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

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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

-Dave

···

On Dec 31, 2015, at 9:52 AM, Erica Sadun <erica@ericasadun.com> wrote:

On Dec 31, 2015, at 10:09 AM, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


(Dave Abrahams) #10

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

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/
And here's Oisin's user-input sequence: 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

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

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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

···

On Dec 31, 2015, at 10:52 AM, Donnacha Oisín Kidney <oisin.kidney@gmail.com> wrote:

On 31 Dec 2015, at 17:52, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 31, 2015, at 10:09 AM, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


(Tino) #11

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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!


(Dmitri Gribenko) #12

Those are collections. Collections can be iterated over multiple times.

Dmitri

···

On Thu, Dec 31, 2015 at 3:04 PM, Susan Cheng <susan.doggie@gmail.com> wrote:

yes for sequences are not immutable. I get confused.

no for sequences should be definition of lists of values. Just like
Fibonacci sequence, we can calculate the values form the start of the
Fibonacci sequence one by one. But we are not accessing the values of
Fibonacci sequence.

--
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@gmail.com>*/


(Dmitri Gribenko) #13

Well, I didn't say you need to iterate to the very end, or that you
need to iterate them serially. You can take two generators from the
same collection, and advance them independently, in interleaved
fashion, for example.

Dmitri

···

On Thu, Dec 31, 2015 at 3:51 PM, Tino Heth <2th@gmx.de> 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 :wink:
(only nitpicking — I just couldn't resist)

--
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@gmail.com>*/


(Donnacha Oisín Kidney) #14

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.

···

On 31 Dec 2015, at 17:52, Erica Sadun via swift-evolution <swift-evolution@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/
And here's Oisin's user-input sequence: 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@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #15

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:

I probably failed to make clear that the code below works today, and doesn’t crash the compiler:

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

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/
And here's Oisin's user-input sequence: 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

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

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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

···

On Dec 31, 2015, at 1:02 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 31, 2015, at 10:52 AM, Donnacha Oisín Kidney <oisin.kidney@gmail.com <mailto:oisin.kidney@gmail.com>> wrote:

On 31 Dec 2015, at 17:52, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 31, 2015, at 10:09 AM, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


#16

I don't think so.

As we don't say "Fibonacci collection", we know Fibonacci numbers are in
order. But we can't tell the number immediately if I asked a specific index
of Fibonacci sequence. The only way is calculate the sequence one by one
from start.

So we need the collection, and collection do the jobs. But it true that
collections are sequences.
Swift is also have this definition, in concrete implementation way.

Dmitri Gribenko <gribozavr@gmail.com> 於 2015年12月31日星期四 寫道:

···

On Thu, Dec 31, 2015 at 3:04 PM, Susan Cheng <susan.doggie@gmail.com > <javascript:;>> wrote:
> yes for sequences are not immutable. I get confused.
>
> no for sequences should be definition of lists of values. Just like
> Fibonacci sequence, we can calculate the values form the start of the
> Fibonacci sequence one by one. But we are not accessing the values of
> Fibonacci sequence.

Those are collections. Collections can be iterated over multiple times.

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@gmail.com
<javascript:;>>*/


(Jordan Rose) #17

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

···

On Dec 31, 2015, at 9:52, Erica Sadun via swift-evolution <swift-evolution@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/
And here's Oisin's user-input sequence: 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@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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 :wink:
(only nitpicking — I just couldn't resist)

Happy new year!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #18

That's OK, collections can have Forward indices which have exactly
these properties.

Dmitri

···

On Thu, Dec 31, 2015 at 3:36 PM, Susan Cheng <susan.doggie@gmail.com> wrote:

I don't think so.

As we don't say "Fibonacci collection", we know Fibonacci numbers are in
order. But we can't tell the number immediately if I asked a specific index
of Fibonacci sequence. The only way is calculate the sequence one by one
from start.

--
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@gmail.com>*/


#19

sequence can have more methods with it, we can find first five values of
a sequence.

but we don't do this with a generator

struct Fibonacci: SequenceType {

    var first, second: Int

    func generate() -> AnyGenerator<Int> {

        var a = first

        var b = second

        return anyGenerator {

            let temp = a

            (a, b) = (b, a + b)

            return temp

        }

    }

}

Array(Fibonacci(first: 1, second: 1).prefix(10))

Happy new year to all

···

2015-12-31 21:57 GMT+08:00 Dmitri Gribenko <gribozavr@gmail.com>:

On Thu, Dec 31, 2015 at 3:36 PM, Susan Cheng <susan.doggie@gmail.com> > wrote:
> I don't think so.
>
> As we don't say "Fibonacci collection", we know Fibonacci numbers are in
> order. But we can't tell the number immediately if I asked a specific
index
> of Fibonacci sequence. The only way is calculate the sequence one by one
> from start.

That's OK, collections can have Forward indices which have exactly
these properties.

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@gmail.com>*/


#20

How GeneratorType confirm 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@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>.
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:
> : 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 })