> On 3 May 2017, at 5:32 PM, Anders Ha via swift-evolution > <[email protected]> wrote: > > 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.
Perhaps I should rephrase this for clarity: Another important constraint missed is that `Sequence` and derived protocols do not imply constructibility and manipulability. These capabilities belong to standalone protocols like `RangeReplaceableCollection` and `SetAlgebra`. So a default of `[Element]` for `Sequence.filter` is inevitable, even with we have higher-kinded types. > > 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 _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
