So a bit of correction: generic protocol had been dismissed in the Generic Manifesto specifically for sequences and collections, because it would permit multiple conformances of a certain type to the same protocol with different types of elements, and it is considered wrong.
`Self` in a protocol refers not to the unbound generic type, but to the specialized one, e.g. `Array<T>` where T is bound, instead of `Array`. For your code snippets to work, the compiler would need to explicitly “unspecialize” the specialised `Self` and parameterise it with a different type. This notion is called higher-kinded types. https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#higher-kinded-types For example, using the potential syntax in the manifesto: extension RangeReplaceableCollection { func filter<Filtered>(_ isIncluded: (Element) -> Bool) -> Filtered where Filtered ~= Self, Filtered.Element == Element func map<Mapped>(_ transform: (Element) -> Mapped.Element) -> Mapped where Mapped ~= Self } Let’s say `Self` is `Set<Int>`, the compiler would need to be instructed to “unspecialize” it and parameterise it again, so that it still knows the resulting collection statically. Then at this point, yes, it can be statically dispatched. But for now, higher-kinded types do not seem to be on the radar at all. So to achieve the same result, there are only two options: 1. Type-erased wrappers, e.g. `AnyCollection<T>`, or generalised existential, e.g. `Collection where .Element == T`. This means dynamic dispatch. 2. Associated type, i.e. the proposal. Another important constraint you’ve missed is that only `RangeReplaceableCollection` implies the collection can be explicitly constructed. So a default of `[Element]` is necessary. Regards Anders > On 3 May 2017, at 4:57 PM, Howard Lovatt <[email protected]> wrote: > > @Anders, > > I think you can eliminate the dynamic dispatch for a struct. Using the > generic parameterised syntax rather than the where clause syntax (because it > is more compact and clearer): > > protocol Sequence<T> { > func filter(_ isIncluded: (T) -> Bool) -> Self<T> // Note: returns > Self<T> > ... > } > extension Sequence { > func filter(_ isIncluded: (T) -> Bool) -> Self<T> { // Note: returns > Self<T> > var result = Self<T> > for element in self { > if isIncluded(element) { result.append(element) } > } > return result > } > ... > } > struct Set<T>: Sequence<T> { ... } // Inherits filter from extension > > For struct `Set<T>` `Self<T>` is `Set<T>` (obviously, that is what Self > means), therefore the compiler can for both code and type checking purposes > generate: > > struct Set<T>: Sequence<T> { > func filter(_ isIncluded: (T) -> Bool) -> Set<T> { // Note: returns > Set<T> > var result = Set<T> > for element in self { > if isIncluded(element) { result.append(element) } > } > return result > } > ... > } > > This is an intermediate step for the compiler since `Set` is still generic, > in `T`. When a specific `Set` is instantiated, e.g. `let s = Set<Int>`, the > compiler can generate both for code and type checking purposes: > > struct Set<Int>: Sequence<Int> { > func filter(_ isIncluded: (Int) -> Bool) -> Set<Int> { // Note: > returns Set<Int> > var result = Set<Int> > for element in self { > if isIncluded(element) { result.append(element) } > } > return result > } > ... > } > > When you call `s.filter` there is no dynamic dispatch because `filter` is > final within a struct and the compiler also knows that this version of > `filter` returns a `Set<Int>` and therefore no dynamic dispatch on the > returned value if in a chain of calls either. > > Have I made a mistake in the above? > > -- Howard. > > On 3 May 2017 at 17:27, Anders Ha <[email protected]> wrote: > Returning `Self<T>` requires higher kinded type. Note that parameterized > protocols are not the same as higher kinded types, since for the former > generic protocol parameters are already bound at conformance of the static > `Self` like associated types, while the later is about having a generic > static `Self`. > > IOW you cannot do `Self<T>` statically without higher kinded type. The best > you can get is generalized existential, e.g. `filter` returning a `Collection > where .Element == T` or `Collection<T>` if protocols can be parameterized. > > The compiler cannot eliminate virtual dispatching for existentials, because > this is what existential is by definition — knowing how to manipulate it at > static time, but not the type which varies at runtime. All non-class > existentials are dispatched through their associated protocol witness tables. > > Regards > Anders > > On 3 May 2017, at 09:05, Howard Lovatt <[email protected]> wrote: > >> My experience with languages that have generalised existential is that they >> are superior in many circumstances; not just for collections, e.g. I gave >> the example of the comparison protocol. >> >> I don't think methods called on a returned generalised existential have to >> be called via a Vtable. If the return type is Self<T> then the compiler can >> eliminate the Vtable for selfs that are value types. For selfs that are >> classes it would still have to use a Vtable though, because classes always >> use Vtables! In most cases the return type will be Self<T> and in most cases >> the Self will be a value type, so I would argue that in most cases a Vtable >> won't be used. >> >> -- Howard. >> >> On 2 May 2017, at 8:57 pm, Anders Ha <[email protected]> wrote: >> >>> I would like to add that generalized existential is not really a better >>> solution than letting the collection optionally and statically supply one. >>> It consequentially forces all calls to the filtered collections >>> virtual/dynamic. >>> >>> Higher kinded type would ideally help, but we all know it is not coming >>> anytime soon, or perhaps ever. >>> >>> Regards >>> Anders >>> >>> On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution >>> <[email protected]> wrote: >>> >>>> Howard, this is also mentioned in the generics manifesto under "Opening >>>> existentials," and it's received plentiful discussion and will surely >>>> receive more as these issues become addressed in future proposals. Let's >>>> not divert the conversation here about map and filter. >>>> On Mon, May 1, 2017 at 19:36 Howard Lovatt <[email protected]> wrote: >>>> Yes, I know the change I suggested involves making generalised >>>> existentials. I am suggesting not making *any* changes until such effort >>>> is available. I understand that this would be after Swift 4. I think the >>>> wait would be worthwhile. >>>> >>>> As an aside: Currently one of the big issues with generalised existentials >>>> in Swift is with Self (which you can think of as a form of generic >>>> argument). Currently: >>>> >>>> protocol Equatable { >>>> static func ==(lhs: Self, rhs: Self) -> Bool >>>> ... >>>> } >>>> struct Int: Equatable { ... } >>>> let e1: Equatable = 1 >>>> let e2: Equatable = 2 >>>> if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the >>>> same dynamic type >>>> >>>> I would replace this with: >>>> >>>> protocol Equatable<T> { // Use T instead of Self >>>> static func ==(lhs: T, rhs: T) -> Bool >>>> ... >>>> } >>>> struct Int: Equatable<Int> { ... } >>>> let e1: Equatable<Int> = 1 >>>> let e2: Equatable<Int> = 2 >>>> if e1 == e2 { ... } // No longer an error since they are both >>>> Equatable<Int> >>>> >>>> As an aside on the aside, even better: >>>> >>>> protocol Equatable<T = Self> { // T defaults to Self >>>> static func ==(lhs: T, rhs: T) -> Bool >>>> ... >>>> } >>>> struct Int: Equatable { ... } // T is Int, the default is Self >>>> let e1: Equatable = 1 // T is Int, the default is Self >>>> let e2: Equatable = 2 // T is Int, the default is Self >>>> if e1 == e2 { ... } // No longer an error since they are both >>>> Equatable<Int> >>>> >>>> Everything I am suggesting is done in other languages and from my personal >>>> experience works out better. >>>> >>>> >>>> -- Howard. >>>> >>>> On 2 May 2017 at 09:53, Xiaodi Wu <[email protected]> wrote: >>>> Howard, take a look at the generics manifesto section on generic protocols: >>>> >>>> https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md >>>> >>>> It explains very nicely how what you're really asking for is not generic >>>> protocols but generalized existentials. This would be nice to have, but >>>> it's clearly not happening within the next month and it wouldn't change >>>> the solution for filter, for which this proposal is the obvious fix. >>>> >>>> On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution >>>> <[email protected]> wrote: >>>>> review of SE-0174 "Change `filter` to return an associated type" >>>>> >>>>> • What is your evaluation of the proposal? >>>> I think a change in this 'area' is valuable because currently always >>>> returning an array from collection operations is limiting. However I think >>>> this proposal feels like 'papering' over problems rather than fixing the >>>> root cause. I think it would be better to reject this and do two more >>>> adventurous proposals instead: >>>> >>>> 1. Allow protocols to be generic, instead of associated types, so that >>>> you can write Sequence<T> >>>> 2. Allow Self to accept a generic argument, so that you can write Self<T> >>>> >>>> With these to, admittedly much more major changes, you can then write: >>>> >>>> protocol Sequence<T> { >>>> func filter(_ isIncluded: (T) throws -> Bool) rethrows -> >>>> Sequence<T> >>>> func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M> >>>> } >>>> extension RangeReplaceableCollection { >>>> func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> >>>> { >>>> var result = Self<T>() >>>> for element in self { >>>> if try isIncluded(element) { >>>> result.append(element) >>>> } >>>> } >>>> return result >>>> } >>>> func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> { >>>> var result = Self<M>() >>>> for element in self { >>>> try result.append(mapper(element)) >>>> } >>>> return result >>>> } >>>> } >>>> >>>> Which I think both reads better and is more powerful since it allows map >>>> to be written also. >>>> >>>>> • Is the problem being addressed significant enough to warrant a change >>>>> to Swift? >>>> Yes, return an array is a real pain >>>> >>>>> • Does this proposal fit well with the feel and direction of Swift? >>>> Yes and no, really smacks of papering over other flaws. Might box Swift >>>> into a corner were other problems can't be fixed because the underlying, >>>> real, problems still remain. >>>> >>>>> • If you have used other languages or libraries with a similar feature, >>>>> how do you feel that this proposal compares to those? >>>> Virtually all other languages I have used, e.g. Java, Scala, use the >>>> solution I presented above. >>>> >>>>> • How much effort did you put into your review? A glance, a quick >>>>> reading, or an in-depth study? >>>> Have been bitten by this and have written my own collection hierarchy to >>>> overcome this limitation, and others, of the current library. >>>> >>>> -- Howard. >>>> >>>> On 29 Apr 2017, at 10:06 am, Douglas Gregor <[email protected]> wrote: >>>> >>>>> Hello Swift community, >>>>> >>>>> The review of SE-0174 "Change `filter` to return an associated type" >>>>> begins now and runs through May 3, 2017. The proposal is available here: >>>>> >>>>> https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md >>>>> Reviews are an important part of the Swift evolution process. All reviews >>>>> should be sent to the swift-evolution mailing list at >>>>> >>>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>>> or, if you would like to keep your feedback private, directly to the >>>>> review manager. When replying, please try to keep the proposal link at >>>>> the top of the message: >>>>> >>>>> Proposal link: >>>>> >>>>> https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md >>>>> Reply text >>>>> Other replies >>>>> What goes into a review? >>>>> >>>>> The goal of the review process is to improve the proposal under review >>>>> through constructive criticism and, eventually, determine the direction >>>>> of Swift. When writing your review, here are some questions you might >>>>> want to answer in your review: >>>>> >>>>> • What is your evaluation of the proposal? >>>>> • Is the problem being addressed significant enough to warrant a change >>>>> to Swift? >>>>> • Does this proposal fit well with the feel and direction of Swift? >>>>> • If you have used other languages or libraries with a similar feature, >>>>> how do you feel that this proposal compares to those? >>>>> • How much effort did you put into your review? A glance, a quick >>>>> reading, or an in-depth study? >>>>> More information about the Swift evolution process is available at >>>>> >>>>> https://github.com/apple/swift-evolution/blob/master/process.md >>>>> Thank you, >>>>> >>>>> -Doug Gregor >>>>> >>>>> Review Manager >>>>> >>>>> _______________________________________________ >>>>> swift-evolution-announce mailing list >>>>> [email protected] >>>>> https://lists.swift.org/mailman/listinfo/swift-evolution-announce >>>> _______________________________________________ >>>> swift-evolution mailing list >>>> [email protected] >>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>> >>>> _______________________________________________ >>>> swift-evolution mailing list >>>> [email protected] >>>> https://lists.swift.org/mailman/listinfo/swift-evolution > _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
