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

[Roopesh Chander]

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.

roop.