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

[Joe Groff]

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

-Joe