[swift-evolution] [Pitch] Achieving a heterogeneous collection of Equatables

[Matthew Johnson]

> On Dec 22, 2015, at 10:48 AM, Joe Groff via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
>> On Dec 21, 2015, at 1:45 AM, Roopesh Chander via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> Hi all,
>> 
>> We know that as of Swift 2.0, if a protocol uses `Self` (like
>> Equatable does), it cannot be used in a heterogeneous collection. This
>> is a pain point, and has been talked about many times (for instance,
>> in Brent Simmons' Swift Diary: http://inessential.com/swiftdiary).
>> 
>> I realize that this problem is intertwined with the use of associated
>> types, but if we forget about associated types for the moment, I
>> believe we can get a heterogeneous collection of Equatable elements to
>> work.
>> 
>> ## The problem
>> 
>> There's no problem in creating a heterogeneous collection when there's
>> no `Self`:
>> 
>>   struct Collection<Element> {
>>   }
>> 
>>   protocol LooseEquatable {
>>       func isEqualTo(other: LooseEquatable) -> Bool
>>   }
>> 
>>   let c1 = Collection<LooseEquatable>()
>> 
>> The type characteristics of c1's elements can be deduced at compile
>> time, so this works.
>> 
>> But when `Self` is used in the protocol:
>> 
>>   protocol StrictEquatable {
>>       func isEqualTo(other: Self) -> Bool
>>   }
>> 
>>   let c2 = Collection<StrictEquatable>()
>> 
>> The type characteristics of c2's elements (for example, what are the
>> signatures of the methods that they should have) are indeterminable at
>> compile time because `Self` isn't yet "bound" to a type. For this to
>> work, the `Self` in StrictEquatable might have to bind to different
>> types at runtime for different subtypes of StrictEquatable.
>> 
>> This, per my understanding, is why Swift errors out. Assuming this
>> understanding is correct, I'd like to pitch a solution.
>> 
>> ## The pitch
>> 
>> What I'm about to suggest is closely related to Joe Groff's suggestion
>> to use an EquatesWith here:
>> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002300.html
>> 
>> Let's say we introduce a new keyword called `Subtype` that can be used
>> when defining a protocol. `Subtype` binds to the closest subtype that
>> fully *implements* the protocol. (In contrast, `Self` binds to the
>> non-protocol type at the end of the protocol hierarchy.)
>> 
>> For example:
>> 
>>   // Type hierarchy: P -> Q -> R -> S
>>   // P, Q, R are protocols; S is a struct.
>> 
>>   protocol P {
>>       func f1(t: Subtype)
>>   }
>>   protocol Q : P {
>>       func f2()
>>   }
>>   protocol R : Q {
>>   }
>>   extension R {
>>       func f1(t: R) { } // Implementing P
>>       func f2() { }     // Implementing Q
>>   }
>>   struct S : R {
>>   }
>> 
>>   let s = Collection<S>() // Okay: P's Subtype is bound to R
>>   let r = Collection<R>() // Okay: P's Subtype is bound to R
>>   let q = Collection<Q>() // Error: Subtype cannot be resolved
>>   let p = Collection<P>() // Error: Subtype cannot be resolved
>> 
>> `Self` can only bind to a non-protocol type like S, but `Subtype` can
>> bind to either a protocol or a non-protocol type, depending on where
>> the protocol gets implemented. Here, the P protocol is implemented in
>> the sub-protocol R, and so the `Subtype` in P binds to R. If `Subtype`
>> cannot be resolved, it should result in a compilation error.
>> 
>> In the standard library, if we replace all `Self`s in Equatable with
>> `Subtype`, we still maintain type safety (so `1 == 1.0` won't compile,
>> like it is now), but we will, at the same time, be able to create
>> heterogeneous collections of elements conforming to a sub-protocol of
>> Equatable, thereby fixing problems like this:
>> http://inessential.com/2015/08/05/swift_diary_9_where_im_stuck
>> 
>> That said, while this conceptually looks good, I have no idea whether
>> it's practically viable. I'd love to hear the community's and the
>> compiler team's take on this suggestion.
> 
> You wouldn't really need a different protocol keyword to achieve this. You're providing a conformance for the type protocol<R>: P, rather than saying T: P for all T: R, as happens today. That's a property of the conformance rather than the protocol itself. What you're proposing is closer to the other approach I laid out, allowing protocol types to be extended to conform to protocols themselves:
> 
> extension protocol<R>: P { // We're extending the protocol *type* to conform, not its conformers
>  func f1(t: R) { }
> }

I like it!  Extend an arbitrary existential (and it’s conforming types?) with additional conformances.  That is pretty cool!